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


  • NMIMS, Mumbai (Marketing)


    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

    0_1505216890612_a1ea5506-4f2e-418a-b715-ce5379fb7282-image.png

    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

    0_1505217156083_a8ac473b-50c8-42e8-8bd1-ca345199f505-image.png

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



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



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


  • NMIMS, Mumbai (Marketing)


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


  • NMIMS, Mumbai (Marketing)


    @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


  • Being MBAtious!


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



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


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.