+0

# help number theory

0
229
3

Find the largest integer n for which 12^n evenly divides $$150!$$.

Apr 17, 2022

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