RGB Classic Games Forum

Code: Select all

1) It is obvious that a square can be only 0 or 1 (mod 4). So, sum
of two squares cannot be 3 (mod 4).

2) Next, the proof that if p divides N, and p is prime of form 3 (mod 4)
then N has no sum of two squares representation in lowest terms.
That is, N cannot be represented as x^2+y^2, such
that gcd(x,y) = 1.

Proof: Since p|N, so p|x^2+y^2. If p|x, then p|y also,
so gcd(x,y) is not 1. So, p cannot divide x or y. So, x and y are congruent
between 1 and p-1 (mod p). Let y=ux, where 1 <= u <= p-1. Then, since
N = x^2+y^2 = 0 (mod p), x^2(1+u^2) = 0 (mod p).
p does not divide x, so (1+u^2) = 0 (mod p). So, -1 is a quadratic residue
(mod p). This is false when p is a prime of form 3 (mod 4). So, N has no sum of two
squares representation in lowest terms (x,y) = 1. If it exists, it should be such
that y = ux (mod p) such that u^2 = -1 (mod p), where p is a prime of form 3 (mod 4) only.

3) Next the proof that if N has a prime factor p of form 3 (mod 4) to an odd power,
then N has no sum of two squares representation at all.
Let p^c divide N, and p^(c+1) does not divide N, where c is odd,
let N = x^2+y^2 with gcd(x,y) = d.
then N = d^2(X^2+Y^2) with gcd(X,Y)=1.
Putting X^2+Y^2 = n, N = d^2n.
Let p^m be the highest power of p, that divides d.
Since n = N/d^2, so highest power of p that divides n is c-2m.
Since c is odd, c-2m > 0. So, p divides n. Since, n = X^2+Y^2,
with gcd(X,Y) = 1, p dividing N with p being a prime of form 1 (mod 4). This is
not possible by (2). Hence the result.

Even if N contains power of p to an even power, the representation of N as sum
of two squares can be only multiples of those values of N divided by all those primes
that are congruent to 3 (mod 4).

4) If p is a prime of form 1 (mod 4), then there exist values of x,y less than p
such that x^2+y^2 = mp, where 0 < m < p.

Proof: If p is prime of form 1 (mod 4), then -1 is a quadratic residue (mod p).
If z is quadratic residue, then so is -z. Since z^2 is quadratic residue,
so is -z^2. Since k^2 mod p = (p-k)^2 mod p, the
quadratic residues are symmetric, so the distinct quadratic residues are from
k^2, where k is between 1 to (p-1)/2 only.

Within this range, for some quadratic residue x^2, there exist some other
value of y such that y^2 = -x^2 mod p. So, x^2+y^2 = 0 (mod p).
Let x^2 + y^2 = mp. Clearly, m>0.
Since, x^2 + y^2 <= 2*((p-1)/2)^2, so m<p.

5) Next comes the proof that for any prime p of form 1 (mod 4), there exist values of
x,y such that x^2+y^2 = p.

Proof by method of infinite descent.
If m=1, then there is nothing to prove at all.
If m>1, then x^2+y^2 = mp, so that x^2+y^2 = 0 (mod m).
Let r and s be minimal residues of x and y (mod m), such that -m/2 < r,s < m/2.
r is congruent to x (mod m) and y is congruent to s (mod m). So,
r^2+s^2 = 0 (mod m).
r and s cannot be both zero simultaneously, because if so, then m divides both x and y,
so m^2 divides x^2+y^2 = mp, so m divides p. This is false
since p is prime.
Let r^2+s^2 = nm. Since, -m/2 < r,s < m/2, so n < m.

(x^2+y^2)(r^2+s^2) = m^2.np
(xr+ys)^2 + (xs - yr)^2 = m^2.np
Since x and r belong to the same residue class (mod m), and so does y and s,
m divides (xr+ys), since x^2+y^2 = 0 (mod m),
m also divides (xs-yr) = (xy-yx) mod m = 0 (mod m).
Let (xr+ys) = am, and that (xs-yr) = bm, then
a^2.m^2 + b^2.m^2 = m^2.np
or that, a^2 + b^2 = np, where n < m.
This says that there exist integers a, b such that a^2+b^2 = np, where n<m.
We can keep continuing this descent until we get some integers u and v such that
u^2+v^2 = p, where p is a prime of form 1 (mod 4).

6) Next we have to prove such representation is unique.
Let N = a^2+b^2 = c^2+d^2, with two distinct sum
of two squares representation. Then N is composite.

Proof: Since even number other than 2 is composite, we will consider only the case when N is odd.
2 has only one such representation, by the way.
If N is odd. One of a,b is odd, and so is c,d pair as well.
Let a,c be odd. b,d be even. Let a>c, then b<d.
Since we have that a^2+b^2 = c^2+d^2
thus, a^2-c^2 = d^2-b^2
(a-c)(a+c) = (d-b)(d+b) where a-c, a+c, d-b, d+b are all even.
Let gcd(a-c,d-b) = g, where g is clearly even.
Let a-c = ug, d-b = vg, where gcd(u,v)=1. Then,
ug(a+c) = vg(d+b), u(a+c) = v(d+b). So u divides d+b, v divides a+c.
Let a+c = tv. Putting that, then it becomes that d+b = tu.
Since that gcd(u,v)=1 and a+c and d+b are both odd, hence that t is being even only.

