Dirisibly Yours

Alan from Madras College, St Andrew's, Scotland and Alexander from Shevah-Mofet School, Israel both used induction to prove that $5^{2n+1} + 11^{2n+1} + 17^{2n+1}$ is divisible by $33$ for all non-negative integer values of n . This is Alexander's proof.

Let us assume that $p =2n+1$, which means that p is a positive odd number. In that case we need to prove that $5^p+11^p+17^p$ divides by $33$.

Obviously if $n=0$, then $p=1$ and $5+11+17=33$ divides by $33$. Let's assume that $5^p +11^p +17^p$ divides by $33$ and prove that $5^{p+2} + 11^{p+2} + 17^{p+2}$ divides by $33$ which means we need to prove that $25 \times5^p+ 121 \times11^p + 289 \times17^p$ divides by $33$.

Since we know that $5^p +11^p +17^p$ divides by $33$, we can subtract it $25$ times and we'll need to prove that $96 \times11^p+ 264 \times17^p$ divides by $33$. Now $264 = 8 \times33$ which means that $264 \times17^p$ divides by $33$. All that is left to prove is that $96 \times11^p$ divides by $33$ and we're done. As $96$ divides by $3$ and $11^p$ divides by $11$ ( $p > 0$) so $96 \times11^p$ divides by $33$. We've proven that if $5^p +11^p +17^p$ divides by $33$ then $5^{p+2} + 11^{p+2} + 17^{p+2}$ also divides by $33$ and we've checked that it is correct for $ p=1$. We have proved inductively that $5^{2n+1} + 11^{2n+1} + 17^{2n+1}$ is divisible by $33$ for all non-negative integer values of $n$ .

This can also be proved using modulus arithmetic as follows:

$5^p + 11^p + 17^p \equiv (-6)^p + 0^p + 6^p \equiv 0$ (mod 11)

We have written up our own solution to this problem, building on these ideas:

One way to solve this problem involves modulo arithmetic. You may have encountered this in the form of clock arithmetic. For example, the hours on a clock face can be considered as a modulo 12 system, with only the numbers from 1 to 12 being possible. If you add 2 hours to 11 o'clock, you get 1 rather than 13. If you add 13 hours to any time, it is effectively the same as adding 1. If you add 12, 24, 36 etc hours to any time, it is the same as adding 0. Numbers above 12 are not possible; you must convert them into numbers between 1 and 12 (inclusive) by dividing by 12 and taking the remainder.

The difference between clock arithmetic and modulo arithmetic is that in modulo arithmetic the numbers begin at 0. Therefore, modulo 12 arithmetic only allows the numbers from 0 to 11. The number 12 would become 0.

One crucial feature of the modulo arithmetic system (as regards this problem) is that if a number can be written as $0$ under modulo $n$ arithmetic, then the number is divisible by $n$. In the solution to this problem I shall use modulo $3$ and modulo $11$ arithmetic.

Technically, the everyday number system that we use is modulo infinity arithmetic, but this is a moot point.

If the expression is divisible by 3 and by 11, it must be divisible by 33. We can show that the expression is divisible by 3 and 11 by showing that the expression is equal to zero under both modulo 3 and modulo 11 arithmetic. 

We can write $5^{2n+1}$ as $25^n \times 5$.

Under modulo 3 arithmetic, $$25 \equiv 1$$ (as 25 divided by 3 leaves remainder 1) so $$25^n \equiv 1^n \equiv 1$$ Also, $5 = 2$

Therefore $$25^n \times 5 \equiv 1 \times 2 \equiv 2$$ Similarly, $$11^{2n+1} = 121^n \times 11$$ Under modulo 3 arithmetic, $$121 \equiv 1$$ so $$121^n \equiv 1^n = 1$$ and $$11 \equiv 2$$ Therefore $$121^n \times 11 \equiv 1 \times 2 = 2$$ $$17^{2n+1} = 289^n \times 17$$ Under modulo 3 arithmetic, $$289 \equiv 1$$ so $$289^n \equiv 1^n = 1$$ and $$17 \equiv 2$$ Therefore $$289^n \times 17 \equiv 1 \times 2 = 2$$ Under modulo $3$ arithmetic, the expression is equal to $2 + 2 + 2 = 6 \equiv 0$. The expression is therefore divisible by 3. Under modulo 11 arithmetic, $25 \equiv 3$ so $$25^n \equiv 3^n$$ $$5 = 5$$

Therefore $$25^n \times 5 \equiv 3^n \times 5$$ $$121 \equiv 0$$ and $$11 \equiv 0$$

Therefore $$121^n \times 11 \equiv 0$$ (clearly it is divisible by 11)

$$289 \equiv 3$$ so $$289^n \equiv 3n$$ (289 is 3 more than a multiple of 11)

$$17 \equiv 6$$

Therefore $$289^n \times 17 \equiv 3^n \times 6$$

Under modulo 11 arithmetic, the expression is equal to: 

\begin{eqnarray}(3^n \times 5) + 0 + (3^n \times 6) &=&3^n \times 11 \\

&\equiv&3^n \times 0 \\ &=&0 \end{eqnarray} 

Therefore the expression is divisible by 11. As the expression is divisible by both 3 and 11, 3 and 11 are included among its prime factors (as both are prime numbers) and so the expression is divisible by $3 \times 11 = 33$. It is also possible to show that the expression is divisible by 33 by using modulo 33 arithmetic. Under modulo 33 arithmetic, $$25^n \times 5$$ remains the same. $$121^n \times 11 \equiv 22^n \times 11$$ $$289^n \times 17 \equiv 25^n \times 17$$

Under modulo 33 arithmetic, the expression is equal to:

\begin{eqnarray} (25^n \times 5) + (22^n \times 11) + (25^n \times 17) & =&(25^n \times 22) + (22^n \times 11) \\ &=& 11 \times [(25^n \times 2) + 22^n] \end{eqnarray}

If this last expression equals a multiple of 33, it is equal to 0. It is clearly divisible by 11, and so will be divisible by 33 if $[(25^n \times 2) + 22^n]$ is divisible by 3. Under modulo 3 arithmetic, $$25^n \equiv 1^n = 1$$ so $$(25^n \times 2) \equiv 1 \times 2 = 2$$ $$22^n \equiv 1^n = 1$$ Therefore $$[(25^n \times 2) + 22^n] \equiv 2 + 1 = 3 \equiv 0$$ Therefore $[(25^n \times 2) + 22^n]$ is divisible by 3.

Therefore the expression is divisible by 33.