OpenCart Templates
Friday , July 28 2017
Home / Elementary Number Theory / Fundamental theorem of arithmetic

Fundamental theorem of arithmetic

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)

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *