+0  
 
0
122
4
avatar

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

 Dec 10, 2018

Best Answer 

 #2
avatar+21855 
+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}\)

 

laugh

 Dec 11, 2018
 #1
avatar
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
avatar+21855 
+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}\)

 

laugh

heureka Dec 11, 2018
 #3
avatar+98102 
+1

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

 

 

cool cool cool

CPhill  Dec 11, 2018
 #4
avatar+21855 
+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}\)

 

laugh

heureka  Dec 12, 2018

34 Online Users

avatar
avatar
avatar
avatar
avatar
avatar
avatar