Theory Of Equations - Sum of Squares - Anubhav Sehgal, NMIMS Mumbai

[anubhav_sehgal]

Any question reducible to a^2 + b^2 = N and you are asked to find ordered/unordered positive/non-negative/total integral solutions.

Keynote 1

N’s prime factorization must consist of only (4k + 1) form primes and in case there are (4k + 3) form primes, they must be raised to an even power for an integral solution to exist.

Logic : a^2 mod 4 = 0,1 only
Similarly, b^2 mod 4 = 0,1 only
Hence, (a^2 + b^2) mod 4 = (0 + 0) OR (0 + 1) OR (1 + 0) OR (1 + 1) = 0, 1, 2 only
Now when we are dealing with prime factorization of a number, we can see that primes are only (4k + 1) or (4k + 3) form barring when prime is the only even prime = 2.
Now (4k + 1) form prime raised to any power p will leave remainder = 1^p = 1 only by simple multiplicative nature of remainders. So with their presence it is possible to express them as sum of two squares (remainders must be 0, 1, 2 only).
But with (4k + 3) form prime, remainder will be 3 when raised to an odd power while 1 when raised to an even power.

Therefore, it is necessary that any presence of (4k + 3) form prime in factorization of N is even number of times i.e. any prime of (4k + 3) form in factorization must have even power for it to be possible to express them as sum of two squares

Examples
a^2 + b^2 = 2 * 7 * 13 has no integral solutions since 7 = 4(1) + 3 is a prime having odd power.
a^2 + b^2 = 2 * 7^2 * 11 also has no integral solutions since while 7 has an even power another prime 11 of the form 4k + 3 has an odd power.
We will see how to handle question when all power of (4k + 3) primes are even in further keynotes.

Keynote 2

When all primes of (4k + 3) form are present with even powers, integral solutions will exist but will be independent of all the (4k + 3) forms. So you may visualize the prime factorization of N, in such a case, to not actually consist of those primes.

Keynote 3

When prime factorization of N contains power of 2 amongst presence of other primes as well, it can simply be ignored like the even powered (4k + 3) primes apart from consideration while checking if the N if a perfect square or not.

Keynote 4

When N is expressed as solely a power of 2, then a^2 + b^2 = 2^odd has only 1 positive integral ordered solution which is a = b = 2^[(odd – 1)/2]
a^2 + b^2 = 2^even has no positive integral ordered solutions.
while total integral solutions will be 4 in each case.

Examples

a^2 + b^2 = 2^3
a, b = +- 2, +- 2 i.e. total 4 integral solutions while just 1 positive integral solution.
Since a = b hence it does not matter if ordered asked or unordered for positive integral as a, b is same as b, a so they yield the same answer.

a^2 + b^2 = 2^4
Though this equation does not have positive integral solutions. It will still have 4 integral solutions as follows
a, b = +- 2^2, 0 and 0, +- 2^2.
None of these 4 are positive as 0 is neither positive nor negative.
If asked for non-negative integral solutions, you can say the above equation has 2 unordered non-negative integral solutions and 4 ordered non-negative integral solutions

Keynote 5

When N is not a perfect square the number of ordered positive integral solutions is given by number of factors of N ignoring the presence of (4k + 3) primes and 2 provided they satisfy the above discussed conditions.
Total integral solutions = (Ordered Positive integral solutions) * 4

Keynote 6

When N is a perfect square the number of ordered positive integral solutions is given by number of factors of N minus 1 ignoring the presence of (4k + 3) primes and 2 provided they satisfy the above discussed conditions.
Total integral solutions = (Ordered Positive integral solutions) * 4 + 4

Now let’s take up several examples here to clear up all the keynotes of this domain.

Example 1 :
a^2 + b^2 = 5^2 * 13^2
Check 1: Are all (4k + 3) primes having even power. None present. Check.
Check 2: Is N a perfect square? Yes. Number of positive integral solutions (ordered) = (2 + 1)(2 + 1) – 1 = 8 Number of positive integral solutions (unordered) = 8/2 = 4
Total integral solutions(ordered) = 4 * 8 + 4 = 32 + 4 = 36
Total integral solutions(unordered) = 36/2 = 18

This is the actual solution set for this question. You can now visualize a few points here

1. 1 is subtracted in case of perfect square in case of positive integral solutions due to the +- 65, 0 and 0,+- 65 solution as 0 is non-negative but not positive.
2. While an additional 4 is added to accommodate for the same in total integral solutions

Example 2 :
a^2 + b^2 = 5 * 13^2
Positive integral (ordered) = 2 * 3 = 6;
Positive integral (unordered) = 6/2 = 3
Total integral (ordered) = 4 * 6 = 24;
Total integral (unordered) = 24/2 = 12

Example 3 :
a^2 + b^2 = 7 * 13^4
No solution since power of 7 is odd.

Example 4 :
a^2 + b^2 = 7^2 * 13^4
Check 1: Power of all (4k + 3) form primes is even. Check.
Check 2: Is it a perfect square? Yes.
Ignoring the presence of even powered (4k + 3) primes,
Positive integral(ordered) = (4 + 1) – 1 = 4
Positive integral(unordered) = 4/2 = 2
Total integral(ordered) = 4 * 4 + 4 = 20
Total integral(unordered) = 20/2 = 10

Example 5 :
a^2 + b^2 = 2^4 * 3^2 * 5^2
Perfect square, (4k + 3) primes having even power, 2 present along with other primes.
Ignore (4k + 3) primes and 2 as well,
Positive integral (ordered) = (2 + 1) – 1 = 2
Positive integral (unordered) = 2/2 = 1
Total integral (ordered) = 4 * 2 + 4 = 12
Total integral (unordered) = 8/2 = 4

Example 6 :
a^2 + b^2 = 2 * 3^2 * 5^2
Not a perfect square, (4k + 3) primes having even power, 2 present along with other primes.
Ignore (4k + 3) primes and 2 as well,
Positive integral (ordered) = (2 + 1) = 3
Positive integral (unordered) = (3 + 1)/2 = 2
Total integral (ordered) = 4 * 3 = 12
Total integral (unordered) = 12/2 = 6

This is the actual solution set for this question. Here occurrence of a (+-15, +-15) form of solution brings the change to our calculation.

[Manmohan]

in example 5 ..total ordered solutions integral ..even though N is a perfect square why did you not do plus 4

[Manmohan]

In example 6 why in unordered solution ( 3+1) is done

[anubhav_sehgal]

@manmohan
Yes for example 5 in reference to Keynote 6, it will be +4 for total solutions.

[anubhav_sehgal]

@manmohan
For example 6
Assume three ordered solutions for the equation
a,b
c,c
b,a
Ordered sets = 3
Unordered sets = 2{=(3+1)/2} = {(a,b) ; (c,c)}

Two situation for a^2 + b^2 = N
Case 1: a and b are equal
2a^2 = N
a = sqrt(N/2)
Ordered sets = a,a = Unordered sets
Case 2 : a and b not equal
Ordered sets = a,b and b,a = 2(unordered sets a,b)

Let Odd number of ordered sets = 2k + 1
Here k will be the ordered sets of Case 2 type and 1 will be the case 1 type
Hence unordered sets = k + 1 = ((2k +1)+1)/2

[zabeer]

@manmohan @anubhav_sehgal
Corrected Example 5 as below
Total integral (ordered) = 4 * 2 + 4 = 12

[test1234]

In keynote 4, example 2, total non-negative unordered integral solutions is just 1 (4,0) and total non-negative ordered integral solutions are 2 (4,0 and 0,4). Please Correct me if I'm wrong.