You may also like

problem icon

Poly Fibs

A sequence of polynomials starts 0, 1 and each poly is given by combining the two polys in the sequence just before it. Investigate and prove results about the roots of the polys.

problem icon

Fibonacci Factors

For which values of n is the Fibonacci number fn even? Which Fibonnaci numbers are divisible by 3?

problem icon

Code to Zero

Find all 3 digit numbers such that by adding the first digit, the square of the second and the cube of the third you get the original number, for example 1 + 3^2 + 5^3 = 135.

Powerful Factors

Age 16 to 18 Challenge Level:

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.