Page 23 - DMTH403_ABSTRACT_ALGEBRA

Abstract Algebra

Notes For example, 2 and 3 are prime numbers, while 4 is a composite number.

Note that, if p is a prime number and a  Z such that p × A, then (p,a) = 1.
Now consider the number 50. We can write 50 = 2 × 5 × 5 as a ,product of primes. In fact we can
always express any natural number as a product of primes. This is what the unique prime
factorisation theorem says.
Theorem 10 (Unique Prime Factorisation Theorem): Every integer n > 1 can be written as
n = p .p ........ p , where p , ........ p are prime numbers. This representation is unique, except for
l
n
2
1
n
the order in which the prime factors occur.
Proof: We will first prove the existence of such a factorisation. Let P(n) be the statement that
n + l is a product of primes. P(1) is true, because 2 is a prime number itself.
Now let us assume that P(m) is true for all positive integers m < k. We want to show that P(k) is
true. If (k+l) is a prime, P(k) is true. If k+l is not a prime, hen we can write k + l = m, m , where
2
1 < m, < k + l and 1 < m < k + l. But then P(m – 1) and P(m – 1) are both true. Thus, m = p p . ....
2
l
2
2
1
l
p , m = q q .........q , where p ,p , .......P , q , q , .......q are primes. Thus,
1 2
2
r
s
l
l
r
s
2
2
k + 1 = p p ... p q q .... q , i .e., P(k) is true. Hence, by Theorem 6, P(n) is true for every n  N.
r
1
2
l
2
s
Now let us show that the factorisation is unique.
Let n = p p ... p, = q q ... q , where
2
2
1
l
s
p , p , ......p . q , q , ......, q are primes. We will use induction on t.
1
s
2
l
l
2
If t = 1, then p = q , q ....... q . But p is a prime. Thus, its only factors are 1 and itself.
1
1
s
2
1
Thus, s = 1 and p = q .
1
1
Now suppose t > 1 and the uniqueness holds for a product of t–1 primes. Now p | q q ......q and
1
1 2
s
hence, p | q for some i, By re-ordering q ....... q, we can assume that p | q . But both
1
1
i
1
1
p and q are primes. Therefore, p = q . But then p ..... p, = q ....... q,. So, by induction, t–1 = s–1
l
2
1
2
1
1
and p ,........ p are the same as q . ......q,, in some order.
t
2
2
Hence, we have proved the uniqueness of the factorisation.
The primes that occur in the factorisation of a number may be repeated, just as 5 is repeated in
the factorisation 50 = 2 × 5 × 5. By collecting the same primes together we can give the following
corollary to Theorem 10.
Corollary: Any natural number n can be uniquely written as n = p p 2 m2 .....P where for i = 1,
ml
mr
r
l
2, ....... r, each m  N and each p is a prime with 1 < p < p < .... < p,.
i i 1 2
As an application of Theorem 10, we give the following important theorem, due to the ancient
Greek mathematician Euclid.
Theorem 11: There are infinitely many primes.
Proof: Assume that the set P of prime numbers is finite, say
P = { p , p , .... p }. Consider the natural number
n
2
1
n = (p p ......... p ) + 1
n
1
2
Now, suppose some p | n. Then p | (n – p p ....... p,), i.e., p | 1, a contradiction.
i i 1 2 i
Therefore, no p divides n. But since n > 1, Theorem 10 says that n must have a prime factor. We
i
reach a contradiction. Therefore, the set of primes must be infinite.
16 LOVELY PROFESSIONAL UNIVERSITY