Powerful Factors

The problem required the use of the facts that

$$\begin{eqnarray} x^2 - y^2 &=& (x - y)(x + y) \quad\mbox{and}\\ x^3 + y^3 &=& (x + y)\left(x^2 - xy +y^2\right) \end{eqnarray}$$

to find the highest power of 2 and the highest power of 3 which divide $5^{36}-1.$

Alexander Marynovsky from Israel sent in this solution.

$$\begin{eqnarray} 5^{36} - 1 &=& (5^{18} - 1)(5^{18} + 1)\\ &=& (5^9 - 1) (5^9 + 1) (5^6 + 1) (5^{12} - 5^6 + 1)\\ &=& (5^3 - 1)(5^6 + 5^3 + 1)(5^3 + 1)(5^6 - 5^3 + 1)(5^2 +1)(5^4 - 5^2 + 1) (5^{12} - 5^6 + 1)\\ &=& (5^3 - 1)(5^6 + 5^3 + 1)(5 + 1)(5^2- 5+1)(5^6 - 5^3 + 1)\\ & &(5^2 +1)(5^4 - 5^2 + 1) (5^{12} - 5^6 + 1) \end{eqnarray}$$

Remember what we have got here, I'll use it twice (for 2 and for 3).

Now let's take out the 2's from it.

Because $5^n - 5^k$ is even and therefore $5^n - 5^k +1$ is odd, $(5^2- 5+1), (5^6- 5^3 +1), (5^4 - 5^2 +1), (5^{12} -5^6 +1)$ obviously can't be divided by 2.

So we are left with

$$ (5^3 - 1) (5^6 + 5^3 + 1)(5 + 1)(5^2 +1) = 124 . 15751 . 6 . 26 = 2^4 . 3 . 13 . 31 . 15751 $$

So the highest power of 2 is 4.

$$\begin{eqnarray} (5^2- 5+1)(5^6&-& 5^3 +1)(5^4 - 5^2 +1)(5^{12} - 5^6 +1) \\ &=& 21 (125.124 + 1) (25.24 + 1 ) ( 125.125.124.126 + 1)\\ &=& 21 . 15501 . 601 (1000.125.31.63 + 1)\\ &=& 21 . 15501 . 601 . 244125001 \end{eqnarray}$$

Combining these results:

$$ 5^{36} - 1 = 2^4 . 3^3. 7 . 13. 31. 5167. 15751 . 601 . 37. 6597973 $$

The highest power of 3 is 3.

The method can be shortened using modulus arithmetic.