Connection between quadratic residue of a number to its factors'

439 Views Asked by At

Is it true that, If $N$ is product of two coprime numbers greater than 1. Quadratic residues of these numbers are quadratic residue of $N$ and vice versa? Can someone point me to a proof or show me if this is not the case.

In other words, if we start with $n = pq$, where $p, q$ are coprimes. If and only if $x^2 \equiv a \mod n$, then $a \equiv x^2 \mod p$ and $a \equiv x^2 \mod q$

2

There are 2 best solutions below

0
On BEST ANSWER

We state a precise version of the result you are after.

Let $m$ and $n$ be relatively prime. Then $a$ is a quadratic residue of $mn$ if and only if $a$ is a quadratic residue of $m$ and $a$ is a quadratic residue of $n$.

One direction is easy. Suppose that $a$ is a quadratic residue of $mn$. Then there exists a integer $x$ such that $x^2\equiv a\pmod{mn}$. It follows that $x^2\equiv a\pmod{m}$ and $x^2\equiv a\pmod{n}$, and therefore $a$ is a quadratic residue of $m$ and a quadratic residue of $n$.

The converse is a little more complicated. Suppose that $a$ is a quadratic residue of $m$ and a quadratic residue of $n$. Then there is a $b$ such that $b^2\equiv a\pmod{n}$, and a $c$ such that $c^2\equiv a\pmod{n}$.

By the Chinese Remainder Theorem, there is an $x$ such that $x\equiv b\pmod{m}$ and $x\equiv c\pmod{n}$.

We have $x^2\equiv b^2\equiv a\pmod{m}$ and $x^2\equiv c^2\equiv a\pmod{n}$. It follows that $x^2\equiv a\pmod{mn}$, and therefore $a$ is a quadratic residue of $mn$.

0
On

If $a\equiv x^2\pmod{pq}$ then $pq|(a-x^2)$ so $p|(a-x^2)$ and $q|(a-x^2)$.