Prove that if $7$ divides $6^n + 1$ then $n$ is odd

Question

Attempt:

We'll prove the contrapositive: $n$ is not odd if $7$ does not divide $6^n + 1$

Just to note: You have written the inverse, not the contrapositive. The contrapositive would be "If $n$ is not odd, then $7$ does not divide $6^n + 1$." — Owen Biesel, Dec 12 '13 at 09:30
Similar to http://math.stackexchange.com/questions/584686/prove-using-mathematical-induction-that-23n-1-is-divisible-by-7 but different. — lhf, Dec 12 '13 at 09:54

score 8 · Answer 1 · answered Dec 12 '13 at 08:55

8

If $x+1$ divides $x^n+1$ then $-1$ is a root of $x^n+1$. Therefore $(-1)^n+1=0$ which is only possible if $n$ is odd. Now put $x=6$.

answered Dec 12 '13 at 08:55

pritam

score 4 · Answer 2 · answered Dec 12 '13 at 08:56

4

Try to look at...:

$$(7-1)^n+1$$

answered Dec 12 '13 at 08:56

Salech Alhasov

lab bhattacharjee · Answer 3 · 2013-12-12T11:24:18.640

1

As $6\equiv-1\pmod7$

$\implies 6^{2m+1}\equiv(-1)^{2m+1}\equiv-1$

and $6^{2m}\equiv(-1)^{2m}\equiv1$

edited Dec 12 '13 at 11:24

answered Dec 12 '13 at 08:52

lab bhattacharjee

1

This proves that if $n$ is odd, then $7 | 6^n + 1$. It doesn't prove that if $n$ is not odd, $7 \not | 6^n + 1$, although it could by the same mechanism. – DanielV Dec 12 '13 at 10:35
@DanielV, please find the edited version – lab bhattacharjee Dec 12 '13 at 11:24

score 1 · Answer 4 · answered Dec 12 '13 at 10:33

1

$$6^{2k} + 1 \equiv 36^k + 1 \equiv 1^k + 1 \equiv 2 \not \equiv 0 \pmod 7$$

answered Dec 12 '13 at 10:33

DanielV

score 1 · Answer 5 · answered Dec 12 '13 at 10:56

1

More generally, $a-b\mid a^n-b^n$ for all $n\in\mathbb N$, $a,b\in\mathbb Z$. As a consequence, $a+b\mid a^n+b^n$ if $n$ is odd.

answered Dec 12 '13 at 10:56

Hagen von Eitzen

5 Answers5