6

How can I show that $$3^{2n}-1 \equiv 0 \pmod 8$$ is true?

What kind of method should I approach this problem with? I was thinking induction but but chapter isn't about induction so need some help...

Fourierstudent
  • 91

8 Answers8

6

$$3^{2n}-1=9^n-1=(8+1)^n-1$$

Using binomial theorem: $$=\sum_{r=0}^n\dbinom nr8^r-1$$

Cancelling: $$=\sum_{r=1}^n\dbinom nr8^r$$

Factor: $$=8\sum_{r=0}^{n-1}\dbinom n{r+1}8^r$$

QED.

Kenny Lau
  • 25,049
  • 1
    I think using $$(8+1)^n -1 $$ will give 1-1 = 0 is enough. Since that's how my book proved another similar exercise.. So thanks for your first line helped me :) thanks! – Fourierstudent May 07 '16 at 14:12
  • No problem, just treat the rest as a proof of why it is enough. – Kenny Lau May 07 '16 at 14:16
4

Observe $3^{2n} - 1 = (3^n - 1)(3^n + 1)$.

Since $3^n$ is odd, both its predecessor and successor are even; in particular, $(3^n - 1)$ and $(3^n + 1)$ are consecutive even numbers. Moreover, note that among any pair of consecutive even numbers, one of them is a multiple of $4$, whence the product is a multiple of $8$ as desired. QED.

Benjamin Dickman
  • 14,451
4

I assume you mean to show $$3^{2n} - 1 \equiv 0 \mod8$$

A proof (without induction):

$$3^{2n} - 1\equiv 9^n - 1 \equiv 1^n - 1 \equiv 0 \mod 8$$

A proof with induction:

The result is trivial for $n = 1$. Assume the result holds for $n=k \in \mathbb N$ (i.e. $3^{2k} - 1 = 8m,\, m\in \mathbb N$). Then for $n = k+1$ we have:

$$3^{2k + 2} - 1 = 9\times3^{2k} - 1 = 9(8m+1) - 1 = 72m +8 = 8(9m + 1)$$

And so the result is true for all natural $n \geq 1$.

KoA
  • 1,379
0

Hint One of two consecutive even number divide by 4, and another divide by 2.

openspace
  • 6,470
0

Let$$3^{2n}-1=8k\implies 3^{2n}=8k+1\implies n=\frac{\log_3(8k+1)}{2}\tag{1.}$$ Let $8k+1=3^a$ where $a$ is an integer.Let the smallest integer $b$ such that $8(k+c)+1=3^a\times 3^b\implies 3^a+8c=3^a\times 3^b\implies c=\frac{3^a(3^b-1)}{8}\tag{2.}$ Now put the integer values starting from $0$ for $b$ in eq. (2) .On putting $b=2$ we get multiple of $8$
So it has been proved that if $$8k+1=3^a $$ then adding some integer to $k$ on L.H.S. can make it to the power of $3$ for $3^a\times 3^2$(Not smaller than that)
So from eq.(1) for n to be an integer $k$ should be such that $8k+1$ becomes in the power of $3$. We have one such $k=1$ i.e. $8k+1=9$ the next number we get is $9\times 3^2$ ,next $9 \times 3^2 \times 3^2$ and so on.....(not smaller than that)
Now the expression for $$n=\frac{\log_33^{2t}}{2}\implies n=t$$ for $t\ge 1 \,,t\in \mathbb{N}$

Mayank Deora
  • 1,436
  • This question is wonderful .As we can see from the answers there are many methods to solve, one of which has been shown by me. – Mayank Deora May 07 '16 at 17:27
0

A couple of simple steps show this, using modular arithmetic only in one occasion, distributing modulo under exponentiation:

\begin{align} 3^{2n} - 1 & \equiv 9^n - 1 & \mod 8 \\ 9^n - 1 & \equiv (9 \bmod 8)^n - 1 & \mod 8 \\ (9 \bmod 8)^n - 1 & \equiv 1^n - 1 & \mod 8 \\ 1^n - 1 & \equiv 0 & \mod 8 \end{align}

orlp
  • 10,508
0

Here is a beginners solution

If we prove $3^{2n} = 1\mod 8$ It should do

So

$3^{2n} = 9^{n}$

$ 9^n = (8 +1)^n = 8^n +8^{n-1}*1 + ......1^n$

So all the terms except the last one will be a multiple of 8

So the remainder will always be $1^n$

We conclude

$3^{2n} = 1\mod 8$

$3^{2n} -1 = 0 \mod 8$

sidt36
  • 261
0

Observe that, $$3^2\equiv 1\pmod 8$$Consequently, $$3^{2n}\equiv 1\pmod 8$$