Highest power of a number that divides a larger number?

Question

Is the method of prime factorization valid for finding largest power of a number n such that n divides the number x also x>n?

E.g:-

Question: Highest power of 2 that divides $2^2 * 3^3 * 4^4 * 5^5 * 6^6$ ?

Ans: $16$ by using prime factorization for eliminating $2$ as $2^{16}$ will divide $2^2 * 3^3 * 4^4 * 5^5 * 6^6$.

Steps:

1. $2^2 * 3^3 * 4^4 * 5^5 * 6^6$.
2. $2^2 * 3^3 * 2^8 * 5^5 * 3^6 * 2^6 $
3. $2^{16} * 3^9 * 5^5 $
4. Now max power of 2 that can divide $2^{16} * 3^9 * 5^5 $ is $2^{16}$ only.

My doubt is after getting rid of $2^{16}$ from numerator in step 4 we still have $3^9 * 5^5$ which can be divided using 2 though we won't get an integral solution so the approach using prime factorization is incorrect ?

Reference Video:- https://www.youtube.com/watch?v=HNeiXfQ6EAk&list=PLK4eozjPKMfHJCRkHI34sOG7Pk5c31UTq&index=24

Also we cannot make use of calculator for solving this problem can anyone verify the method in the video if possible do describe an alternate method.

Thanks

Answer 1

The method of prime factorization is correct, as shown through your first example. The second example you have cited is wrong. $2$ does not divide $3^{9} \cdot 5^{5} = 61509375$ because there is no even number in the prime factorization.

Answer 2

The method of prime factorization is correct, but inefficient. For example, $234525482759285025987250295345695702224252525239458250845205825092502520592$ is rather hard to factor, but it is quite easy to check that it is divisible by $2^4$ but not by $2^5$.