Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|cite|improve this question
Also posted to, without any notice at either site. How rude.… – Gerry Myerson Jun 14 '14 at 4:54

2 Answers 2

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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