bilarev wrote: Find the number of residues mod p of $(x^{2}+y^{2})^{2}$ I don't understand This problem has form beautifuly.

$x$ and $y$ runs over all residues mod $p$ except 0.

You not understand what I said Ok, problem said that: Find $0\leq r<p$ such that $(x^{2}+y^{2})^{2}=p\cdot q+r$, for some $q\in\mathbb{N}$?

Sorry for this inexactness ... I think that now it's clearer.

If p=2 all residues can be write in this way. If $x=y=0$, then $r=0$. If one of $x,y$ not equal 0, then $(x^{2}+y^{2})^{2}=x^{4}z^{2}\in Z_{p}^{2},z=1+t^{2}, t=y/x$. If $p=3(mod 4)$ all quadratic residue can be write in this way. Number of residius is (p+1)/2. If $p=1(mod 4)$ sufficiently consider z. If exist t, suth that $(\frac{1+t^{2}}{p})=-1$, then all quadratic residues can be write in these way, else only residues from $Z_{p}^{4}$. Because for all $p=1(mod 4)$ exist t, suth that $(\frac{1+t^{2}}{p})=-1$ all quadratic residues can be write in these way.

We need use following lemmas lemma 1. If $p=4k+3$ is prime and $\gcd (x,p)=\gcd (y,p)=1$ then $x^{2}+y^{2}\not \equiv 0\pmod{p}$. Proof. Trivial. lemma 2. If $p=4k+3$ is prime then there exists $x_{0},y_{0}\in\mathbb{N}$ such that $x_{0}^{2}+y_{0}^{2}+1\equiv 0\pmod{p}$ and $\gcd (x_{0},p)=\gcd (y_{0},p)=1$. Proof. Theorem 87 in Hardy and Wright. If $0\leq r<p$ such that for some $x,y$ :$\gcd (x,p)=\gcd (y,p)=1$ and $(x^{2}+y^{2})^{2}\equiv r\pmod{p}$ then by lemma 1, $r$ must is quadratic residue of $p$, therefore there at most $\frac{p-1}{2}$ of $r$. Now, by lemma 2 we have $(x_{0}^{2}+y_{0}^{2})^{2}\equiv 1\pmod{p}$ therefore $((p_{i}x_{0})^{2}+(p_{i}y_{0})^{2})^{2}\equiv q_{i}^{2}\pmod{p}$ for $i=1,2,...,\frac{p-1}{2}$ and $q_{1},q_{2},...,q_{\frac{p-1}{2}}$ are all quadratic residues and $q_{i}\equiv p_{i}^{2}\pmod{p}(i=1,2,...,\frac{p-1}{2}$), but numbers $q_{1}^{2},q_{2}^{2},...,q_{\frac{p-1}{2}}^{2}$ are all incongruent, we have at least $\frac{p-1}{2}$ of $r$. Final, answer $\frac{p-1}{2}$.

N.T.TUAN wrote: Final, answer $\frac{p-1}{2}$. Final answer $2$ if p=2, $\frac{p+1}{2}$ if p>2 ($0=(0^{2}+0^{2})^{2}$).

Rust: reading, thinking, posting!

Can you post a proof for lemma 2 N.T.TUAN? (I do not have that book:) Edit: Ok I have an idea but I am not sure: Let $r_{1},...r_{\frac{p-1}{2}}$ the quadratic residues. So there is enough to find a quadratic residue r such that $r+1$ is a nonquadratic residue. If we assume that this does not hold, then all the residues are quadratic, a contradiction

The $\frac{p+1}{2}$ numbers $x^{2}(x=0,1,...,\frac{p-1}{2}).$ are incongruent and so are the $\frac{p+1}{2}$ numbers $-1-y^{2}(y=0,1,...,\frac{p-1}{2}).$ But there $p+1$ numbers in the two sets together, therefore...

ciprian wrote: Can you post a proof for lemma 2 N.T.TUAN? (I do not have that book:) Edit: Ok I have an idea but I am not sure: Let $r_{1},...r_{\frac{p-1}{2}}$ the quadratic residues. So there is enough to find a quadratic residue r such that $r+1$ is a nonquadratic residue. If we assume that this does not hold, then all the residues are quadratic, a contradiction Sufficiently proof, that exist t, suth that $(\frac{1+t^{2}}{p})=-1$. If $(\frac{1+t^{2}}{p})\ge 0 \ \forall t$, then $r=1+(r-1)=1+1+(r-2)=...=1+1+...+1$ and $(\frac{r}{p})\ge 0 \ \forall r$. It give contadition for p>2.

