How can you prove 52n+1+112n+1+172n+1 is divisible by 33 for all non-negative integer value of n ?

Welcome our bloge

Here is an exercise in:

• obtaining new result(s) from old result(s) on the cheap
• problem-solving
• seeing connections between things that are not explicitly there

---

First, computationally the machinery of modular arithmetic offers an economic proof requested: since the prime factorization of 33$33$ amounts to 3⋅11$3\cdot 11$, we consider two cases. Namely, modulo 3$3$ and modulo 11$11$ residues.

All three base numbers of 5,11$5,11$ and 17$17$ are congruent to 2$2$ modulo 3$3$:

5≡2(mod3)$\begin{array}{}& 5\equiv 2(\mathrm{mod}3)\end{array}$

11≡2(mod3)$\begin{array}{}& 11\equiv 2(\mathrm{mod}3)\end{array}$

17≡2(mod3)$\begin{array}{}& 17\equiv 2(\mathrm{mod}3)\end{array}$

Due to the basic properties of modular arithmetic, we know that if two integers a$a$ and b$b$ are congruent modulo m$m$, that is if a≡b(modm)$a\equiv b(\mathrm{mod}m)$, then so are their respective positive powers, that is ak≡bk(modm)$a^k\equiv b^k(\mathrm{mod}m)$ for any positive integer k$k$. Therefore, it will be the case that:

52n+1≡22n+1(mod3)$\begin{array}{}& 5^{2n+1}\equiv 2^{2n+1}(\mathrm{mod}3)\end{array}$

112n+1≡22n+1(mod3)$\begin{array}{}& {11}^{2n+1}\equiv 2^{2n+1}(\mathrm{mod}3)\end{array}$

172n+1≡22n+1(mod3)$\begin{array}{}& {17}^{2n+1}\equiv 2^{2n+1}(\mathrm{mod}3)\end{array}$

By the similar basic properties of modular arithmetic, we know that we can add the above relations without ill effects:

52n+1+112n+1+172n+1≡3⋅22n+1(mod3)$\begin{array}{}& 5^{2n+1}+{11}^{2n+1}+{17}^{2n+1}\equiv 3\cdot 2^{2n+1}(\mathrm{mod}3)\end{array}$

which is to say that:

52n+1+112n+1+172n+1≡0(mod3)(1)$\begin{array}{}\text{(1)}& 5^{2n+1}+{11}^{2n+1}+{17}^{2n+1}\equiv 0(\mathrm{mod}3)\end{array}$

Likewise, because it is the case that:

15≡4(mod11)$\begin{array}{}& 15\equiv 4(\mathrm{mod}11)\end{array}$

subtracting 10$10$ from both sides of the above relation, we find:

5≡−6(mod11)$\begin{array}{}& 5\equiv -6(\mathrm{mod}11)\end{array}$

It is evident that 11≡0(mod11)$11\equiv 0(\mathrm{mod}11)$ and that 17≡6(mod11)$17\equiv 6(\mathrm{mod}11)$. Hence:

52n+1≡(−1)⋅62n+1(mod11)$\begin{array}{}& 5^{2n+1}\equiv (-1)\cdot 6^{2n+1}(\mathrm{mod}11)\end{array}$

112n+1≡0(mod11)$\begin{array}{}& {11}^{2n+1}\equiv 0(\mathrm{mod}11)\end{array}$

172n+1≡62n+1(mod11)$\begin{array}{}& {17}^{2n+1}\equiv 6^{2n+1}(\mathrm{mod}11)\end{array}$

Adding the last three results together and observing that the odd powers of 6$6$ cancel out:

52n+1+112n+1+172n+1≡0(mod11)(2)$\begin{array}{}\text{(2)}& 5^{2n+1}+{11}^{2n+1}+{17}^{2n+1}\equiv 0(\mathrm{mod}11)\end{array}$

we conclude that 11$11$ also always divides the number requested.

Thus, the combination of (1) and (2) tells us that 33$33$ divides the number requested for all non negative numbers n$n$.

---

An alternative proof of the statement at hand is based on the idea that we have discussed not so long ago where we proved that for a natural number n$n$ the number n(n+1)(n+2)(n+3)+1$n(n+1)(n+2)(n+3)+1$ is always a perfect square via the introduction of an object equidistant from the given factors - their arithmetic mean.

In this, no doubt carefully crafted, problem, however, the arithmetic mean of the three base numbers is one of the main characters, number 11$11$ that is:

5+11+173=11$\begin{array}{}& {\displaystyle \frac{5+11+17}{3}}=11\end{array}$

For one* tactical leverage of this idea we represent the peripheral two numbers via the arithmetic mean at hand:

5=11−6$\begin{array}{}& 5=11-6\end{array}$

17=11+6$\begin{array}{}& 17=11+6\end{array}$

noting that both 5$5$ and 17$17$ are equidistant from 11$11$.

Next, we observe that like molecules in a chemical reaction, the two summands a$a$ and b$b$ in their binomial expansion bond almost all the way through:

(a+b)5=a5+5a4b+10a3b2+10a2b3+5ab4+b5$\begin{array}{}& (a+b{)}^5=a^5+5a^{4}b+10a^3{b}^2+10a^2{b}^3+5a{b}^4+b^5\end{array}$

Almost because the molecules of an$a^n$ and bn$b^n$ hang out all by themselves. In a sample binomial expansion above we used n=5$n=5$ for demonstration purposes only - we do not inhale any significance into the concrete power of 5$5$.

Now, when we binomially expand (11–6)$(11–6)$:

(11−6)2n+1=∑k=02n+1(nk)112n+1−k(−1)k6k(3)$\begin{array}{}\text{(3)}& {\displaystyle (11-6{)}^{2n+1}=\sum _{k=0}^{2n+1}(\genfrac{}{}{0ex}{}{n}{k}){11}^{2n+1-k}(-1{)}^k{6}^k}\end{array}$

