Math Help - Proofs Involving Congruence of Integers

1. Proofs Involving Congruence of Integers

Course: Foundations of Higher Math

Let
$n\in Z$. If $n^2 \not \equiv n(mod3)$, then $n \not \equiv 0(mod3)$ and $n \not \equiv 1(mod3)$. State and prove the converse.

Converse: If $n \not \equiv 0(mod3)$ and $n \not \equiv 1(mod3)$, then $n^2 \not \equiv n(mod3)$.

It seems easier to prove by contrapositive so

Assume that $n^2 \equiv n(mod3)$, i.e. $n^2 - n = 3a$, for some integer a.

$\Rightarrow n(n-1)=3a \Rightarrow (n-0)(n-1)=3a$

So, $3|(n-0)$ or $3|(n-1)$.

Hence, $n \equiv 0(mod3)$ or $n \equiv 1(mod3)$

How's that?

2. Re: Proofs Involving Congruence of Integers

Looks good to me