Here's another solution, copied from here. The answer is $\frac{p-1}{2}$. Let $S$ be the set of residues $\pmod{p}$ ($0$ is not a residue here). I'll show that for each number $k \not\equiv 0 \pmod{p}$, either $k$ or $p-k$ is in $S+S$. (*) Since $p \equiv 3 \pmod{4}$, $0 \not\in S+S$. But by Cauchy-Davenport, $|S+S| \ge 2|S|-1 = p-2$. So $S+S$ can be missing at most one other element other than $0$. So if $k$ is missing, then $p-k$ can't be missing. So (*) is proven and the result trivially follows.

Obviously zero can't be represented as that would imply that $\left(\frac{-1}{p}\right)=1$ contradiction with the first condition.So let's show that all QR-s can be represented and this will kill it as this is obviously necessary. $p\equiv_4 3$ $\implies$ at least one of $\{a,-a\}$ is a QR and so it suffices to show that for every $z$ $x^2+y^2=z^2$ has non-trivial solution in $\mathbb{F}_p$.But we could just pick $(x,y)=\left(\frac{s-1}{s+1}\cdot z,\frac{2s}{s+1}\cdot z\right)$ for some $s\not =-1$ and we,re done.

I claim that all nonzero quadratic residues modulo $p$ work, hence there are $\frac{p-1}2$ solutions. For Fermat Christmas reasons, $p \mid x^2+y^2$ is impossible. On the other hand, it is clear that $r$ must be quadratic, so we show that all remaining QR's work. This is simply because as $p \equiv 3 \pmod 4$, one of $a$ and $-a$ is a NQR mod $p$ by multiplicativity. Hence for each $a$, there exists a pair $(x, y)$ such that among the two equations \begin{align*} x^2+y^2 &\equiv a \\ x^2+y^2 &\equiv -a \end{align*}one has at least $p-1$ solutions with $p \nmid x, y$. (It is well-known that an $x^2+y^2 \equiv a$ type equation has at least $p-1$ solutions in general.) This is enough to conclude.

