Why does $n^2 \equiv 10 \pmod{30}$ imply $n \equiv 0 \pmod{10}$?

Question

It seems that $n^2 \equiv 10 \pmod{30} \iff n \equiv 0 \pmod{10}$. I found this by calculating $\{n \in \mathbb N_0 \mid n < 30 \land n^2 \equiv 10 \pmod{30}\} = \{10, 20\}$, and noting that 10 divides both of the numbers in the resulting set.

Can this be proven without testing all integers modulu n or can it even be generalized? (Or, if is this all not even true: Where is my mistake?)

A bit of context: This question arose while solving Project Euler Problem #146. Since the numbers $n^2+1$, $n^2+3$, $n^2+7$, $n^2+9$ and $n^2+13$ which must be prime for $n$ to be considered further, form a prime quadruplet, there must be a $k$ such that $n^2+1 = 30k + 11$.

Answer 1

Note: In your title, you ask why $n^2 \equiv 10 \pmod{30}$ implies $n \equiv 0 \pmod{10}$. My answer is a response to that statement. In your question itself there is a different statement, that $n^2 \equiv 10 \pmod{30}$ if and only if $n \equiv 0 \pmod{10}$; this is false, and I assume it is an error.

---

Why does $n^2 \equiv 10 \pmod{30} \implies n \equiv 0 \pmod{10}$?

This is true and can be generalized. In fact, it is a result of two simpler implications $$ n^2 \equiv 10 \pmod{30} \implies n^2 \equiv 0 \pmod{10} \implies n \equiv 0 \pmod{10} $$ The first implication is true because $10 | 30$. The second implication is true because $10$ is squarefree, i.e., it is a product of distinct primes.

More details on the second implication: write $10 = 2 \cdot 5$, so $n^2 \equiv 0 \pmod{10}$ if and only if $n^2$ is a multiple of $2$ and a multiple of $5$. But since $2$ is prime, for $n^2$ to be a multiple of $2$, it must be that $n$ itself contains a factor of $2$. Same for $5$. So $n$ is divisible by $2$ and $5$, hence $n \equiv 0 \pmod{10}$.

Answer 2

We know that $n^2\equiv 0\mod 2$ and that $n^2\equiv 0\mod 5$. Because $2$ and $5$ aren't squares, the only solutions to these equations are $n\equiv 0\mod2$ and $n\equiv 0\mod 5$. Combining this yields $n\equiv 0\mod 10$.

Answer 3

Hint $\ \, 10\mid 30\mid n^2-10\,\Rightarrow\, 10\mid n^2\,\Rightarrow\,10\mid n,\,$ because $\,q\mid n^2\,\Rightarrow\,q\mid n\,$ for squarefree $\,q,\,$ since for each prime $\ p_i\mid q\,\ $ we have $\ p_i\mid n^2\,\Rightarrow\ p_i\mid n,\,$ thus $\ q = {\rm lcm}\,\{\,p_i\,\} \mid n.$

Remark $\ $ The above property is $(3)$ in the below equivalent characterizations of $\,q\,$ squarefree.

Theorem $\ $ Let $\rm\ 0 \ne q\in \mathbb Z\:.\ \ $ The following are equivalent.

$(1)\rm\quad\ \ \ \, n^2\,|\ q\ \ \Rightarrow\ \ n\ |\ 1\qquad\ $ for all $\rm\:\ n\in \mathbb Z $

$(2)\rm\quad\ \ \ \, n^2\, |\, qm^2 \!\Rightarrow n\ |\ m\qquad\! $ for all $\rm\: \ n,m\in \mathbb Z$

$(3)\rm\qquad\ q\ |\ n^2\ \Rightarrow\ q\ |\ n\qquad\ $ for all $\rm\:\ n\in \mathbb Z $

$(4)\rm\qquad\ q\ |\ n^k\ \Rightarrow\ q\ |\ n\qquad\ $ for all $\rm\:\ n\in \mathbb Z,\ k\in \mathbb N $

$(5)\rm\quad\:\ \: q^q\ |\ n^n\ \Rightarrow\ q\ |\ n\qquad\ $ for all $\rm\:\ n\in \mathbb N,\ $ for $\rm\ q > 0 $

Proof $\ \: (1\Rightarrow 2)\rm\:\ \ $ Canceling $\rm\:(n,m)^2\:$ from LHS of $(2)\:$ we may assume w.l.o.g. that $\rm\:(n,m)\:=\:1.\ $ By $ $ Euclid's Lemma $\rm\: n^2\, |\, qm^2\: \Rightarrow\ n^2\: |\: q\ \Rightarrow\ n\:|\:1\ \Rightarrow\ n\:|\:m$

$(2\Rightarrow 3)\rm\quad q\ |\ n^2\ \Rightarrow\ q^2\ |\ qn^2\ \Rightarrow\ q\ |\ n $

$(3\Rightarrow 4)\rm\quad k \ge 2\ \Rightarrow\ k \le 2\:(k-1)\ $ so $\rm\:\ q\ |\ n^k\ |\ (n^{k-1})^2\ \Rightarrow\ q\ |\ n^{k-1}\:\ldots\:\Rightarrow\ q\ |\ n$

$(4\Rightarrow 5)\rm\quad q\ |\ q^q\ |\ n^n\ \Rightarrow\ q\ |\ n $

$(5\Rightarrow 1)\:$ via $\:\lnot\: 1\Rightarrow\lnot\: 5.\ $ By $\rm\:\lnot 1,\,\ q\: =\: ab^2,\:\ b\nmid 1.\:$ Put $\rm\ n = abc\:$ for $\rm\:c\:$ as below.

$\rm\qquad\ \ \ q\ |\ (ab)^2\ \Rightarrow\ q^{\:q}\ |\ (ab)^{2\:q}\ |\ (abc)^{abc}\! = n^n\quad\ \ for\ all \:\ c\:\ with\ \ abc > 2\:q $

Since $\rm\ b\nmid 1\ \Rightarrow\ q\nmid ab,\:$ we may choose $\rm\:c\:$ so that also $\rm\ q\nmid abc,\ $ e.g. $\rm\:\ c\equiv 1\,\ (mod\ q)$