Is it true that an $n^2 \equiv 0 \pmod 5 \Rightarrow 5 \vert n$?

Question

I want to use this as a lemma in a different proof, but I'm not sure if it holds. I would suspect it does, since: $n^2 \mod 5$ is in $\{0, 1, 4\}$ for all integers $n$, and only $0$ puts $0$ in this set, but I don't think this is enough to prove it. Can this be proved, or am I wrong?

Answer 1

$n^2 \equiv 0 \pmod p \implies p | n$ holds for all prime $p$ (so, yes, it does hold for your case of $p=5$).

It does not necessarily hold for composite $p$, e.g. consider $n^2 \equiv 0 \pmod 4$ and see if it's necessarily true that $4 | n$?

Answer 2

There are only 5 equivalence classes. Brute force will verify $n\equiv 0 \mod 5\iff n^2\equiv 0\mod 5$.

This is overkill, but if $p $ is prime, then of the $p $ equivalence classes $0 \mod p $ is the only divisor of zero[1] and so $n \times m\equiv 0$ only if either $n $ or $m \equiv 0 \mod p $. Therefore $n^k\equiv 0\iff n\equiv 0\mod p $.

So,yes, you can state that.

[1] $n \times m\equiv 0 \implies n \times m=kp\implies p|n \times m $ but as $p $ is prime either $p|n $ or $p|m $, i.e. either $n $ or $m \equiv 0 \mod p$.

Answer 3

Simple proof: by contrapositive.

Harder proof but still valid: using the Fundamental Theorem of Arithmetic

Forst is useful, second is kinda fun to work with

Answer 4

Euclid's Lemma:

If $p$, prime, divides $ab$, then $p|a$ or $p|b.$

Hence: $p|n^2$ $ \rightarrow$ $p|n.$

https://en.m.wikipedia.org/wiki/Euclid%27s_lemma