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 number
is a prime number if
and the only positive divisors ofare 1 and
If andis not prime then it is called composite. Prime numbers are usually denoted by some variation on the letter
or
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 for
Assume it is true for every
. If
is not prime it has a positive divisor
hence
where
But both
so each of
are 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, say
Let 
Now
so either
is prime oris a product of primes. Of courseis not prime since it exceeds
for
Moreover, nodivides(if dividesthendivides the difference
This contradicts theorem 1.
Theorem 3
If a primedoes not divide
then
Proof: Let
then
dividesso
or
but
so
because 
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 primedivides
then
or
More generally if a primedivides a product
thendivides at least one of the factors.
Proof: Assumedividesand
By theorem 3
so by Euclid's Lemma,
