4
$\begingroup$

Let $N=pq$ where $p$ and $q$ are primes of the form $4k+1$. Let $\mathbb{Z}_N$ be the set of integers modulo $N$ and $\mathbb{Z}_N^*$ be the units in $\mathbb{Z}_N$. Let $QR$ be the quadratic residues in $\mathbb{Z}_N^*$. If none of $p$ and $q$ is $5$, then show that $\mathbb{Z}_N=\{a-b: a, b \in QR\}$. That is, we need to show that $\mathbb{Z}_N$ can be expressed as difference of quadratic residues.

Actually I observed that for N being product of two primes, apart from 3 and 5, Z_N can always be represented as difference of its set of quadratic residues. I tried to prove it but I failed. That's why I asked it here.

Initially I started with primes of the form 4k+1 as -1 is a quadratic residue there. However, nothing seems to work out.

$\endgroup$
1

2 Answers 2

3
$\begingroup$

For any prime $p$, and any nonzero residue $x\in(\mathbb{Z}/p\mathbb{Z})^\times$, the equation $a^2-b^2=x$ has $p-1$ solutions in $\mathbb{Z}/p\mathbb{Z}$, hence at least $p-5$ solutions in $(\mathbb{Z}/p\mathbb{Z})^\times$. It follows that, for $p>5$, any residue modulo $p$ is the difference of two quadratic residues modulo $p$. By the Chinese Remainder Theorem, it follows that if $N$ is the product of distinct primes exceeding $5$, any residue modulo $N$ is the difference of two quadratic residues modulo $N$ (i.e. two squares of units modulo $N$).

$\endgroup$
3
$\begingroup$

In any ring where $2$ is invertible, every element is the difference of two squares, namely $a=(a+4^{-1})^2-(a-4^{-1})^2$.

EDIT: I missed that the squares are supposed to be units. If $N$ is odd, the Chinese remainder theorem and Hensel’s lifting show that the property holds in $\mathbb Z/N\mathbb Z$ iff it holds in $\mathbb Z/p\mathbb Z$ for all prime divisors $p\mid N$. The identity above shows that an element $a$ of $\mathbb Z/p\mathbb Z$ is a difference of nonzero squares if we can find $b\ne0$ such that $ab^2\ne\pm4^{-1}$; the latter is always possible unless the only quadratic residues are $\pm1$, i.e., $p=3,5$. Since the property also fails for $2$, we see that every element of $\mathbb Z/N\mathbb Z$ is a difference of two square units iff $N$ is not divisible by 2, 3, or 5.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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