For all positive integers, n, if $3^n \equiv 1 \mod 8$, then n is even.

Question

I've had trouble trying to prove this statement. I have been at it for 4 hours, but I don't feel like the proof I produced is right. And since this is a simple question, I think I am missing some big point. I hope you guys can share some tips or feedback.

Here's the solution I've come up with so far. I am sure there is a more elegant way. I was also thinking of maybe assuming n is odd and finding a contradiction or come to a false conslusion using P.M.I. (math induction).

---

Let $n$ be a positive integer, then $n\geq1$. Suppose $3^n\equiv1 \pmod 8$. Then $8\mid 3^n-1$ and $3^n-1=8k$ for some integer $k$. Suppose $n$ is even, then $n=2v$ for some positive integer $v$. Then $$3^{2v}-1=8k=(3^2)^v-1=9^v-1,$$ which can be rewritten as $9^v-1=8k$. Now we need to prove that for every positive integer $v\geq 1$, $8\mid 9^v-1$ holds.

Let $P(v)$ denote the statement $8|9^v-1$. We shall prove, by mathematical induction that $\forall v\geq1:P(v)$. For $v=1$, $$P(1)\iff 8\mid9-1\iff 8\mid 8,$$ $8$ does indeed divide itself. Hence the basis premise $P(1)$ is true.

Now we shall work with the second step of this proof, which is the induction premise. Let $v$ be an integer, $v\geq 1$ and suppose that $P(v)$ is true. That is, suppose that $9^v-1=8m$ for some integer $m$ (induction hypothesis). It must be shown that $P(v+1)$ is true, that is $9^{v+1}-1=8p$ ($*$) for some integer $p$. Let’s expand ($*$). $9^{v+1}-1 = 9^v9^1$. But, by substitution from the induction hypothesis we can rewrite it as: $$(8m+1)9^1-1=72m+9-1=72m+8=8(9m+1)=8p$$ Thus, $P(v+1)$ is true for all $v\geq 1$.

Thus, from the basis step and the induction premise and with the help of P.M.I we can conclude that $P(v)$ is true for all $v\geq 1$. Therefore the congruence holds for all positive and even integers $n$.

---

Thanks in advance.

Answer 1

This is actually very simple and easy to prove.

Lets assume that it is true for $n$ odd in other words, if $n = 2k+1$ then

$$3^{2k+1} \equiv 1 \mod 8$$ Now note that the inverse for $3$ is $3$. $$3(3^2)^k \equiv 1 \mod 8$$ $$3^1 \equiv 1 \mod 8$$

Leading to a contradiction.

Answer 2

Note that $3^{n}-1 = (3-1)\sum_{k=0}^{n-1}3^{k}$; note that $n$ being odd implies $\sum_{k=0}^{n-1}3^{k}$ is the sum of an odd number, $n$, of odd numbers. So if $n$ is odd then $3^{n} - 1$ is not divisible by $8$; hence $n$ is even.

In plain language, the "logic" above is: prove that no counterexample to the proposition under consideration exists.

Answer 3

Here's a simpler way (using induction). Suppose that the statement is true for all $1\le k\le n-1$. Suppose that $3^n \equiv 1 \pmod 8$.

Note that $9\equiv 1\pmod 8$, so $3^n \equiv 9 \pmod 8$. As $\gcd(3,8) = 1$, we may "divide by $3$ both sides" twice to get $3^{n-2} \equiv 1 \pmod 8$. By the induction hypothesis, it follows that $n-2$ is even, $\therefore n$ is even.

Answer 4

An easy way to show $8\mid9^v-1$ is using geometric series: for $n\geq 1$,

$$1+9+9^2+9^3+\cdots+9^{n-1}=\frac{9^n-1}{9-1}$$

since the left-hand side is an integer, $9^n-1$ must be divisible by $8$.

---

That being said, we can also use the contrapositive of your statement to prove it:

if $n$ is odd (not even), then $3^n\not\equiv 1\mod 8$

If $n$ is odd, then $n=2k+1$ for some integer $k$, thus, $$3^n\equiv 3^{2k+1}\equiv 3\cdot9^k\equiv 3\cdot1^k\equiv3\not\equiv1\mod 8$$

proving the statement.

Answer 5

Here's another way.

$3^n \equiv 1 \mod 8$ means

$3^n - 1 \equiv 0 \mod 8$

$(3-1)(3^{n-1} + 3^{n-2} + ..... + 9 + 3 + 1) \equiv 0 \mod 8$

$2(3^{n-1} + 3^{n-2} + ..... + 9 + 3 + 1) = 8k$ for some $k$

$3^{n-1} + 3^{n-2} + ..... + 9 + 3 + 1 = 4k$ is even.

As $3^i$ is odd. There must be an even number terms. So $n$ is even.