Proof Verification: If $a\in \mathbb{Z}$, then $a^3≡a \pmod{3}$.

Question

So, I understand that congruence equation can be written as $a^3 -a = 3k$ ,$k\in \mathbb{Z}$. I also understand that this can be written as $a(a^2 - 1) = 3k$, which can be simplified further to show the multiplication of $3$ consecutive integers.

$(a-1)a(a+1) = 3k$

I'm just not sure where to go from here. Can anyone help?

Answer 1

$(a-1)a(a+1)$ is the product of $3$ consecutive numbers, hence at least one of them is a multiple of $3$.

Hence the product is a multiple of $3$ as well.

Remark: this is an example of Fermat's little theorem.

Answer 2

You may also proceed as follows by noting that it is enough to show

• $a^2 \equiv 1 \mod 3$ for $a \not \equiv 0 \mod 3$.
• For $a \equiv 1 \mod 3$ you are done.
• For $a \equiv 2 \mod 3$ you get $a^2 \equiv 4 \equiv 1 \mod 3$.

Answer 3

You simply need to realize that if you have $k$ consecutive integers one of them has to be divisible by $k$.

The proof is almost too trivial to bother with.

If your consecutive numbers are $m, m+1, m+2, m+3,...... , m+(k-1)$ and if $m \equiv i \pmod k$ then $m+1 \equiv i+1 \mod p$ and $m+2 \equiv i+2 \mod p$ and so on and then number $m + (k-i) \equiv i+(k-i) \equiv 0 \pmod k$.

(More generally, for any $j; 0 \le j < k-1$ then one of the consecutive integers is equivalent to $j \pmod k$.)

So if $(a-1), a, (a+1)$ are three consecutive numbers then one of them must be divisible by $3$.

So the product of all of them is divisible by $3$ so $(a-1)a(a+1) \equiv 0 \pmod 3$.

....

Another less elegant but more direct one would be to note that either $a \equiv 0 \pmod 3$ or $a \equiv 1 \pmod 3$ or $a \equiv 2 \equiv -1 \pmod 3$.

So either $a^3 \equiv 0^3 = 0\equiv a \pmod 3$ or $a^3 \equiv 1^3 =1 \equiv a\pmod 3$ or $a^3 \equiv 2^3 = 8\equiv 2 \equiv a \pmod 3$.

Those are the only three options.

....

Or if you really want a basic argument. Let $a = 3k +i$ for some $k$ and $i = 0, 1, $ or $2$.

Then $a^3 = (3k + i)^3 = 27k^3 + 27k^2i + 9ki^2 + i^3 \equiv i^3 \pmod 3$. And it's easy to verify $i^3 \equiv i \pmod 3$ if $i=0,1,2$.