What does this congruent proof actually say?

Question

I have a statement that says:

For every $n >= 2$.

If n is an odd number then $7^{n}-1$ is not divisible by 4

Prove whether the statement is true or false.

The proof:

$7\cong -1 (mod 4)$ so $7^n-1\cong (-1)^n-1\cong -1(mod 4)$ and thus 4 does not divide $7^n-1$

I can't find any good explanations on the net.

The most I know from congruency is that a $\cong b(mod (n)))$ if n divides $a - b$.

Answer 1

You are on the right track.

$$7\equiv -1 \pmod4$$ $$7^n\equiv (-1)^n \pmod4$$ And for odd $n$, we have $$7^n\equiv -1 \pmod4$$ $$7^n -1\equiv -1-1\pmod4$$ $$7^n -1\equiv -2\not \equiv 0\pmod4$$

So the given statement is true.

Answer 2

You might find the following proof easier to follow

$\qquad \begin{align}{\rm mod}\ 4\!:\,\ 7^{\,\large 1+2K} &=\, \color{#0a0}7\cdot \color{#c00}{49}^{\large K}\\ &\equiv\, \color{#0a0}3\cdot \color{#c00}1^{\large K}\\ &\equiv\, 3\end{align}\!\!$ by $\ \begin{align} \color{#0a0}{7\equiv 3}\\ \color{#c00}{49\equiv 1} \end{align}$

The quoted proof is the same except it deduces $\,\color{#c00}{7^{\large 2}\equiv 1}\,$ by squaring $\,7\equiv -1$.

Above we used standard Congruence Rules (the Product and Power Rules)

Answer 3

You know $a \equiv b \mod n$ means $n$ divides $a-b$. (Notation: I will write $n|k$ to mean "$n$ divide $k$).

There are a few basic facts to know about this that in a very short time you will take for granted that most people won't even bother to state them and just assume they are obvious.

1) $a \equiv b \mod n \iff n|a-b \iff a = b + kn$ for some integer $m$ $\iff $ $a$ and $b$ have the same remainder when divide by $n$. All four of those statements mean the exact same thing. (It's easy to prove this and it makes a good excercise.)

2) $a \equiv 0 \mod n \iff n|a$

3) if $a\equiv r \mod n$ and $0 \le r < n$ then $r$ is the remainder when you divide $a$ by $n$.

Those are so basic that I imagine must mathematicians will just assume they are obvious and go without saying.

Not so obvious but still basic.

4) If $a \equiv b \mod n$ and $c \equiv d \mod n$ then $a+c \equiv b + d \mod n$ and $ac \equiv bd \mod n$ and $a^k \equiv b^k \mod n$

Pf: $a \equiv b \mod n \implies a = b + kn$ for some integer $k$. Likewise $c \equiv d \implies $c = d + jn$ for some $j$. So $a + c = b + d + n(k+j)$. $k+j$ is an integer so $a+c \equiv b+d \mod n$.

$ac = (b+kn)(d+jn) = bd + kdn + jbn + jkn^2 = bd + n(kd + jb + jkn)$. $kd + jb + jkn$ is and integer so $ac \equiv bd \mod n$.

$a \equiv b \mod n$ so $a^2 = a*a \equiv b*a \equiv b*b = b^2 \mod n$. Repeat inductively. $a^k \equiv b^k \mod n$.

Okay, with all that in mind.

$4$ divides $7^n - 1 \iff$

$7^n -1 \equiv 0 \mod 4 \iff$

$7^n \equiv 1 \mod 4$.

As $7 = -1 + 2*4$ we know $7 \equiv -1 \mod 4$.

So $7^n \equiv (-1)^n \mod 4$. If $n $ is odd then $(-1)^n = -1$.

So $7^n \equiv (-1)^n = -1\mod 4$.

And as $1 - (-1) = 2$ and $4$ does not divide $2$, $-1 \not \equiv 1 \mod 4$

So $4$ does not divide $7^n - 1$.

If that seems a little to abstract or obtuse....

Note this hinged on $7 = (2*4) - 1$.

Then $7^n - 1 = (8 - 1)^n - 1$

Note: $(8 - 1)^n = \sum_{i = 0}^n {n \choose i}8^i(-1)^{n-i}$.

Note each of the ${n\choose i}8^i(-1)^{n-i}$ where $i \ge 1$ are divisible by 8 and therefore divisible by $4$.

So the remainder of dividing $(8-1)^n$ by $4$ will be the one term where $i=0$. So the remainder will by ${n \choose 0}8^0(-1)^{n-0} = (-1)^n$ and as $n$ is odd, the remainder is $-1$. Oh... actually it is $3$, I guess, (see what I said about assuming things are so obvious they go without saying?)

So the remainder of dividing $(8-1)^n - 1$ will be $3 -1 = 2$. So $4$ does not divide $7^n -1$ for $n$ odd.

(Note: if $n$ is even and $n > 0$ the $4$ will always divide $7^n - 1$.