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 p1 to be the smallest
(this is possible by the well ordering principle)
. Then p1 must be a prime number. Otherwise it too would have a divisor q with 1 < q < q1; but then q\p1and p1\n imply that q\n, which contradicts the choice of p1 as the smallest positive divisor, not equal to 1, of n.
We therefore may write n = p1n1, where p1 is rime and 1< n1 < n. If n1 happens to be a prime, then we have our representation. In the contrary case, the argument is repeated to produce to second prime number p2 such that n1 = p2n2; that is,
n = p1p2 n2 1 < n2 < n1
If n2 is a prime, then it is not necessary go further. Otherwise, write n2 = p2n3, with p3 is a prime:
n = p1p2p3n3 1 < n3 < n2
The decreasing sequence n > n1 > n2 > …>1
Cannot continue indefinitely, so that after a finite number of steps nk-1 is a prime, call it pk. This leads to the prime factorization
n = p1p2…pk
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 = p1p2…pr = q1q2…qs r ≤ s
where pi and qj are all primes, written in magnitude so that
p1 ≤ p2 ≤ … ≤ pr q1 ≤ q2 ≤ …≤ qs
Since p1\q1q2…qs, “ If p, q1, q2, …,qn are all primes and p \q1q2…qn, then p= qk for some k, where 1 ≤ k ≤ n.” tells us that p1= qk for some k; but then p1 ≥ q1. Similar reasoning gives q1 ≥ p1, whence p1 = q1. We may cancel this common factor and obtain
p2p3… pr = q2q3…qs
Now repeat the process to get p2 = q2 and in turn,
P3p4… pr = q3q4…qs
Continue in this fasion. If the inequality r < s were to hold, we would eventually arrive at
1 = qr+1qr+2…qs
Which is absurd, because each qj > 1. Hence, r = s and
P1 = q1 p2 = q2 ,….,pr = qr
Making the two factorization of n identical. The proof is now complete. (Proved)
Corollary: If p is a prime and p\a1, a2, …,an, then p\ak 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 \a1a2…an. From Theorem “ If p is a prime and p\ab, then p\a or p\b.”, either p\a1a2…an-1. If p\an, then we are through. As regards the case were
p\a1a2…an-1, the induction hypothesis ensures that p\ak for some choice of k, with 1 ≤ k ≤ n-1. In any event, p divides one of the integers a1a2…an. (Proved)