Looking for a simpler solution about quadratic congruence [duplicate]

Here is the Problem:

1)Suppose $p$ is a prime. prove that for any integer $k$, there exist integers $x$ and $y$ such that $x^2+y^2 \equiv k\ \pmod p$.

2)Are there infinitely many composite numbers that have the property of 1?

Which doesn't seem complicated, but it took me quite long to solve it. Still, my solution is not simple enough.

Here is my solution:

1)Without loss of generality, we assume $0\leq k \leq p-1$

It is quite obvious that when $(\frac{k}{p})=1$, we can find $x,y$, where one of them is $0$.

If there is actually some $k$ that we can't find $x,y$ accordingly. Let us assume $k$ has the minimum value. We claim that $k$ has the properties as follows:

a). $k$ is actually a prime. Otherwise, we have $k = k_1k_2$, however:

$$ k_1 \equiv x_1^2+y_1^2\ (modp)\\ k_2 \equiv x_2^2+y_2^2\ (modp) $$ then: $$ k\equiv k_1k_2 \equiv (x_1^2+y_1^2)(x_2^2+y_2^2) \equiv (x_1x_2+y_1y_2)^2+(x_1y_2-x_2y_1)^2\ (modp) $$

b). $k\equiv 3\ (mod4)$ if $k\equiv 1\ (mod4)$, then there exist $x,y$ such that $x^2+y^2 = k$, which satisfy $x^2+y^2 \equiv k\ (modp)$

Now consider the sequence$\{(4l+2)p+k\}(l=1,2...)$. On the one hand, we have$(4l+2)p+k \equiv 1\ (mod4)$, on the other hand $(4l+2)p+k = 4p\times l+2p+k$, but $gcd(4p, 2p+k) = 1$. Applying Dirihlet's Theorem. We can say that there exists $l_1$ That $(4l_1+2)p+k$ is a prime. So it can be written as sum of two squres, which is a contradiction.

2).Let us consider a prime $p$, where $p\equiv 1(mod4)$. We can prove $p^2$ has the property of 1.

Firstly. We can prove that k has the property in the similar way we prove 1),where $gcd(p,k) = 1$.

What's more. If $k = k'\times p$,$gcd(k',p) = 1$:

Applying 1), we know there exists $s_1,t_1$ such that $s_1^2+t_1^2 = pm+k'$ Also, it is known that there exists $s_2,t_2$ that $p = s_2^2+t_2^2$($p\equiv 1(mod4)$). By multiplying them, we have $(s_1s_2+t_1t_2)^2+(s_1t_2-s_2t_1)^2 \equiv k'p\ (modp^2)$.

The solution looks fine to me. But I meet up with this problem in a book where nothing about the quadratic congruence is mentioned. Not to mention Dirihlet's Theorem. So I doubt there is a simpler solution.

I have another Idea, which seems promising. But it didn't finally lead to a solution.

Specifically, we can multiple both sides of the congruence with $(x^{-1})^2$, then we have $(x^{-1}y)^2\equiv (x^{-1})^2 \times k -1 (modp)$. As is known to all, we have $\frac{p-1}{2}$ numbers within $\{1,2,...,p-1\}$ which are not quadratic residues to $p$. if there is a $k$ such that the claim in 1) doesn't stand. Let $x^{-1}$ pass through the complete set of residues of $p$ we can see that none of the $RHS$ of the equation is quadratic residue to $p$. But not any two of them are congruent to each other(mod p).,So we have $RHS$ to be exactly the set of numbers which are not quadratic residues to $p$.

I hoped the idea mentioned above can lead to the solution of the problem. But I failed going on.

Hope somebody can give me some other solutions which at least don't need Dirihlet's Theorem.

Solution 1:

Here's my idea: taking into account zero (or $\;0\pmod p\;$ , if you prefer), there are $\;\frac{p+1}2\;$ quadratic residues modulo $\;p\;$ , and now define for $\;k\in\Bbb Z/p\Bbb Z\;$ fixed:

$$T:=\left\{\,x^2\;:\;x\in\Bbb Z/p\Bbb Z\,\right\}\;,\;\;S_k:=\left\{\,k-x^2\;:\;x\in\Bbb Z/p\Bbb Z\,\right\}$$

and observe that again $\;|S_k|=\frac{p+1}2\;$ , of course. From here that

$$|T\cup S_k|>p\implies \exists\,z\in T\cap S_k$$

and we've finished to prove.