# Prove that $2^n + 5^n + 56$ is divisible by $9$, where $n$ is an odd integer

Prove that $$9 \mid2^n + 5^n + 56$$ where n is odd

I have proved this by using division into cases based on the value of $$n\bmod3$$ but it seems a little bit clumsy to me and I wonder if there are other ways to prove it, probably by using modular arithmetic or induction? Below is my proof:
$$\text{Case 1, }n\bmod3=0,\text{then n=3k for some odd integer k:}$$ \begin{align} 2^n+5^n+56 & =2^{3k}+5^{3k}+56 \\ & = 8^k+125^k+56 \\ & \equiv (-1)^k+(-1)^k+2\quad&\left(\bmod9\right) \\ & \equiv 0\quad&\left(\bmod9\right) \end{align}

$$\text{Case 2, }n\bmod3=1,\text{then n=3k+1 for some even integer k:}$$ \begin{align} 2^n+5^n+56 & =2^{3k+1}+5^{3k+1}+56 \\ & = 2\cdot8^k+5\cdot125^k+56 \\ & \equiv 2\cdot(-1)^k+5\cdot(-1)^k+2\quad&\left(\bmod9\right) \\ & \equiv 9\equiv0\quad&\left(\bmod9\right) \end{align}

$$\text{Case 3, }n\bmod3=2,\text{then n=3k+2 for some odd integer k:}$$ \begin{align} 2^n+5^n+56 & =2^{3k+2}+5^{3k+2}+56 \\ & = 4\cdot8^k+25\cdot125^k+56 \\ & \equiv 4\cdot(-1)^k+25\cdot(-1)^k+2\quad&\left(\bmod9\right) \\ & \equiv -27\equiv0\quad&\left(\bmod9\right) \end{align}

• To Dominic Peng: I am sure that Mathematical induction will do a job. Did you give a try? Commented Jul 25, 2021 at 9:22
• You may also write $2=3-1$ and $5=6-1$ and expand using binomial theorem. Then, note that the expression is $\equiv_9 (-1)^n\cdot 2+n\cdot 3(1+2)+56\equiv_9 2((-1)^n+1)\equiv_9 0$ for odd $n$ Commented Jul 25, 2021 at 9:34
• @Anton Vrdolijack Yeah I did...I attempted to show that $P_{k+1}-P_k$ is divisible by 9, that is, $2^{2k+3}+5^{2k+3}+56-2^{2k+1}-5^{2k+1}-56$ is divisible by 9 but after factoring out $2^{2k+1}$ and $5^{2k+1}$ I haven't got any progress yet. Commented Jul 25, 2021 at 9:49
• In case 3, why do you get $k$ is even? $4$ is congruent to 1 mod 3 but $4=3\cdot 1+1$
– Alan
Commented Jul 25, 2021 at 10:39
• To @Dominic Peng: I posted an answer which contains Mathematical induction approach. Commented Jul 25, 2021 at 10:43

Hint:  let \ \begin{align}n &= 2k\!+\!1\\ a&=(-2)^k\end{align}. $$\bmod 9\,$$ it's $$\:\!f(a)\equiv\, 2a^2\!+\!5a\!+\!2\,\equiv 2\,(a\!-\!1)^2\equiv 0\,$$ by $$\, 3\mid a\!-\!1\!\!$$

Or, conceptually $$\,a\equiv 1\,$$ is double root of $$\,f(a)\,$$ by $$\,f(1)\equiv 0\equiv f'(1)\,$$ by $$\,f'(a) \equiv 4a\!+\!5$$

• Note $\,3\mid a\!-\!1\,$ by $\!\bmod 3\!:\ a = (-2)^k\equiv 1^k\equiv 1\ \$ Commented Jul 25, 2021 at 11:37
• This one is very slick! +1; though I was wondering whether there's a general approach to enumerating all nontrivial positive integer solutions $(d,a,b,c,k)$ such that $d^k\mid a^n+b^n+c$ for (say) all odd positive integers $n$, when I was first looking at this problem. But seeing how most approaches are ad-hoc, I doubt there is a general procedure. Commented Jul 25, 2021 at 19:25

