4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In the second congruency statement, you forgot the ≡ right? $\endgroup$ – Mif Ano Apr 23 '17 at 13:07
  • $\begingroup$ Yes i did, i corrected it. $\endgroup$ – Ziad Fakhoury Apr 23 '17 at 13:10
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can the downvoter please elaborate on why my answer is being downvoted? I'd like to learn from my mistakes. $\endgroup$ – vrugtehagel Apr 23 '17 at 12:48
  • $\begingroup$ You meant that n=2k+1 right? $\endgroup$ – Mif Ano Apr 23 '17 at 13:08
  • $\begingroup$ Yes, thank you for your correction $\endgroup$ – vrugtehagel Apr 23 '17 at 19:01
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.