Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote -1 down vote accepted

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!

share|cite|improve this answer
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.

share|cite|improve this answer

This is a famous theorem of Fermat.

share|cite|improve this answer

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

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.