Ok so I've tried making this one work for a while and keep getting stuck. I have the following: Prove: ($x^2$ is congruent to $x\mod3$) $\iff$ ($x$ is not congruent to $2\mod3$).
So I know it is bi-conditional and needs both directions to be proven. In one direction, I took the contrapositive and said: If ($x$ is congruent to $2\mod3$), then ($x^2$ is not congruent to $x\mod3$).
So: $x=3k+2$ where $k$ is an integer.
then $x^2=9k^2+12k+4$
$(x^2)-x=9k^2+9k+2=3(3k^2+3k)+2.$
So I think, (not sure as I'm really new to this) that since we can't "factor completely" without a remainder of $2$, then we have no congruence and the original statement is correct. Now, making this go the other way is where I'm stuck because how do you manipulate this around if you can't work with just a single $x$ and thus just $x$'s congruence? Contradiction doesn't seem to work, and using contrapositive again only lets you assume $x^2$ is not congruent to $x\mod3$ and again, you can't work with just $x$. Again I'm pretty new to this but any help would be wonderful.
$\endgroup$ 01 Answer
$\begingroup$$\implies$ If $x \equiv 2 \mod 3$, then $2^2 = 4 \equiv 1 \mod 3$ and $x^2$ not congruent to $x$.
$\impliedby$ When $x \ncong 2 \mod 3$ the cases $0^2 \equiv 0 \mod 3$ and $1^2 \equiv 1\mod 3$ shows that $x^2 \equiv x \mod 3$.
Edit:
$\implies$ (Contrapositive). If $x \equiv 2 \mod 3$. Let $x = 2 + 3k$ for some $k$. Then $$x^2 = 4 + 12k + 9k^2 = 1 + 3(1 + 4k + 3k^2) = 1 + 3m$$ Therefore, $x^2 = 2^2 \equiv 1 \mod 3$ and $x^2$ is not congruent to $x$.
$\impliedby$ When $x \ncong 2 \mod 3$, we examine the two cases:
$0^2 \equiv 0 \mod 3$ since $x = 3k \implies x^2 = 3(3k^2) = 3m$ with $m = 3k^2$.
$1^2 \equiv 1\mod 3$ since $x=1 + 3k \implies x^2 = 1 + 6k + 9k^2 = 1 + 3m$ with $m = 2k+3k^2$.
Therefore, $x^2 \equiv x \mod 3$ holds when $x \ncong 2 \mod 3$.
$\endgroup$ 4
