Re: Question about a^2+b^2=4k+1 prime ...

Suppose p is a prime of the form 4k+1.
Letting r=(2k)! (mod p) we have (by
Wilson's theorem) r^2+1=0 (p), so
there is an m such that r^2+1=mp.
Therefore we have (r+i)(r-i)=mp.

How does this help us get a^2+b^2=p ??

If P is prime, then for quite a large
proportion of A ... we have the result

A^(P-1) = 1 mod P, A^((P-1)/2) = -1 mod P

therefore if A^((P-1)/4) = B mod P,

B^2 = -1 mod P.

We can simply take B=(2k)! (mod P)

By expanding P/B as a continued fraction,
we find there are numbers near the middle
of the expansion such that C^2 + D^2 = P.


Hmm, an example is in order.

Let P=41, so k=10, and B=9. Then B^2=-1(P)

Now 41/9 = [4;1,1,4], and the convergents are
4/1, 5/1, 9/2 and 41/9. Is it always consecutive
numerators of the convergents that give us the
two numbers we need?

Another example, P=233, k=58, B=89.

233/89 = [2;1,1,1,1,1,1,1,1,2]

Convergents
2/1, 3/1, 5/2, 8/3, 13/5, 21/8,
34/13, 55/21, 89/34 and 233/89

Our two squares are 8 and 13, which appear
as consecutive numerators, immediately before
the midpoint.

I don't see why.
.