1. ## Modular arithmetic problem

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.

2. Originally Posted by spoon737
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,
$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:
$n^3\equiv n(\mbox{ mod } 2)$ (1)
$n^3\equiv n(\mbox{ mod } 3)$ (2)
The first congruence is true because consider cases when $n$ is even or odd. It is true in both of them.
The second congruence is true by Fermat's little theorem.

$n^3 \equiv n \text{ (mod 6)}$

$n^3 - n \equiv 0 \text{ (mod 6)}$

$n(n^2 - 1) \equiv 0 \text{ (mod 6)}$

$n(n + 1)(n - 1) \equiv 0 \text{ (mod 6)}$

So $n \equiv -1, 0 , 1 \equiv 0, 1, 5 \text{ (mod 6)}$

Why isn't this producing all the solutions?

-Dan

4. Originally Posted by topsquark

Why isn't this producing all the solutions?
Because of the property of Zero divisors..

In general when you have a ring of multiplication mudolu $n>1$, $\mathbb{Z}_n$ there shall always be zero divisros unless $n$ is prime.

5. Originally Posted by ThePerfectHacker
Because of the property of Zero divisors..

In general when you have a ring of multiplication mudolu $n>1$, $\mathbb{Z}_n$ there shall always be zero divisros unless $n$ is prime.
Gotcha. The missing solutions are -2, 2, and 3 which are all divisors of 6.

-Dan