1
$\begingroup$

I wanted to know how many solutions the quadratic equation:

$$x^2 \equiv a \pmod N$$

had when $N$ is a composite of the form $N = pq$. It is not too hard to show that when $N$ is prime, there are either exactly 2 solutions or no solutions. But I wasn't sure how to show extend this composites of the form $N = pq$.

My intuition tells me that one can show that there are exactly 4 solutions using a corollary of the Chinese remainder theorem. In fact, the following corollary:

If $n_1, n_2, ..., n_k$ are pairwise relatively prime and $n = n_1n_2...n_k$ then for all integers $x$ and $a$,

$$ x \equiv a \pmod {n_i}$$

for $i=1,2,...,k$ if and only if

$$ x \equiv a \pmod n$$

So it seems that if we have the equation:

$$ x^2 \equiv a \pmod {pq} $$

then it implies the following:

$$x^2 - a = k(pq) \implies p \mid x^2 - a \text{ AND } q \mid x^2 - a $$

$$ \iff x^2 \equiv a \pmod {p} \text{ AND } x^2 \equiv a \pmod {q}$$

Since $x^2 \equiv a \pmod {p} \text{ AND } x^2 \equiv a \pmod {q}$ are true, and in turn each has a pair of numbers $x,-x$ that satisfies each one of these two equation, which results in total of 4 different $x$'s that satisfies the first equation. For this logic to work we need the corollary of the Chinese reminder theorem to be true though.

Is this correct? Does it mean the quadratic equation has exactly 4 solutions when $N=pq$? (if I had to guess, when $N = pqt$, there are 6 solutions using a similar logic). Ideally, I'd like to know why my proof is wrong and how to correct it and get a correct proof.

$\endgroup$
  • 1
    $\begingroup$ If $p$ and $q$ are distinct odd primes, there are $4$ or none. If $p,q,t$ are distinct odd primes there are $8$ or none. And so on. The proof uses the Chinese Remainder Theorem. $\endgroup$ – André Nicolas Dec 14 '15 at 0:36
  • $\begingroup$ @WillJagy What do you mean "cheap answer". Not sure what that sentence is suppose to mean. $(\alpha, \beta )$ suppose to be the square roots of $a$ mod p or q? Sorry if these are easy questions. Since I'm still trying to figure out this theorem (i.e. how many solns to quadratic equation mod composites) there are still things that might be obvious to you but aren't for me (yet). $\endgroup$ – Charlie Parker Dec 14 '15 at 0:49
  • $\begingroup$ @AndréNicolas can you explain what the proof is that if $p$ and $q$ are distinct odd primes, there are either 4 or no solutions? $\endgroup$ – ALannister Nov 6 '16 at 5:37
1
$\begingroup$

of the $pq$ residue classes in $\mathbb{Z}/pq\mathbb{Z}$ there are $\frac{(p+1)(q+1)}4$ squares, of which $0$ occurs once, $\frac{p+q}2-1$ occur twice, and $\frac{(p-1)(q-1)}4$ occur four times, these latter being the squares in the group of residues relatively prime to both $p$ and $q$.

for example with $p=3$ and $q=5$ we have $$ 0^2=0 $$ then $$ 9 \equiv_{15} 3^2 \equiv_{15} 12^2 \\ 10 \equiv_{15} 5^2 \equiv_{15} 10^2 \\ 6 \equiv_{15} 6^2 \equiv_{15} 9^2 $$ and finally $$ 1 \equiv_{15} 1^2\equiv_{15} 4^2 \equiv_{15} 11^2 \equiv_{15} 14^2 \\ 4 \equiv_{15} 2^2\equiv_{15} 7^2 \equiv_{15} 8^2 \equiv_{15} 13^2 \\ $$

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