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.
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
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.
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.
If a primedividesthenorMore generally if a primedivides a productthendivides at least one of the factors.
Proof: AssumedividesandBy theorem 3so by Euclid's Lemma,