Prime Numbers

Primes numbers are used much in codes and cryptography. The primes numbers less than 100 are coloured orange in the following number square,.

A numberis a prime number ifand the only positive divisors ofare 1 andIf andis not prime then it is called composite. Prime numbers are usually denoted by some variation on the letteror

The prime numbers less than 50 are 2,3,5,7,11,13,17,19,23,29,31,37,42,43,47.

Theorem 1

Every integeris either a prime number or a product of prime numbers.

Proof: Use induction onThe theorem is clearly true forAssume it is true for every . Ifis not prime it has a positive divisorhencewhereBut bothso each ofare products are prime numbers hence so is

Theorem 2

There are infinitely many prime numbers.

Proof (originally due to Euclid): Suppose there are only a finite number, sayLet Nowso eitheris prime oris a product of primes. Of courseis not prime since it exceedsforMoreover, nodivides(if dividesthendivides the differenceThis contradicts theorem 1.

Theorem 3

If a primedoes not dividethen

Proof: Letthendividessoorbutsobecause hence

The above theorem implies also that the only divisors of p are 1 and p, the definition of prime numbers.

Theorem 4

If a primedividesthenorMore generally if a primedivides a productthendivides at least one of the factors.

Proof: AssumedividesandBy theorem 3so by Euclid's Lemma,