# Prime conditional problem in modulo

Any odd prime p can be written in the form of $x^2 + y^2$ when $p \equiv 1 \pmod{ 4}$. explain the proof. Is there any such condition equations and satisfying the primes? if there, how to construct them? Also, is there any function, which will give a prime.

-
You are not using LaTeX correctly. You need to place dollar signs round complete formulae, and not just small parts of them. Please have a look at the edit I made. – Old John Dec 15 '12 at 10:18

I do not know the prime function. It is my out of expectation. We can create your cited type problems. For example, primes can be written as primes $x^2$ + 2$y^2$ if and only if p = 1 or 3 (mod 8). Regarding your first question:

Let L = (1, 0, 1) and L has discriminant = -4. If (a, b, c) is reduced representative of some equivalence class with |b| < or = a < or = |c| => $b^2$ = 4(ac -1). Since |ac| > or = $b^2$, we should have ac -1 = 0. The only form of L is (1, 0, 1). Thus h (-4) = 1 and p can be expressible by (1, 0, 1) if and only if -4 = () (mod 4p). I hope you can do the necessary things to complete the solution of $x^2$ + 2$y^2$ if and only if p = 1 or 3 (mod 8). All the best!

-
You are not using LaTeX correctly. You need to place dollar signs round complete formulae, and not just small parts of them. Please have a look at the edit I made to the question. – Old John Dec 15 '12 at 10:34

Regarding the proof: Here's an elementary argument. It can be modified to the following similar problems:

• $x^2 + 2y^2 =p \leftrightarrow p \equiv 1,3 \mod 8$ or $p=2$.
• $x^2+ 3y^2 = p \leftrightarrow p \equiv 1 \mod 3$ or $p=3$.

Neccesity: Note that for any $x,y$, we have $x^2+y^2=0,1,2 \mod 4$, so for it to be a prime $p$ we need either $p=2$, or $p= 1 \mod 4$.

Sufficiencty: If $p=2$, $x=y=1$ will work. If $p \equiv 1 \mod 4$, then $t^2 + 1 = 0 \mod p$ is solvable, as it is equivalent to finding an element of order 4 in $(\mathbb{F}_{p})^{\times}$, which is a cyclic group of order $p-1$, i.e. divisible by $4$, so you can just take $t=g^{\frac{p-1}{4}}$ for any generator $g$.

By the pigeonhole principle, two of the elements $\{ ta-b \mod p| 0 \le a,b < \sqrt{p} \}$ are the same mod $p$, say: $ta-b=ta'-b' \mod p$, i.e. $$t(a-a')=(b-b') \mod p$$ Square both sides of the last equation and move both terms to same side to get: $(b-b')^2 + (a-a')^2 \equiv 0 \mod p$. Note that $|a-a'|,|b-b'| < \sqrt {p}$, so $0< (b-b')^2 + (a-a')^2 < 2p$, implying: $$(b-b')^2 + (a-a')^2 = p$$

Regarding more such conditions - I suggest the wonderful book "Primes of the form $x^2 + ny^2$" by David A. Cox. Another related book is "Introduction to the Construction of Class Fields" by Harvey Cohn.

Regarding a prime-generating function: consult this Wikipedia page. There are many formulas, most of them impractical. But there's a system of Diophantine equations "defining" the primes, which is maybe what you're looking for.

-

Here is (perhaps) a simplification of the proof by Euler given in the wikipedia link. If $p$ is a prime which is congruent to 1 (mod $4$), then $-1$ is a square in the field $\mathbb{Z}/p\mathbb{Z}.$ Hence there is an integer $x$ such that $p$ divides $x^{2}+1.$ We may replace $x$ by $-x$ if necessary, and suppose that $|x| \leq \frac{p-1}{2}.$ Then $x^{2}+1 \leq 1+ (\frac{p-1}{2})^{2} \leq \frac{p^{2}-p}{4}.$ If there is a prime congruent to 1 (mod $4$), which is not the sum of two squares, there is a smallest such prime, so suppose that that prime is $p.$ Choose integers $y$ and $z$ (not both zero) so that $y^{2}+z^{2} = mp$ where $m$ is an integer, but as small as possible. We know that $m \leq \frac{p-1}{4}.$ We claim that $m = 1.$ Note first that $y$ and $z$ are relatively prime. For suppose that $h = {\rm gcd}(y,z) \neq 1.$ Now $|h| <p$ as $y^{2} + z^{2} <p^{2}.$ Since $h^{2} | mp,$ we have $m = h^{2}n$ for some integer $n.$ Then $np = (\frac{y}{h})^{2}+ (\frac{z}{h})^{2}$ contrary to the choice of $m.$

If $m = 2n$ for some integer $n$, then $y$ and $z$ are both odd, (they can't both be even), and we use the standard trick $np = (\frac{y-z}{2})^{2} + (\frac{y+z}{2})^{2},$ which dates to antiquity. But this contradicts the choice of $m,$ so $m$ is odd. Hence if $m >1,$ then $m$ is divisible by an odd prime $q < p.$ We have excluded the case that both $y$ and $z$ are divisible by $q,$ so neither is divisible by $q,$ since $y^{2}+z^{2}$ is divisible by $q.$ Both $y$ and $z$ have non-zero images in the field $\mathbb{Z}/q\mathbb{Z},$ so $-1$ is a square in that field, ie $q \equiv 1$ (mod 4) as $4 | (q-1)$. By the minimal choice of $p,$ we know that $q$ is a sum of two integer squares, say $q = u^{2} +v^{2}.$ Now we can argue as Euler did that $\frac{m}{q}$ is a sum of two integer squares, and $\frac{m}{q}$ is still divisible by $p,$ contrary to the choice of $m.$

-