Here is a one-liner: $$2^{2k+1}+5^{2k+1}+56\equiv2(1+3)^k+5(1+24)^k-7\equiv2(1+3k)+5(1+24k)-7\equiv126k$$ where we used binomial theorem in middle step.

• When you repeat a proof given an hour prior in a comment you should cite the comment. Commented Jul 25, 2021 at 10:49
• @BillDubuque, The idea in that comment is similar, but it's not same. Commented Jul 25, 2021 at 12:01
• They are equivalent mod trivial algebra, i,e. use the first two terms of the Binomial Theorem, as often works for problems like this, e.g. see here. Commented Jul 25, 2021 at 12:10
• @BillDubuque, Every proof using binomial theorem isn't equivalent. I am expanding something else, he's expanding something else. Even the exponents of the expressions aren't same! Commented Jul 25, 2021 at 12:13
• Who said anything about "every proof"? This proof is equivalent. The only difference is that you expand after substituting $\,n = 2k+1.\$ In fact it;s simpler as in the comment. Commented Jul 25, 2021 at 12:19

It still involves cases, but here's a somewhat slicker proof.

By Euler's theorem, $$a^{\varphi(n)}\equiv 1$$ mod $$n$$, where $$\varphi$$ is Euler's totient function, which count the number of positive integers less than $$n$$ coprime to $$n$$.

As $$\varphi(9)=6$$, this implies that the residue of $$2^n+5^n+56$$ mod $$9$$ depends only on $$n$$ mod $$6$$. If we assume $$n$$ is odd, then the only possible residues are $$1,3,5$$. As such it is sufficient to verify the claim for $$n=1,3,5$$.

We can further reduce the number of calculations we have to do by noting that $$2$$ and $$5$$ are multiplicative inverses mod $$9$$. Then, as $$2^5\equiv 5$$, we must have $$5^5\equiv 2$$, so the $$n=5$$ case follows from the $$n=1$$ case. Similarly, as $$2^3\equiv -1$$, we have $$5^3\equiv -1$$, letting us easily verify the $$n=3$$ case.

Though it is arguably simpler to just directly verify these three cases

2 times complete induction only $$n\rightarrow n+1$$

$$2^n+5^n+56=9\cdot m\Rightarrow$$

$$2^{n+2}+5^{n+2}+56=4\cdot 2^n+25\cdot 5^n+56=3\cdot 2^n+24\cdot 5^n+2^n+5^n+56=3\cdot 2^n+24\cdot 5^n+9\cdot m$$

$$3\cdot 2^n+24\cdot 5^n+9\cdot m=3(2^n+8\cdot 5^n)+9\cdot m$$

$$2^n+8\cdot 5^n=3\cdot x$$, because $$2^{n+1}+8\cdot 5^{n+1}=2^n+8\cdot 5^n+2^n+8\cdot 5^n+3\cdot 8\cdot 5^n=2\cdot 3x+3y$$

Here's one way (not sure if it is the easiest, though).

Let us start with a lemma which you may easily prove by induction.

Lemma: For each natural number $$k$$, $$2^{2k+1}+1$$ and $$2^{2k}-1$$ are divisible by $$3$$.

Next, we have the following

Claim: For $$n=2k+1$$, one has $$2^n+5^n+56\equiv-2(2^{2k+1}+1)(2^{2k}-1)\mod 9.$$

In fact, $$2^n+5^n+56\equiv 2^{2k+1}+(-2^2)^{2k+1}+2\equiv 2(2^{2k}-2\cdot 2^{4k}+1) \mod 9.$$ Observe that the RHS is equal to the RHS of the claim.

