Prove, for positive integers n, that 7 divides 6^n + 1 if and only if n is odd.?

Question

I'm doing modular arithmetic and can't figure this out!!

Answer 1

Let's use arithmetic mod 7.
Note that 6 = -1(mod 7).
So we want to know:
When is (-1)^n +1 = 0(mod 7)?
That requires -1^n = -1(mod 7)
which happens if and only if n is odd.

Answer 2

base case:
n=1
6^1 + 1 = 7
7 divides 7

assume true for n=k s.t. 7 divides 6^k + 1 for odd k

prove true for n = k + 2 (k+1 is even)

6^(k+2) + 1
= 6^2 * 6^k + (-35 + 36)
= 36 * 6^k + (-35 + 36)
= 36 (6^k + -35/36 + 1)
= 36 (6^k + 1) + 36(-35/36)
= 36 (6^k + 1) - 35

Since 6^k + 1 is divisible by 7 (by the hypothesis), so is 36 * (6^k + 1).

Also -35 is divisible by 7.

The sum of two numbers divisible by 7 is also divisible by 7.

Therefore, proven by mathematical induction, 7 divides 6^n + 1 for all positive odd integers.

Answer 3

Write S(n) = a million^ok + 2^ok + ...+ n^ok. be conscious that because of the fact a million, 2, ...n. is an entire gadget of residues mod n, then so is -a million, -2, ..., -n. Then 2S(n) = S(n) + S(-n) = 0 mod n (=0 because of the fact ok is unusual). Now evaluate S(n+a million) mod n+a million = S(n) mod n+a million. making use of the comparable good judgment as above 2S(n) = 2S(n+a million) = 0 mod n+a million. because of the fact n and n+a million are rather top then 2S(n) = 0 mod n(n+a million), ie, n(n+a million)/2 divides S(n).