Dirisibly Yours
Problem
We wonder who can find and explain the shortest and neatest proof that
$5^{2n+1} + 11^{2n+1} + 17^{2n+1}$
is divisible by 33 for every non negative integer n .
Getting Started
Student Solutions
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)
Teachers' Resources
Why do this problem?
An exercise in proof by induction or, perhaps more simply, modulus arithmetic.Possible approach
The challenge in the question is to find the neatest and simplest proof. The class could take up this challenge, perhaps working in pairs. Then the class could discuss criteria for a good write-up of a proof and the teacher can add advice. Perhaps the class could then mark each others work say in groups of four.Key questions
How couldwe test that an expression is divisible by 33?What do we notice for small values of n?
What methods do we know for proving a result for all positive integers?