# Prove that for all positive integers $n, 9|(11^ n − 2 ^n )$

Prove that for all positive integers $n, 9|(11^n − 2^n )$

So the base case would be

9 * k = (11*1 - 2 * 1)
9 * k = 9
k = 1 so yes


The inductive hypothesis would be the fact that $(11^n-2^n)$ is divisible by $9,$

So I thought then I would have to show that $(11^{(n+1)}-2^{(n+1)})$ is divisible by$9$

11^(n+1) - 2^(n+1)
11^(n) * 11^1 - 2^n * 2^1
(11-2) * (11^n-2^n)
9*(11^n-2^n)


Is this algebraically correct?

• Under "the inductive hypothesis" it should be "is divisible by" May 8, 2014 at 15:25
• 11^(n+1) - 2^(n+1) ---- 11^(n) * 11^1 - 2^n * 2 ---- (11-2) * (11^n-2^n) ---- 9*(11^n-2^n) May 8, 2014 at 15:31
• In the comment this is very hard to read. You should be able to edit it into your post (there should be a gray edit below the post) or post an answer to the question. It is explicitly permitted to answer your own question. This looks like an answer to me. May 8, 2014 at 15:33

HINT:

$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+... +y^{n-1})$

• Or, in congruence language $\ {\rm mod}\ x\!-\!y\!:\ x\equiv y\,\Rightarrow\,x^n\equiv y^n,\,$ cf. my answer. May 8, 2014 at 16:16
• @BillDubuque I know that, thanks, just wanted to put it another way. May 8, 2014 at 16:17

Hint: Can you factor $x^n-y^n$?

Hint $\$ Suppose that $\ \color{#c00}{11^n = 2^n\! + 9k}.\$ Then

$\qquad \begin{eqnarray} 11^{n+1}&=\,&\quad 11\cdot \color{#c00}{11^n}\\ &=& (2\!+\!9)(\color{#c00}{2^n\!+9k})\\ &=&\quad 2^{n+1}\! + 9(\cdots)\end{eqnarray}$

which yields the induction step.

Remark $\$ Essentially it is congruence multiplication, i.e.

$\qquad {\rm mod}\ 9\!:\,\ 11\equiv 2,\ 11^n\equiv 2^n \,\Rightarrow\, 11^{n+1}\equiv 2^{n+1}$

a special case of using the $\$ Congruence Product Rule $\ \ A\equiv a,\ B\equiv b\,\Rightarrow\, AB\equiv ab\$ in order to inductively prove the sought Congruence Power Rule. $\ A\equiv a\,\Rightarrow\, A^n\equiv a^n,\,$

A quicker/non-inductive method is as $11 \equiv 2 \mod 9$, for all integers $n \geq 1$, $11^n \equiv 2^n \mod 9$, so $11^n - 2^n \equiv 0 \mod 9$ and hence $11^n - 2^n$ is divisible by $9$.

Hint: $11^{n+1} - 2^{n+1} = 11(11^{n}-2^{n}) +2^{n}(11-2).$

Hint: $$11^{n+1}-2^{n+1}=11\cdot11^n-2\cdot2^n=$$ $$=9\cdot11^n+2\cdot11^n-2\cdot2^n=2(11^{n}-2^{n})+9\cdot11^n$$ First part is true from assumption and second part has 9 as a factor

• As explained in my answer, this is a special case of the proof of the Congruence Product Rule, namely May 8, 2014 at 16:48
• $\begin{eqnarray} \\ \color{#0a0}{A-a\equiv 0}, &&\ \color{#c00}{B-b}&\color{#c00}\equiv& \color{#c00}0 &\,\Rightarrow\,& AB\ -\ ab &=\,& a(\color{#c00}{B\ -\ b}) &+& (\color{#0a0}{A-\,b})B &=\,& 0\\ \color{#0a0}{11-2\equiv 0}, && \color{#c00}{11^n\!-2^n}&\color{#c00}\equiv&\color{#c00} 0 &\,\Rightarrow\,& 11^{n+1}\!-2^{n+1}\! &=\,& 2(\color{#c00}{11^n-2^n})\! &+& (\color{#0a0}{11-2})11^n &\equiv\,& 0_{\phantom{I_I}} \\ \end{eqnarray}\qquad\qquad\qquad$ Note that the prior equality is precisely the same equality that you derived May 8, 2014 at 16:49
• I just gave a very elementary hint that helps to solve the problem posed. I agree that your solution is much more general, I do not know so much about congruence product rule. May 8, 2014 at 17:05

One of numerous possible approaches using Binomial theorem

$$11^n -2^n=(10+1)^n -\sum_{j=0}^{n}\binom{n}{j} =\\ \sum_{j=0}^{n}\binom{n}{j}10^{n-j}-\sum_{j=0}^{n}\binom{n}{j} \\ =\sum_{j=0}^{n}\binom{n}{j}\left(10^{n-j}-1 \right) \equiv 0\,(mod\,9)$$

The identity $$x^k-y^k=(x-y)\left(\sum_{j=0}^{n-1}x^{n-1-j}y^j\right) \,\, \forall k \in \mathbb{Z}^{+}$$ has been used