0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Under "the inductive hypothesis" it should be "is divisible by" $\endgroup$ May 8, 2014 at 15:25
  • $\begingroup$ 11^(n+1) - 2^(n+1) ---- 11^(n) * 11^1 - 2^n * 2 ---- (11-2) * (11^n-2^n) ---- 9*(11^n-2^n) $\endgroup$
    – Gaurav
    May 8, 2014 at 15:31
  • 3
    $\begingroup$ 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. $\endgroup$ May 8, 2014 at 15:33

7 Answers 7

3
$\begingroup$

HINT:

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

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

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

$\endgroup$
2
$\begingroup$

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,\, $

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ As explained in my answer, this is a special case of the proof of the Congruence Product Rule, namely $\endgroup$ May 8, 2014 at 16:48
  • $\begingroup$ $\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 $\endgroup$ May 8, 2014 at 16:49
  • $\begingroup$ 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. $\endgroup$
    – Adi Dani
    May 8, 2014 at 17:05
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .