Sum of two squares

If n = p*q where p and q are primes of the form 4k + 1 then n is a sum of squares. Similarly for more factors.

Primes of the form 4k + 1 can be written as the sum of two squares (uniquely). Then the same is true for a product of such primes. This follows from the identity
(a² + b²)(c² + d²) = (ac – bd)² + (ad + bc)², that is easily proved using complex numbers (of course it is easy to check, once found, by complex numbers lead directly to the result). The proof depends essentially on the fact that the norm is multiplictive:

(a² + b²)(c² + d²) = |a + ib|² * |c + id|² = |(a + ib)(c + id)|² =
= |ac – bd + i(ad + bc)|² = (ac – bd)² + (ad + bc)²

So, provided the prime factors can be written as sum of two squares this identity makes it possible to calculate two squares that sum to the given number. We must first write the primes as sums of two squares, maybe by trial and error, but that should be much easier than trying the whole given number. And we are guaranteed a result at least if all prime factors are of the form 4k + 1. – Of course, if other factors (not prime) are seen to be sums of two squares we can start from them using the above identity.

Examples:
15457 = 13*29*41 = (2² + 3²)(2² + 5²)(4² + 5²) =
= ( (2*2 – 3*5)² + (2*5 + 3*2)² ) * (4² + 5²) = (11² + 16²)(4² + 5²) =
= (11*4 – 16*5)² + (11*5 + 16*4)² = 36² + 119²

25*90 = (3² + 4²)(3² + 9²) = (3*3 – 4*9)² + (3*9 + 4*3)² = 27² + 39²

Annonser

7 Responses to Sum of two squares

  1. Alexandra skriver:

    You’re so interesting! I do not believe I’ve read through a single thing like this before.
    So wonderful to find someone with a few original thoughts on this issue.
    Seriously.. thanks for starting this up. This website is one thing that’s needed on the internet, someone with a bit of originality!

  2. Actually no matter if someone doesn’t understand then its up to other viewers that they will assist, so here it takes place.

  3. Ivy skriver:

    Furthermore, its qualities improve the immune functions of the
    body; prevent heart disease, diabetes, cancer and much more.
    Some sources even say that it is more effective than medicated dandruff
    shampoos and conditioners. When it comes to antibacterial properties, one study in particular found that
    virgin coconut oil helped to treat skin infections.

  4. Otilia skriver:

    Superb, what a web site it is! This weblog presents valuable data to us, keep
    it up.

  5. Read more skriver:

    Hmm it appears like your website ate my first comment (it was extremely long) so I
    guess I’ll just sum it up what I wrote and say, I’m thoroughly enjoying your blog.
    I too am an aspiring blog blogger but I’m still new to the whole thing. Do you have any helpful hints for inexperienced blog writers? I’d genuinely appreciate it.

  6. Victorina skriver:

    Its like you read my mind! You seem to know a lot approximately
    this, such as you wrote the book in it or something.
    I think that you just can do with some p.c.
    to power the message house a bit, but other than that,
    that is fantastic blog. An excellent read.
    I’ll definitely be back.

  7. Powerline Indonesia

    Sum of two squares | Bengts funderingar

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut /  Ändra )

Google+-foto

Du kommenterar med ditt Google+-konto. Logga ut /  Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut /  Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut /  Ändra )

Ansluter till %s

%d bloggare gillar detta: