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.
+9519 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\).
