Modulus Arithmetic and a solution to Dirisibly Yours
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.