Posts

Showing posts from October, 2017

Representing integers as the sum of two squares

Image
Almost 400 years ago, Pierre de Fermat stated that every odd prime of the form `4k+1` can be expressed as the sum of two squares:

`p = x^2 + y^2`

with integers `x` and `y`, if and only if

`p ≡ 1 mod 4`

Later on, around the year 1747, Leonhard Euler was able to prove Fermat's statement correct.
# Overview In this post, we're presenting a recursive algorithm for finding all the possible representations, as a sum of two squares, for any given integer that can be expressed this way.
For example, if `n=12345678910111213`, we can represent it as a sum of two squares in 4 different ways:
`12345678910111213 = 1251082^2 + 111104067^2` `12345678910111213 = 13508317^2 + 110286918^2` `12345678910111213 = 52418877^2 + 97969078^2` `12345678910111213 = 64959738^2 + 90143837^2`
If the prime factorization of a number is known, it can be verified if the number is expressible as a sum of two squares by checking each prime factor modulo 4. If a prime factor is congruent to `3 mod 4` , then its …

Representing integers as the difference of two squares

Image
Most integers can be represented as the difference of two squares, where each square is a non-negative integer.

Algebraically speaking:

`n = x^2 - y^2`

for some non-negative integers `x` and `y`.

In this blog post we're going to look at a simple and elegant algorithm for finding all the possible representations for any given integer that can be represented as a difference of two squares, using its divisors.

For example, if we have `n = 12345`, we can represent it in four different ways as a difference of two non-negative integer squares:

`12345 = 419^2 - 404^2`
`12345 = 1237^2 - 1232^2`
`12345 = 2059^2 - 2056^2`
`12345 = 6173^2 - 6172^2`

# Finding solutions By writing `n` as the product of two whole numbers, `n = a*b`, we have the following identity:

`a*b = ((a+b)/2)^2 - ((a-b)/2)^2`

Then, by iterating over all the divisors of `n`, we generate all the possible representations for `n` as a difference of two non-negative squares.

In order to generate only integer solutions, we have…