Lesson Prime numbers and the Fundamental Theorem of Arithmetic

Source code of 'Prime numbers and the Fundamental Theorem of Arithmetic'

This Lesson (Prime numbers and the Fundamental Theorem of Arithmetic) was created by by ikleyn(52797)

: View Source, Show
About ikleyn:

<H2>Prime numbers and the Fundamental Theorem of Arithmetic</H2>

A prime number (or prime for short) is a natural number that has exactly two divisors: itself and the number 1. 
Because 1 has only one divisor, itself, we do not consider it as a prime number. 
So, 2 is the first prime, 3 is the next prime, but 4 is not a prime because 4 has three divisors: 1, 2, and 4. 
Numbers with more than two divisors are called composite numbers.

The first 20 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71.
The first 20 composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, 24, 25, 26, 27, 28, 30, 32, and 34.

The importance of prime numbers is that every natural number can be expressed as the product of primes.
For example,<BLOCKQUOTE>{{{4 = 2*2 = 2^2}}},
{{{6 = 2*3}}},
{{{8 = 2*2*2 = 2^3}}},
{{{9 = 3*3 = 3^2}}},
{{{10 = 2*5}}},
{{{12 = 2*2*3 = 2^2*3}}},
{{{14 = 2*7}}},
{{{15 = 3*5}}},
{{{16 = 2*2*2*2 = 2^4}}},
{{{18 = 2*3*3 = 2*3^2}}},
{{{20 = 2*2*5 = 2^2*5}}},</BLOCKQUOTE> and so on ...
So, the prime numbers are the building material to construct all natural numbers using multiplication.

The Fundamental Theorem of Arithmetic states that
<BLOCKQUOTE>Any natural number (except for 1) can be expressed as the product of primes. 
For each natural number such an expression is unique.</BLOCKQUOTE>

So, the Fundamental Theorem of Arithmetic consists of two statements.
First one says about the possibility of the factorization of any natural number as the product of primes.
The second one is about the uniqueness of such a factorization.

The proof of the Fundamental Theorem of Arithmetic is in the lesson <A HREF = http://www.algebra.com/algebra/homework/divisibility/Proof-of-Fundamental-Theorem-of-Arithmetic.lesson> Proof of Fundamental Theorem of Arithmetic</A> of this module.
Below we discuss the Theorem.

You may ask what the uniqueness of the factorization means.
Indeed, you can write the number 12 in two different ways as 12 = 2*2*3 and 12 = 2*3*2.
What exactly the uniqueness of the factorization means?

The uniqueness of the factorization doesn't mean that the order of primes in the product is unique.
It means that the set of participating primes is unique and the index (the multiplicity) of each participating prime 
is unique in this decomposition.

We can reformulate the Fundamental Theorem of Arithmetic saying that
<BLOCKQUOTE>every natural number N can be expressed as the product of primes
{{{N = p[1]^k[1]*p[2]^k[2]* ellipsis *p[n]^k[n]}}}.
For given N the set of primes {{{p[1]}}}, {{{p[2]}}}, ... , {{{p[n]}}} and the set of indexes {{{k[1]}}}, {{{k[2]}}}, ... , {{{k[n]}}} are unique.</BLOCKQUOTE>

Note that for a given natural number N the prime p participates in its factorization if and only if the prime p divides N 
(if and only if the prime p is a divisor of N).

Now, let us ask ourselves whether the set of prime numbers is finite or infinite?
The answer is:<BLOCKQUOTE>The set of primes is infinite.</BLOCKQUOTE>

This fact was just known to ancient Greece mathematicians. A remarkable proof was given by Euclid (third century B.C.) in one 
of his famous books Elements.

Let us assume that the set of all prime numbers is finite and consists, let say, of n primes
{{{p[1]}}}, {{{p[2]}}}, ... , {{{p[n]}}}.

Consider the integer number M = {{{p[1]*p[2]* ellipsis *p[n] + 1}}}.

This number is greater than 1 and greater than any of {{{p[i]}}}.
The number M is either prime or composite. Let us consider each of these two options.

If the number M is prime, then this prime number is out of the list of {{{p[1]}}}, {{{p[2]}}}, ... , {{{p[n]}}}, because it is greater than any of {{{p[i]}}}.
This contradicts to our assumption that there is no other primes than {{{p[1]}}}, {{{p[2]}}}, ... {{{p[n]}}}.

If the number M is composite, then, according to the Fundamental Theorem of Arithmetic, it can be expressed as the product of primes. 
Let P is any prime number of this decomposition. Then the prime P is a divisor of the integer M. Therefore, the prime P can not be equal to any 
of the numbers {{{p[1]}}}, {{{p[2]}}}, ... , {{{p[n]}}}, because no one of integers {{{p[i]}}} divides M. Indeed, if you divide M by any {{{p[i]}}}, you get the remainder equal to 1.
We again get contradiction to our assumption that there is no other primes than {{{p[1]}}}, {{{p[2]}}}, ... , {{{p[n]}}}.

Thus, the assumption that the set of all prime numbers is finite leads us to contradiction.
So, we must conclude that the set of prime numbers is infinite.
The proof is completed.