Pythagorean primes

Fermat stated that an odd prime p can be expressed as a sum of two squares if and only if p leaves a remainder of 1 when divided by 4:

p = a² + b² ⇔ p ≡ 1 (mod 4),

where a and b are some positive integers.  Such primes are called Pythagorean primes.

If you are interested, the proof can be found in any elementary number theory textbooks.

Prime generating formulas?

I wrote about Wilson's theorem previously.  While Wilson's theorem can be used to test whether a positive integer is prime, there are no known formulas generating prime numbers.  Throughout the ages, mathematicians have been searching for such a formula, yet without success.  In addition to the Mersenne primes, there are other numbers studied by Fermat and Euler.

The Fermat numbers are generated by the formula, for n = 0, 1, 2, ...

The first five Fermat numbers 3, 5, 17, 257 and 65537 are all prime.  However, when n = 5,

F₅ = 2³² + 1 = 4294967297 = 641 × 6700417

is composite.

Euler saw that the formula n² − n + 41 generates primes for n = 1, 2, 3, ... , 40.  Clearly, the formula fails to generate a prime when n = 41.

Fermat's little theorem

Fermat is among the most prominent figures in the history of number theory.  One of the elegant properties about numbers he discovered is known as Fermat's little theorem, which states that if p is a prime number, then for any integer a, the number a ^p − a is divisible by p:

a ^p ≡ a (mod p).

An alternative version of Fermat's little theorem states that if a is not divisible by p, then the number a ^p − 1 − 1 is a multiple of p:

a ^p − 1 ≡ 1 (mod p).

Fermat's little theorem was proved by Euler and can be generalized by Euler's theorem: if a and n are relatively prime, then

a ^φ(n)  ≡ 1 (mod n),

where φ(n) is the number of integers between 1 and n that are relatively prime with n.  Euler's theorem form the basis of the RSA encryption system.

Pythagorean triples

A Pythagorean triple (a,b,c) consists of positive integers a, b and c such that

The triple is called primitive if a, b and c are relatively prime.  It can be easily proved that all Pythagorean triples can be generated using Euclid's formula:

where m and n are positive integers with m > n.  The triple (a,b,c) generated is primitive if m and n are coprime and m - n is odd.  There are 16 primitive Pythagorean triples with c < 100:

( 3 , 4 , 5 )	( 5, 12, 13)	( 7, 24, 25)	( 8, 15, 17)
( 9, 40, 41)	(11, 60, 61)	(12, 35, 37)	(13, 84, 85)
(16, 63, 65)	(20, 21, 29)	(28, 45, 53)	(33, 56, 65)
(36, 77, 85)	(39, 80, 89)	(48, 55, 73)	(65, 72, 97)

There are a lot of interesting facts about primitive Pythagorean triples.  For example:

• One of a and b is odd, the other is even; c is always odd.
• Exactly one of a and b is divisible by 3.
• Exactly one of a and b is divisible by 4.
• Exactly one of a, b and c is divisible by 5.
• Every prime factor of c leaves a remainder of 1 when divided by 4.

A generalization of the Pythagorean triples leads to the famous Fermat's Last Theorem dated 1637, which remained an unsolved mystery for 358 years until finally proved by Andrew Wiles in 1995.  The theorem states that the equation



has no non-trivial solutions for (a,b,c) if n is a positive integer greater than 2.