I'm a little out of practice when it comes to modular arithmetic, so this problem is giving me some trouble. I need to show that for every integer n, (n^3) mod 6 = n mod 6.
It is standard to write,
$\displaystyle n^3\equiv n (\mbox{ mod }6)$
Note, the we can factor 6 as 2 times 3.
Where 2 and 3 are relatively prime.
Thus, it is equivalent to saying the system of congruences is satisfied:
$\displaystyle n^3\equiv n(\mbox{ mod } 2)$ (1)
$\displaystyle n^3\equiv n(\mbox{ mod } 3)$ (2)
The first congruence is true because consider cases when $\displaystyle n$ is even or odd. It is true in both of them.
The second congruence is true by Fermat's little theorem.
A question about this:
$\displaystyle n^3 \equiv n \text{ (mod 6)}$
$\displaystyle n^3 - n \equiv 0 \text{ (mod 6)}$
$\displaystyle n(n^2 - 1) \equiv 0 \text{ (mod 6)}$
$\displaystyle n(n + 1)(n - 1) \equiv 0 \text{ (mod 6)}$
So $\displaystyle n \equiv -1, 0 , 1 \equiv 0, 1, 5 \text{ (mod 6)}$
Why isn't this producing all the solutions?
-Dan
Because of the property of Zero divisors..
In general when you have a ring of multiplication mudolu $\displaystyle n>1$, $\displaystyle \mathbb{Z}_n$ there shall always be zero divisros unless $\displaystyle n$ is prime.