# Quadratic Congruence modulo square-free integer

If $$m$$ is a square-free integer, show that $$x^{2} + y^{2} \equiv k\pmod{m}$$ has a solution $$\forall k\in\mathbb{N}$$. This means that we need to prove existence of such $$m$$ for all $$k\in\mathbb{N}$$.

So far I've got this:

Prime decomposition of each square-free integer has exactly one factor for each prime in it. Therefore $$m= p_1...p_v$$.

Suppose that $$k=a+b$$ for some $$a,b \in \mathbb{N}$$, then $$x^2 \equiv a \ \pmod{m}$$, $$y^2 \equiv b\pmod{m}$$ would imply $$x^2 + y^2 \equiv k\pmod{m}$$.

Using Chinese remainder theorem $$x^{2} \equiv a \pmod{m}$$ requires

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

...

$$x^2 \equiv a \pmod{p_v}$$,

$$y^2 \equiv b \pmod{p_1}$$

...

$$y^2 \equiv b \pmod{p_v}$$,

Therefore we nedd to show that $$\forall a,b \in \mathbb{N}$$ we can find primes $$p_{1},...,p_{v}$$ which satisfy the above mentioned congruences.

I would appreciate an advice or a hind, because I'm not sure whether this is the right path to the solution.

• You can't do it this way. For many $a$, $x^2\equiv a\pmod p$ is not soluble. But $x^2+y^2\equiv k\pmod p$ is always soluble. – Angina Seng Apr 11 '19 at 8:22

For $$p_i>2$$ not every residue is a quadratic residue, so the congruences $$x^2\equiv a\pmod{p_i}\qquad\text{ and }\qquad y^2\equiv b\pmod{p_i},$$ do not admit solutions for all integers $$a$$ and $$b$$ with $$k=a+b$$.
Also, after applying the Chinese remainder theorem you seem to get confused: The question is not to find primes $$p_1,\ldots,p_n$$ such that the congruences hold. You are given $$m=p_1\cdot\ldots\cdot p_n$$ and must show that there exist $$a$$ and $$b$$ with $$k=a+b$$ such that the congruences hold. But unfortunately finding such $$a$$ and $$b$$ explicitly for all $$k$$ and $$m$$ is not practically doable.
Edit: Upon reading again, this confusion already starts on the very first line; you do not need to prove existence of $$m$$ for all $$k$$, you need to prove existence of $$x$$ and $$y$$ for all $$k$$ and $$m$$.
Your idea to use the Chinese remainder theorem is a good start though; you can use this to reduce the problem to showing that for every prime number $$p$$ the congruence $$x^2+y^2\equiv k\pmod{p},$$ has a solution for all $$k\in\Bbb{N}$$. This problem has been posed and answered on this site before.