+26367 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}\)
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
+26367 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}\)
+128656 That's an interesting way of solving this problem, heureka......how was that method derived???
+26367 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}\)