and when we binomially expand (11+6)$(11+6)$:

(11+6)2n+1=∑k=02n+1(nk)112n+1−k6k(4)$\begin{array}{}\text{(4)}& {\displaystyle (11+6{)}^{2n+1}=\sum _{k=0}^{2n+1}(\genfrac{}{}{0ex}{}{n}{k}){11}^{2n+1-k}{6}^k}\end{array}$

we see that because 11$11$ is almost omnipresent on the RHSs of the expansions in (3) and (4), each of these expansions, term by term, will be divisible by 11$11$ except, perhaps, for the last term. Here the role of the summand a$a$ is played by the natural number 11$11$ that bonds to −6$-6$ which is a concrete image of b$b$.

Luckily, however, because the final power of 6$6$ is odd, these last odd powers of 6$6$ will again cancel out after we add the expansions (3) and (4) together.

Note how we exercise the symmetry of the arrangement.

Adding one more copy of 112n+1${11}^{2n+1}$ to the above sum will not ruin the divisibility of the whole by 11$11$ - it will remain intact.

By the same token, because 6$6$ factorizes as 2⋅3$2\cdot 3$ and because 6$6$ will be almost omnipresent on the RHSs of the expansions in (3) and (4), each of these expansions, term by term, will be divisible by 3$3$ except, perhaps, for the first term of 112n+1${11}^{2n+1}$.

But taken in sum, so as to form the number requested, we will have exactly three copies of 112n+1${11}^{2n+1}$, implying that the said number will also be always divisible by 3$3$.

Thus, since we have shown that the positive integer 52n+1+112n+1+172n+1$5^{2n+1}+{11}^{2n+1}+{17}^{2n+1}$ is divisible by both 11$11$ and 3$3$, it follows that the said number is divisible by 33$33$ for all non negative integers n$n$.

---

This, as is evident from the answers given, is the point at which all the participants drop the problem on the floor cold turkey.

*We, however, go further by re-representing, intuitively speaking, our numbers around 3$3$:

5=3+2$\begin{array}{}& 5=3+2\end{array}$

11=3+23$\begin{array}{}& 11=3+2^3\end{array}$

17=3+2⋅7$\begin{array}{}& 17=3+2\cdot 7\end{array}$

If we go through the same motions of binomially expanding the above summands then due to the observations already made above, we will conclude that all the terms in the said expansions will be divisible by 3$3$ except, perhaps, for the last ones.

But we are asked to take the sum of the above three expansions. Hence, the only (and all the) divisible-by-three suspects will be bunched up as follows:

22n+1+26n+3+22n+172n+1$\begin{array}{}& 2^{2n+1}+2^{6n+3}+2^{2n+1}{7}^{2n+1}\end{array}$

Factoring out the single copy of 22n+1$2^{2n+1}$ from the formation above, we will have:

22n+1⋅(1+42n+1+72n+1)$\begin{array}{}& 2^{2n+1}\cdot (1+4^{2n+1}+7^{2n+1})\end{array}$

Now, on the one hand, we already proved that the above number must be divisible by 3$3$ by other means that kill circular reasoning. On the other hand, by the corresponding theorem framed by Euclid many years ago, 3$3$, being prime, must divide either of the above factors or both.

But 2$2$ and 3$3$ are coprime. Hence, no positive power of 2$2$ is divisible by 3$3$. But 3$3$ must divide one of the said factors - the only such factor is the number given by:

1+42n+1+72n+1(5)$\begin{array}{}\text{(5)}& 1+4^{2n+1}+7^{2n+1}\end{array}$

We, thus, conclude that for all non negative numbers n$n$ the number 3$3$ divides 1+42n+1+72n+1$1+4^{2n+1}+7^{2n+1}$. That is a new result the we obtained on the cheap and to which we were alluding to earlier.

Is that it?

Nope. We also see that the number in (5) must necessarily be even, 12$12$ being the smallest specimen - thus, and that is another, perhaps weaker, result: the number in (5) is divisible by 2$2$ for all non negative numbers n$n$.

But in aggregation it also means that the number in (5) is divisible by 6$6$ - yet another result obtained on the cheap.

---

Just for kicks, before posting this answer, I, on the whim and without hope of any kind, decided to search Quora for exactly that problem. And what do you know?

Lo and behold, that exact question was already asked on Quora in November of 2014 and was answered by 12$12$ participants, no less.

What I am about to say next, I mean with complete respect, with no hidden sarcasm and no hidden agenda of any kind except for an educational one.

To be sure, please do not misconstrue what follows for criticism - for it is not.

We learn now that the two problems are actually connected - if we generate a proof of the current problem then, with a minimal effort in curiosity, we have a proof for the second problem. That connection, however, is extremely difficult to see, especially in vacuum, especially due to the peculiarity of the beast that the theory of numbers is - that is why the said connection is absent from the 12$12$ answers given to the linked to question.

In conclusion, the grand finale that we were building this answer up to is the following. If, when and as you solve tons and tons of technical problems in various vaguely defined layers of mathematics (and theoretical physics and computer science, I will lump these ones in here too) then chances are that you might start seeing deeper and more abstract similarities and connections between such problems.

The next time that you take on a technical problem, you might avoid a brute force, forehead on, as they say in Russian, attack by finding a connection or a similarity with a previously solved, related or otherwise, problem and generate a proof/solution that will be qualified as elegant or beautiful by others.

To a side observer such a solution may look nothing short of magic.

But now we now that behind the, sometimes flawless, elegance at the microphone there sits the ugly truth of the author’s blood, sweat and tears.