# Mathematical Induction divisibility $8\mid 3^{2n}-1$

So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ ,

$$8|(3^{2n} - 1)$$

(is divisible by 8)

I have my base case: [P(1)], $3^2 - 1 = 9 - 1 = 8$, since $8|8$, the base case proves true

Assume [P(k)], $8 | (3^{2k} - 1)$.

I know that I need to show [P(k+1)], $8| (3^{2(k+1)}-1)$, but I'm not sure how to prove this. I've only been using induction for summation, so how could I prove divisibility?

• Try factoring out $3^2=8+1$. – Matt Samuel Nov 10 '14 at 1:51
• Note also that $3^{2n}-1=(3^2)^n-1=9^n-1$. Now the claim follows from $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\cdots+b^{n-1})$. – Kim Jong Un Nov 10 '14 at 2:54
• @Integrator it's correct though the identity in my comment is more elementary than the binomial theorem. – Kim Jong Un Nov 10 '14 at 8:03

If you don't mind I'm gonna do some magic $$3^{2n}=(3^2)^n=(8+1)^n=\binom{n}{o}8^n+\binom{n}{1}8^{n-1}+\cdots+\binom{n}{n-1}8^{1}+\binom{n}{n}8^0$$

$$3^{2n}=\binom{n}{0}8^n+\binom{n}{1}8^{n-1}+\cdots+\binom{n}{n-1}8^{1}+1$$

$$3^{2n}-1=\binom{n}{0}8^n+\binom{n}{1}8^{n-1}+\cdots+\binom{n}{n-1}8=8(k)$$

$$\implies8|(3^{2n} - 1)$$

Hint: Note that: $$3^{2(n+1)} -1=9\cdot3^{2n}-1=(3^{2n}-1)+8\cdot3^{2n}$$

• How did you factor 9*3^(2n) -1 to equal (3^(2n) - 1)+ 8*3^(n)? (the last part) I don't understand how you were able to set them equal – Mark Nov 10 '14 at 2:03
• $3^{2(n+1)} - 1 = 3^{2n+2} - 1 = 3^{2n}\cdot3^{2} - 1 = 9\cdot 3^{2n} - 1$ $= (8+1)\cdot 3^{2n} - 1 = 8\cdot 3^{2n} + 1\cdot 3^{2n} - 1 = (3^{2n}-1) + 8\cdot 3^{2n}$ – JMoravitz Nov 10 '14 at 3:26
• so i can make deduction that we assumed that 8|P(k) is true and so 8| 8*3^(2*n) so P(n) is true? – talmudist Oct 25 '15 at 19:01
• @talmudist Assumed that $8|P(k)$ is true and show that $8| [P(k+1)=(3^{2k}-1)+8\cdot3^{2k}]=P(k)+8\cdot3^{2k}$ is true, then P(n) is true? – AsdrubalBeltran Oct 25 '15 at 21:43
• from the question , yes – talmudist Oct 25 '15 at 22:00

Here is an alternative approach to that given by AsdrubalBeltran.

Write $3^{2n}-1$ is base three notations as :

$$3^{2n}-1 = \underbrace{22\dots2_{base 3}}_{2n \text{ times}}$$

Then since $8 = 22_3$, we can see the result at once. Now use induction on n.