## Posts

Showing posts from October, 2017

### Representing integers as the sum of two squares

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

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…