Let $S$ be the set of reduced nonzero quadratic residues modulo $p$, so that $S$ contains exactly the reduced residues of $i^2$, where $i\in\left\{1,2,\cdots,\frac{p-1}2\right\}.$ Letting $S'$ be the set of possible reduced residues attainable by $(x^2+y^2)^2$ for integers $x$ and $y$ relatively prime to $p,$ we claim that $S=S'.$ First, we note that $(x^2+y^2)^2$ must clearly be a quadratic residue modulo $p$, implying that all quadratic nonresidues modulo $p$ are not in $S'.$ Additionally, note that having $(x^2+y^2)^2\equiv0\pmod{p}$ is equivalent to having $$x^2+y^2\equiv0\pmod{p},$$which is impossible since $p\equiv3\pmod4$, due to Fermat's Christmas Theorem. Hence $0\notin S'$, thus ruling out all quadratic residues and zeroes modulo $p$. It follows that $S'\subseteq S$; to show that $S=S'$, it suffices to prove that there exist $x$ and $y$ such that $x^2+y^2\equiv a\pmod{p}$ for all $a\in\{1,2,\cdots,p-1\}$. Let $N$ be some solutions to the equation $x^2+y^2\equiv a\pmod{p}$, where $(x,y)\in\{1,2,\cdots,p-1\}^2.$ Fixing $y$, we find that $$y^2\equiv a-x^2\pmod{p},$$and it is well known that there are $\left(\frac{a-x^2}{p}\right)+1$ solutions $y\in\{0,1,\cdots,p-1\}$ to the above equation. However, note that we must have $y\not\equiv0\pmod{p}$ in our original setup; if such a case happens, there must exist some $x$ such that $a-x^2\equiv0\pmod{p}$, which happens iff $a$ is a quadratic residue modulo $p$, corresponding to $\left(\frac{a}{p}\right)+1$ such values of $x$, each of which correspond to $1$ bad value of $y=0.$ Thus, as $x$ ranges from $1$ to $p-1$, we find that $$N=\sum_{x=1}^{p-1}\left(\left(\frac{a-x^2}p\right)+1\right)-\left(\left(\frac{a}{p}\right)+1\right),$$where the terms $\left(\frac{a-x^2}p\right)$ and $\left(\frac{a}{p}\right)+1$ respectively correspond to the number of pairs $(x,y)$ for some fixed $x$ and the number of bad pairs $(x,0)$. We then find that \begin{align*} N&=\sum_{x=1}^{p-1}\left(\left(\frac{a-x^2}p\right)+1\right)-\left(\left(\frac{a}{p}\right)+1\right)\\ &=p+\sum_{x=0}^{p-1}\left(\left(\frac{a-x^2}p\right)\right)-\left(\left(\frac{a-0^2}{p}\right)-1\right)-\left(\left(\frac{a}{p}\right)+1\right)\\ &=p+\sum_{x=0}^{p-1}\left(\left(\frac{a-x^2}p\right)\right)-2\left(\left(\frac{a}{p}\right)+1\right)\\ &=(p-2)+\sum_{x=0}^{p-1}\left(\left(\frac{a-x^2}p\right)\right)-2\left(\frac{a}{p}\right). \end{align*}As it is well known that $$\sum_{x=0}^{p-1}\left(\left(\frac{a-x^2}p\right)\right)=(-1)^{\frac{p+1}2}$$for $\gcd(a,p)=1$, as in our case, it follows that, since $p=4k+3$, \begin{align*} N&=(p-2)+\sum_{x=0}^{p-1}\left(\left(\frac{a-x^2}p\right)\right)-2\left(\frac{a}{p}\right)\\ &=(p-2)+(-1)^{\frac{p+1}2}-2\left(\frac{a}{p}\right)\\ &=(p-2)+(-1)^{2(k+1)}-2\left(\frac{a}{p}\right)\\ &\ge p-2+1-2\\ &=p-3. \end{align*}Thus, for $p>3$, we have $N\ge1$, so there must some $(x,y)$ such that $x^2+y^2\equiv a\pmod{p}$. It therefore follows that $S=S'$ for all $p>3.$ Now consider the case were $p=3.$ Since the only nonzero quadratic residue modulo $1$ and both $S$ and $S'$ are nonempty, it follows that $S=S'=\{1\}.$ We therefore conclude that $S=S'$ for all primes $p=4k+3$. Our final answer is therefore \begin{align*} |S'|&=|S|\\ &=\frac{p-1}2. \end{align*}$\blacksquare$ - Jörg

We shall use $\left ( \frac ap \right)$ to denote the value of the Legendre Symbol $\pmod{p}$ evaluated at $a$. We claim the answer is $\boxed{\frac{p-1}{2}}$, i. e. the number of nonzero quadratic residues $\pmod{p}$. Note that $0$ is not achievable, due to Fermat's Christmas Theorem. Note further that all residues we obtain must be quadratic residues by definition. We now show that we can obtain all nonzero quadratic residues. Observe that $\left ( \frac{x}{p} \right ) = 1 \iff \left ( \frac{-x}{p} \right ) = -1$. So in particular the set $A = \left \{ x^2 : \left ( \frac{x}{p} \right ) = 1 \right \}$ is the set of all nonzero quadratic residues, as is the set $B =\left \{ x^2 : \left ( \frac{x}{p} \right ) = -1 \right \}$. Now choose an arbitrary value of $\frac yx$. If $ 1 + \left (\frac yx \right )^2$ is a Quadratic residue, multiplying by $x^2$ for any $x$ and squaring gives us the set $A$; else doing so gives us the set $B$. Therefore, the answer is confirmed, $\square$

We need $(x^2+y^2)^2$ to be a QR mod $p$. Claim: Any non-zero residue mod $p$ are the remainders. The problem is equivalent to finding number of $a$ such that $x^2+y^2\equiv \pm a\pmod{p}, a\nmid p$. One of $a,-a$ is a QNR mod $p$ because $p=4k+3$. WLOG it is $a$. $\vspace{0.5pt}$ The number of solutions to $x^2+y^2\equiv a\pmod{p}$ is known to be $p-(-1)^{\frac{p-1}{2}}, a\nmid p$ which evaluates to $p-1$. Observe that $x,y\nmid p$ because if one of them did then $a$ will be QR which is contrary to our prior assumption. $\vspace{0.5pt}$ So the number of remainders will be $\boxed{\frac{p-1}{2}}$ since primes are of the form $4k+3$.