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 if
and the only positive divisors of
are 1 and
If
and
is 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, sayLet
Now
so either
is prime or
is a product of primes. Of course
is not prime since it exceeds
for
Moreover, no
divides
(if
divides
then
divides the difference
This contradicts theorem 1.
Theorem 3
If a primedoes not divide
then
Proof: Letthen
divides
so
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 prime
divides a product
then
divides at least one of the factors.
Proof: Assumedivides
and
By theorem 3
so by Euclid's Lemma,