0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Your implication is only true one way...if $n=30$ then $n^2 = 900$ which is not congruent to $10 \bmod 30$. However $n^2 \equiv 10 \bmod 30$ if and only if $n\equiv 0 \bmod 10$ AND $n \not\equiv 0 \bmod 3$. $\endgroup$ – fretty Feb 6 '14 at 22:05
4
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.