Copyright © University of Cambridge. All rights reserved.
This is the problem called
Dirisibly Yours :
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$.
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.