#2**+10 **

**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

#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**

Guest Dec 10, 2018

#2**+10 **

Best Answer

**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**+1 **

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

CPhill
Dec 11, 2018

#4**+9 **

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