By the lemma, the RHS of the claim is divisible by $$3\cdot 3=9$$, hence the LHS as well.

• Hi Zuy, thanks for your answer. I can prove the lemma now but could you explain further on how to derive the last congruence? Commented Jul 25, 2021 at 10:01
• @DominicPeng You may use that $5\equiv -2^2\mod 9$.
– Zuy
Commented Jul 25, 2021 at 10:03
• Could the downvoter share their reason, please?
– Zuy
Commented Jul 25, 2021 at 10:35
• Maybe it has to do with you claimed congruence after "we have...". More details would likely help there. Commented Jul 25, 2021 at 11:11
• I hope that the edits made my thoughts clearer.
– Zuy
Commented Jul 25, 2021 at 11:27

Write $$a_n=2^n + 5^n + 56\cdot1^n$$ and write $$(x-2)(x-5)(x-1)=0$$ as $$x^3=8 x^2 - 17 x + 10$$. Then $$a_{n+3} = 8 a_{n+2} -17 a_{n+1}+ 10 a_n$$ Then $$a_n \bmod 9$$ is $$4,0,4,0,\color{red}{4,0,4},\dots$$ Because of the linear recurrence, the sequence repeats as soon as it repeats three consecutive terms, $$4,0,4$$ in this case.

Bottom line $$a_n \equiv 0 \bmod 9$$ iff $$n \equiv 1 \bmod 2$$.

Mathematical induction approach

We know that $$n$$ is an odd integer, i.e. we can use $$n= 2k - 1, k \in \mathbb{N}$$. Hence, we can reformulate a starting statement:

$$9 \mid 2^{2k-1} + 5^{2k-1} + 56, \quad k \in \mathbb{N}.$$

$$\text{1.}$$ Basis of Induction:

For $$\ k=1 \$$ we have: $$\ 2^1 + 5^1 + 56 = 63 = 9 \cdot 7, \$$ i.e. the statement is true for $$\ k=1$$.

$$\text{2.}$$ Induction Hypothesis:

Suppose the statement holds for some $$\ k>1, \$$i.e. that it holds: $$\ 2^{2k-1} + 5^{2k-1} + 56 = 9 \cdot m, \ m \in \mathbb{N}.$$

$$\text{3.}$$ The proof:

Let's check if the statement holds for $$\ k+1. \$$ We have:

$$2^{2(k+1)-1} + 5^{2(k+1)-1}+56 = 2^{2k+2-1} + 5^{2k+2-1}+56=4\cdot 2^{2k-1} + 25 \cdot 5^{2k-1} + 56 = \\ 4\cdot (2^{2k-1}+5^{2k-1}+56) + 21\cdot 5^{2k-1} - 168 = 4\cdot 9 \cdot m + 21 \cdot (5^{2k-1} - 8).$$

The first summand on the right side (i.e. $$\ 4\cdot 9 \cdot m$$) is obviously divisible by $$\ 9, \$$ and because we know $$\ 21 = 3 \cdot 7, \$$ it remains to prove that it holds: $$\ 3 \mid 5^{2k-1} - 8, \ k \in \mathbb{N}.$$ For that purpose we will use a mathematical induction too!

I wanted to offer a different approach, using a bit of algebra.

\begin{align}2^n+5^n+56 &\equiv \\ &\equiv2^n+5^n+54+2\\ &\equiv 2^n+5^n+2\\ &\equiv 10^n-1+2^{2n}+2\times 2^n+1\\ &\equiv2^{2n}+2\times 2^n+1\\ &\equiv \left(2^n+1\right)^2\\ &\equiv 0\thinspace \thinspace \thinspace(\text{mod 9}) \end{align}

Because, \begin{align}2^n+1\equiv 0 \thinspace \thinspace \thinspace (\text{mod 3})\end{align}

where, $$~n\equiv 1 \thinspace \thinspace \thinspace (\text{mod 2}).$$