**Fundamental theorem of arithmetic**: Every positive integer n > 1can be expressed as a product of primes; this representation is unique, a part from the order in which the factors occur.

**Proof:** Either n is a prime or composite; in the former case, there is nothing more to prove. If n is composite, then there exists an integer d satisfying d\n and 1 < d < n. Among all such integers d, choose p_{1} to be the smallest

(this is possible by the well ordering principle)

. Then p_{1} must be a prime number. Otherwise it too would have a divisor q with 1 < q < q_{1}; but then q\p_{1}and p_{1}\n imply that q\n, which contradicts the choice of p_{1} as the smallest positive divisor, not equal to 1, of n.

We therefore may write n = p_{1}n_{1}, where p_{1} is rime and 1< n_{1} < n. If n_{1} happens to be a prime, then we have our representation. In the contrary case, the argument is repeated to produce to second prime number p_{2} such that n_{1} = p_{2}n_{2}; that is,

n = p_{1}p_{2} n_{2} 1 < n_{2} < n_{1}

## If n_{2 } is a prime, then it is not necessary go further. Otherwise, write n_{2} = p_{2}n_{3}, with p_{3} is a prime:

n = p_{1}p_{2}p_{3}n_{3} 1 < n_{3} < n_{2}

The decreasing sequence n > n_{1} > n_{2} > …>1

*Cannot continue indefinitely, so that after a finite number of steps n _{k-1} is a prime, call it p_{k}. This leads to the prime factorization*

n = p_{1}p_{2}…p_{k}

To establish the second part of the proof- the uniqueness of the prime factorization-let us suppose that the integer n can be represented as a product of primes in two ways; say,

n = p_{1}p_{2}…p_{r} = q_{1}q_{2}…q_{s} r ≤ s

where p_{i} and q_{j} are all primes, written in magnitude so that

p_{1} ≤ p_{2} ≤ … ≤ p_{r} q_{1} ≤ q_{2} ≤ …≤ q_{s}

Since p_{1}\q_{1}q_{2}…q_{s}, “ If p, q_{1}, q_{2}, …,q_{n} are all primes and p \q_{1}q_{2}…q_{n}, then p= q_{k} for some k, where 1 ≤ k ≤ n.” tells us that p_{1}= q_{k} for some k; but then p_{1 }≥ q_{1}. Similar reasoning gives q_{1} ≥ p_{1}, whence p_{1} = q_{1}. We may cancel this common factor and obtain

p_{2}p_{3}… p_{r} = q_{2}q_{3}…q_{s}

Now repeat the process to get p_{2} = q_{2} and in turn,

P_{3}p_{4}… p_{r} = q_{3}q_{4}…q_{s}

Continue in this fasion. If the inequality r < s were to hold, we would eventually arrive at

1 = q_{r+1}q_{r+2}…q_{s}

Which is absurd, because each q_{j} > 1. Hence, r = s and

P_{1} = q_{1} p_{2} = q_{2} ,….,p_{r} = q_{r}

Making the two factorization of n identical. The proof is now complete. **(Proved)**

**Corollary**: If p is a prime and p\a_{1}, a_{2}, …,a_{n}, then p\a_{k} for some k, where 1≤ k ≤ n.

**Proof:** We proceed by induction on n, the number of factors. When n = 1, the stated conclusion obviously holds, when n= 2 the result is the content of

“ if p is a prime and p\ab, then p\a or p\b.”.

Suppose, as the induction hypothesis, that n>2 and that whenever p divides a product of less than n factors, it divides at least one of the factors. Now let p \a_{1}a_{2}…a_{n}. From Theorem “ If p is a prime and p\ab, then p\a or p\b.”, either p\a_{1}a_{2}…a_{n-1}. If p\a_{n}, then we are through. As regards the case were

p\a_{1}a_{2}…a_{n-1}, *the induction hypothesis ensures that p\a _{k} for some choice of k*, with 1 ≤ k ≤ n-1. In any event, p divides one of the integers a

_{1}a

_{2}…a

_{n}.

**(Proved)**