You may also like

problem icon

Purr-fection

What is the smallest perfect square that ends with the four digits 9009?

problem icon

Old Nuts

In turn 4 people throw away three nuts from a pile and hide a quarter of the remainder finally leaving a multiple of 4 nuts. How many nuts were at the start?

problem icon

Mod 7

Find the remainder when 3^{2001} is divided by 7.

Dirisibly Yours

Stage: 5 Challenge Level: Challenge Level:1

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)

because $p$is odd, and $5^p + 11^p + 17^p \equiv 2^p + 2^p + 2^p \equiv 3 x 2^p \equiv 0$ (mod 3).

For more discussion of solutions to this problem see the article.