+0  
 
0
88
3
avatar

Find the largest integer n for which 12^n evenly divides \(150!\).

 Apr 17, 2022
 #1
avatar
0

Since 12 ==2^2 * 3, therefore the largest exponent of 3 in the factorization of 150! will be:

 

150!== 2^146 * 3^72 * 5^37 * 7^24 * 11^14 * 13^11 * 17^8 * 19^7 * 23^6 * 29^5 * 31^4 * 37^4 * 41^3 * 43^3 * 47^3 * 53^2 * 59^2 * 61^2 * 67^2 * 71^2 * 73^2 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149.

 

Therefore, 12^72 should divide 150! and:

 

150! mod 12^72 ==0.

 Apr 17, 2022
 #2
avatar+9459 
+1

Note that \(150! = 1\times 2 \times 3 \times 4\times \cdots\).

To find the largest n for which 12^n divides 150!, we find the largest m and k for which 2^m divides 150! and 3^k divides 150!.

 

The formula for finding the largest power n of a prime p for which p^n divides k! is: \(\max n = \displaystyle\sum_{r = 1}^\infty \left\lfloor\dfrac{k}{p^r}\right\rfloor\).

 

Then, \(\max m = \displaystyle\sum_{r = 1}^\infty \left\lfloor\dfrac{150}{2^r}\right\rfloor=\left\lfloor\dfrac{150}{2}\right\rfloor+ \left\lfloor\dfrac{150}{2^2}\right\rfloor+ \left\lfloor\dfrac{150}{2^3}\right\rfloor+ \left\lfloor\dfrac{150}{2^4}\right\rfloor+ \left\lfloor\dfrac{150}{2^5}\right\rfloor+ \left\lfloor\dfrac{150}{2^6}\right\rfloor+ \left\lfloor\dfrac{150}{2^7}\right\rfloor\), since \(\left\lfloor\dfrac{150}{2^r}\right\rfloor = 0\) for any integer r >= 8.

Hence, \(\max m = 146\). i.e., \(2^{146}\Big|150!\), but \(2^{147}\nmid 150!\).

Similarly, we have \(\max k = 72\). i.e., \(3^{72}\Big|150!\), but \(3^{73}\nmid 150!\).

 

Now, we have 146 "two"s and 72 "three"s for us to pick from the prime factorization of 150!. To make 12, we take 2 "two"s and 1 "three". In total, we can make \(\min\left(\dfrac{146}2, 72\right) = 72\) "twelve"s from what we have.

 

Therefore, the largest power of 12 such that 12^n divides 150! is \(n = 72\).

 Apr 17, 2022
 #3
avatar
+1

Just Divide 150 by powers of 3 as follows:

 

Floor [150/3]  +  [150/3^2]  +  [150 / 3^3]  +  [150 / 3^4] ==50 + 16 + 5 + 1 ==72 - is the largest power of 12.

 Apr 17, 2022

7 Online Users

avatar