So, 2N = a^2 + b^2 + c^2 + d^2
4N = 2a^2 + 2c^2 + 2b^2 + 2d^2
4N = (a+c)^2 + (a-c)^2 + (d+b)^2 + (d-b)^2
4N = t^2.v^2 + u^2.g^2 + t^2.u^2 + v^2.g^2
4N = (t^2+g^2)(u^2+v^2)
N = ((t/2)^2+(g/2)^2)(u^2+v^2)
Since t and g are both odd, so we have that (t/2) and (g/2) are both integers.
So, N is representable as product of two integers, both being clearly > 1 only.
Thus, N is composite.

EVERY PRIME OF FORM 1 (MOD 4) CAN BE UNIQUELY REPRESENTED AS SUM OF TWO SQUARES.

7) Every number that is not of form 4^b(8c+7)
can be represented as sum of three squares.

8) Regarding number of ways of representing an arbitrary value of N as sum of two squares:
Since (a^2+b^2)(c^2+d^2)
= (ac+bd)^2 + (ad-bc)^2
= (ac-bd)^2 + (ad+bc)^2
The product of two distinct primes of form 1 (mod 4) can be represented as sum of two squares
in two ways. Pending exercise to prove that these are the only ways of such representation.
Continuing up in this way, it is certainly possible to see that the product of k distinct primes of form
1 (mod 4) can be represented in 2^(k-1) ways.

9) Regarding product with a power of 2 will not change the number of ways of representation at all:
This is because of the fact that
2(a^2+b^2) = (a+b)^2 + (a-b)^2
Continuing this, we will get that
4(a^2+b^2) = (2a)^2 + (2b)^2

Code: Select all

Regarding representing up a random prime p of form 1 (mod 4) as sum of two squares:

The first algorithm that strikes to me is that
x^2+y^2=p
For a random value of x^2, we can get the value of square root of -x^2
by using the Modular Square Root algorithm only.
Such that x^2+y^2 = mp, for some value of m, 0 < m < p
Then, by using the fact in (5),
by putting that a = (xr+ys)/m, b = (xs-yr)/m
where r and s are minimal residues of x and y, such that -m/2 < r,s < m/2
we can get that a^2+b^2 = np, for some other value of n < m only
Continuing with this process, we can get for some value of u and v that
u^2+v^2 = p.

This algorithm I found somewhere online to solve up that equation only
x^2+y^2 = p for any arbitrary prime p of the form 1 (mod 4)
Let n be any quadratic non-residue mod p.
Then, let a=p, b=n^((p-1)/4) mod p, so that b = square root of -1 mod p
Then, similar to the GCD process,
while (b^2>p)
do {
(a,b) = (b, a mod b)
}
return (b,a mod b)

Code: Select all

We shall see how to compute square root of a number modulo a prime number.

Let a be the given number. And p be the given prime number which forms the modulo for the calculations.
If there exists a number x such that
x^2 = a (mod p)
then x is called a square root of a (mod p)

If there exists a square root for a (mod p), then a is called quadratic residue (mod p)
then there will be two square roots for a (mod p), such that their sum will be p.
If there exist no square root for a (mod p), then a is called quadratic non-residue (mod p)
In short, half of a less than p, have two square roots, and half of a less than p, have no square roots.

The Legendre Symbol (a/p) is defined by the following statements
1 if a is quadratic residue (mod p)
-1 if a is quadratic non-residue (mod p)
0 if a and p are not relatively prime.

For any prime number p and a base number a, the Legendre Symbol can be calculated by using the following formula
(a/p) = a^((p-1)/2) (mod p)

Note that, if p is prime number and a is less than p,
by the Fermat's Little Theorem,
a^(p-1) = 1 (mod p)
Since p is prime,
a^((p-1)/2) should be either 1 (mod p) or -1 (mod p)

If m is a composite number (or a prime number with only one prime factor),
and has prime factorization p(1)^b × p(2)^c × p(3)^d × ... × p(n)^z
then the Jacobi Symbol [a/m] is defined by
(a/p(1))^b × (a/p(2))^c × (a/p(3))^d × ... × (a/p(n))^z

So, given a base number a and a prime number p,
whether a has a square root (mod p), or not
can be calculated by the Legendre Symbol (a/p) = a^((p-1)/2) (mod p)

If (a/p) = 1, then a has two square roots (mod p), both of which add up to p.
If (a/p) = -1, then a has no square roots (mod p)
So, if (a/p) = 1, there exist two square roots for a (mod p)
We will see and then discuss here how to compute those square roots x, given a and p.
However note that this algorithm works only when p is prime.

If p = 3 (mod 4), then it is the best case
Square root is given by the following formula
x = a^((p+1)/4) (mod p)

If p = 5 (mod 8),
Square root is calculated with the following formula
x = a^((p+3)/8) (mod p)
So that, now, with this, either x^2 = a (mod p) or x^2 = (p-a) (mod p)
If x^2 = (p-a) (mod p), then
Assign x = 2^((p-1)/4)x (mod p)

If p = 1 (mod 8), then it is the worst case
Square root can be calculated by using the following algorithm
Select a random d between 0 and p-1 such that (d/p) = -1, i.e. d is a quadratic non-residue (mod p)
Write p-1 = 2^(s)t where t is odd, i.e. t is the highest odd divisor of p-1
Let A = a^t mod p
Let D = d^t mod p
Assign m = 0
For (i from 0 to s-1)
{
If ((A(D^m))^(2^(s-1-i)) = -1 (mod p))
{
Assign m = m + 2^i
}
}
x = a^((t+1)/2) D^(m/2) (mod p)
return x