PRIME NUMBERS

Prime numbers are numbers that have only two factors: one and itself. This page covers theorems and lemmas that pertain to the distribution and properties of prime numbers.

Euclid's lemma:

Euclid's lemma is a fundamental argument that is named after the ancient Greek mathematician Euclid.

It states:

If a prime number divides the product of two integers, it must divide at least one of those integers individually

Example, if p = 3, a = 48, b = 16, then a x b = 48 × 16 = 768, and since this is divisible by 3, the lemma implies that one or both of 48 or 16 must be as well. In this case, 48 = 3 x 16.

Fermat's little theorem

The theorem states that if p is a prime number and a is any integer not divisible by p,

then:

Example: If p = 11 and a=2, then 2^10≡1(mod11). *to learn more about mods, please visit our remainders page

2^10 = 1024 -> 1024/11 = 93 x 11 + 1

In other words, there will be a remainder of 1

An alternative to this theorem is

Example: If P=11 and a = 2, then 2^12 = 2 (mod 11)

2^11 = 2048 -> 2048/11 = 11 x 186 + 2