+0

# prime factorization

0
66
4

int the prime factorization of 109! what is the exponent of 3?

Dec 10, 2018

#2
+20831
+5

int the prime factorization of 109! what is the exponent of 3?

$$\begin{array}{|rcl|} \hline \text{The exponent of 3 is } \\ && \lfloor \frac{109}{3} \rfloor +\lfloor \frac{109}{9} \rfloor +\lfloor \frac{109}{27} \rfloor +\lfloor \frac{109}{81} \rfloor \\ &=& 36 + 12 +4 +1\\ &=& 53\\ \hline \end{array}$$

Dec 11, 2018

#1
0

Factor 109! =

2^104×3^53×5^25×7^17×11^9×13^8×17^6×19^5×23^4×29^3×31^3×37^2×41^2×43^2×47^2×53^2×59×61×67×71×73×79×83×89×97×101×103×107×109 (260 prime factors, 29 distinct).

= 3^53

Dec 10, 2018
#2
+20831
+5

int the prime factorization of 109! what is the exponent of 3?

$$\begin{array}{|rcl|} \hline \text{The exponent of 3 is } \\ && \lfloor \frac{109}{3} \rfloor +\lfloor \frac{109}{9} \rfloor +\lfloor \frac{109}{27} \rfloor +\lfloor \frac{109}{81} \rfloor \\ &=& 36 + 12 +4 +1\\ &=& 53\\ \hline \end{array}$$

heureka Dec 11, 2018
#3
+94501
+1

That's an interesting way of solving this problem, heureka......how was that method derived???

CPhill  Dec 11, 2018
#4
+20831
+4

Hello CPhill,

"how was that method derived":

1.)

This is the Legendre Theorem from 1808:

Source: Legendre's Theorem - The Prime Factorization of Factorials https://www.cut-the-knot.org/blue/LegendresTheorem.shtml

2.)

There is a second nice Theorem from Legendre to solve this problem:

Source: Legendre's Theorem - The Prime Factorization of Factorials https://www.cut-the-knot.org/blue/LegendresTheorem.shtml

Example:

The prime factorization of 109!  So $$n = 109$$

What is the exponent of 3?  So $$p = 3$$
$$\begin{array}{|rcll|} \hline 109 \text{ in base } 3: \\ 109_{10} = 11001_3 \\ \hline \end{array}$$

The exponent of 3 is:

$$\begin{array}{|rcll|} \hline \text{The exponent of 3} &=& \dfrac{\overbrace{109}^{=n}-(\overbrace{1+1+0+0+1}^{\text{sum of all the digits in the expansion of n in base p}})}{\underbrace{3}_{=p}-1} \\ \text{The exponent of 3} &=& \dfrac{ 109 - 3}{2} \\\\ \text{The exponent of 3} &=& \dfrac{ 106}{2} \\\\ \mathbf{\text{The exponent of 3}} & \mathbf{=} & \mathbf{53} \\ \hline \end{array}$$

heureka  Dec 12, 2018