Solving a second degree congruence relation

Question

Suppose $n = pq$ where $p$ and $q$ are distinct odd primes. Let $r$ be an integer such that $r \equiv p^{-1} \pmod q$, and put $s = 1 − 2rp$. Let a be an integer such that $(a, n) = 1$.Show that the solutions modulo n to the congruence $$x^2 ≡ a^2 \pmod n$$ are precisely $x \equiv ±a \pmod n$ and $x \equiv ±as \pmod n$

My attempt:
From $r \equiv p^{-1} \pmod q$, we get that $rp \equiv 1 \pmod q$
so $rp = 1 + qk$ for some $k$
$s = 1 - 2(1+qk) = -1 -2qk$
$s \equiv -1 \pmod q$

I'm kinda stuck now. Any help would be appreciated.

Hint: $x^2\equiv a^2\pmod n$ if and only if both $x^2\equiv a^2\pmod p$ and $x^2\equiv a^2\pmod q$ (by the Chinese remainder theorem). — Greg Martin, Mar 18 '15 at 04:15
No: if $s\equiv-1\pmod q$, then there's no way $s$ can be congruent to $1$ modulo a multiple of $q$. — Greg Martin, Mar 18 '15 at 05:38

score 1 · Accepted Answer · answered Mar 18 '15 at 04:53

HINT

So far you have $$s\equiv -1 \pmod{q} \implies \color{blue}{s^2\equiv 1 \pmod{q}}\tag{1}$$

Also $$s=1-2rp \implies s\equiv 1 \pmod{p}\implies \color{blue}{s^2\equiv 1 \pmod{p}}\tag{2}$$

Since $p$ and $q$ are primes, from $(1)$ and $(2)$ :
$ q|(s^2-1)$ and $p|(s^2-1) \iff pq|(s^2-1)$ so $$\color{blue}{s^2\equiv 1 \pmod{pq}}$$

Multiply $a^2$ both sides and conclude!

Solving a second degree congruence relation

1 Answers1