We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
185
4
avatar

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

 Dec 10, 2018

Best Answer 

 #2
avatar+22188 
+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+22188 
+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+100564 
+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+22188 
+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

13 Online Users

avatar
avatar
avatar
avatar