Basic logic and number theory chapter 12 PDF

Preview

Summary

This is a detailed note for basic mathematics and number theory and its very helpful for every students....

Description

Chapter

12

The Fundamental Theorem of Arithmetic Definition An integer c is said to be a common multiple of two nonzero integers a and b whenever a|c and b|c. Examples 1. 0 is a common multiple of a and b. 2. The products ab and −(ab) are both common multiples of a and b. By the Well-Ordering Principle of natural numbers, the set of all positive common multiples of a and b must contain a smallest integer. Theorem 1 (Euclid) If p is a prime and p|ab, then p|a or p|b.

175

176

The Fundamental Theorem of Arithmetic

Proof If p|a, there is nothing to prove. So let us assume that p ∤ a. Then we have to show that p|b. Because the only positive divisors of p are 1 and p itself, this implies that (p, a) = 1. i.e., we have now p|ab and (p, a) = 1, this using Euclid’s lemma, implies p|b . This completes the proof. Theorem 1 easily extends to product of more than two terms. This is the content of the next result. Corollary 1 If p is a prime and p|a1 a2 · · · an , then p|ai for some i, where 1 ≤ i ≤ n. Proof We proceed by induction on n, the number of factors. When n = 1, the stated conclusion obviously holds; whereas when n = 2, the result is the content of Theorem 1. 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|a1 a2 · · · an . From Theorem 1 either p|an or p|a1 a2 · · · an−1 . If p|an , then we are through. As regards the case where p|a1 a2 · · · an−1 , the induction hypothesis ensures that p|ai for some choice of i, with 1 ≤ i ≤ n − 1. In any case, p divides one of the integers a1 , a2 , . . . , an . Corollary 2 If p, q1 , q2 , . . . , qn are all primes and p|q1 q2 . . . qn , then p = qi for some i, where 1 ≤ i ≤ n. Proof By the help of Corollary 1 we know that p|qi for some i, with1 ≤ i ≤ n.

The Fundamental Theorem of Arithmetic

177

Being a prime, qi is not divisible by any positive integer other than 1 or qi itself. Because p > 1, we are forced to conclude that p = qk . Theorem 2 (Fundamental Theorem of Arithmetic) Every positive integer n > 1 can be expressed as a product of primes; this representation is unique, apart from the order in which the factors occur. Proof Either n is a prime or it is composite. If n is a prime, 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 < p1 ; but then q|p1 and 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 = p1 n1 ,wherep1 is prime 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 a second prime number p2 such that n1 = p2 n2 ; that is, n = p1 p2 n2 where 1 < n2 < n1 . If n2 is a prime, then it is not necessary to go further. Otherwise, write n2 = p3 n3 , with p3 a prime: n = p1 p2 p3 n3 where 1 < n3 < n2 . The decreasing sequence n > n1 > n2 > · · · > 1

178

The Fundamental Theorem of Arithmetic

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 = p1 p2 · · · pk . To prove 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 = p1 p2 · · · pr = q1 q2 · · · qs wherer ≤ s where the pi and qj are all primes, written in increasing magnitude so that p1 ≤ p2 ≤ · · · ≤ pr and q1 ≤ q2 ≤ · · · ≤ qs . Because p1 |q1 q2 · · · qs , Corollary 2 of Theorem 1 tells us that p1 = qk for some k; but then p1 ≥ q1 . Similar reasoning gives q1 ≥ p1 . Combining these, we have p1 = q1 . We may cancel this common factor and obtain p2 p3 · · · pr = q2 q3 · · · qs . Now repeat the process to get p2 = q2 and, in turn, p3 p4 · · · pr = q3 q4 · · · qs Continue in this fashion. If the inequality r < s were to hold, we would eventually arrive at 1 = qr+1 qr+2 · · · qs which is not possible, because each qj > 1.

The Fundamental Theorem of Arithmetic

179

Hence, r = s and p1 = q1 and p2 = q2 , . . . , pr = qr making the two factorizations of n identical. This completes the proof. Of course several of the primes that appear in the factorization of a given positive integer may be repeated, as is the case with 360 = 2 · 2 · 2 · 3 · 3 · 5. By collecting like primes and replacing them by a single factor we can rephrase, Theorem 2 as below. Remark By the above theorem every composite number n can be factored into primes. Such a factorization is called a prime factorization of n. For example, 5544 = 2 · 2 · 3 · 7 · 2 · 11 · 3. . . (1) i.e. 5544 = 23 · 32 · 7 · 11 . . . (2) the factorization in Eq.(2) is called Prime-power decomposition of n. If the primes occurring in Eq.(2) is of increasing order then it is called the canonical decomposition. Canonical Decomposition The canonical decomposition of a positive integer n is of the form n = pa11 pa22 · · · pkak , where p1 , p2 , . . . , pk are distinct primes with p1 < p2 < · · · < pr and each exponent ai is a positive integer. There are two different techniques for finding the canonical decomposition. We illustrates this by the following examples. Example 1 Find the canonical decomposition of 2520. Solution

180

The Fundamental Theorem of Arithmetic

Beginning with the smallest prime 2, since 2|2520, 2520 = 2 · 1260. Now 2 is a factor of 1260, so 2520 = 2·2·630; 2|630 again, so 2520 = 2·2·2·315. Now 2 ∤ 315, but 3 does, so 2520 = 2 · 2 · 2 · 3 · 105; 3 is a factor of 105 also, so 2520 = 2 · 2 · 2 · 3 · 3 · 35. Continuing like this we get 2520 = 2 · 2 · 2 · 3 · 3 · 5 · 7 = 23 · 32 · 5 · 7 which is the desired canonical decomposition. Example 2 Find the canonical decomposition of 2520, by Method 2. Solution Notice that 2520 = 40 · 63. Since none of the factors are primes, split them again: 40 = 4 · 10 and 63 = 7 · 9, so 2520 = (4 · 10) · (7 · 9). Since 4, 10, and 9 are composites, split each of them: 2520 = (2 · 2)(2 · 5)(7)(3 · 3). Now all the factors are primes, so the procedure stops. Rearranging them yields the canonical decomposition: 2520 = 23 · 32 · 5 · 7. Finding Trailing Zeros It can be seen that 9!=362,880 has one trailing zero, while 11!=39,916,800 has two trailing zeros. We now apply the fundamental theorem of arithmetic and the floor function to determine the number of trailing zeros in the decimal value of n!, without computing it. We note that each trailing zero corresponds to a factorization by 10. So the number of trailing zeros is k if and only if k is the largest positive integer such that 10k is factorization by 10. Example 3 Find the number of trailing zeros in 112!.

The Fundamental Theorem of Arithmetic

181

Solution By the fundamental theorem of arithmetic, we can factorize 112! by prime numbers and we write 112! in the form 112! = 2a 5b c, where a and b are positive integers and c denotes the product of primes other than 2 and 5 (Note: Here c is not a prime, but a product of prime factors of 112! other than 2 and 5). We note that 112! is the product of positive integers from 1 to 112; among those integers, multiples of 2 up to 112 and multiplies of 5 up to 112 are included. It can be seen that number of multiples of 2 are greater than number of multiples of 5. Hence while factorizing by prime number, 112 has more 2s than 5s. Hence a > b. Each trailing zero in 112! corresponds to a 10 in a factorization and vice versa; each 10 is the product of a 2 and a 5. Hence the numbers 10s corresponds to the number of products of the form 2 · 5 in a prime factorization of 112!. Since a > b it follows that number of products of the form 2 · 5 in a prime factorization of 112!. is b. Hence the number of trailing is zeros is b. To find b, we proceed as follows: No. of positive integers ≤ 112 and divisible by 5 = ⌊112/5⌋ = 22 Each of them contributes a 5 to the prime factorization of 112!. No. of positive integers ≤ 112 and divisible by 25 = ⌊112/25⌋ = 4 Each of them contributes an additional 5 to the prime factorization of

182

The Fundamental Theorem of Arithmetic

112!. No higher power of 5 contributes a 5 to the prime factorization of 112!, so the total number of 5s in the prime factorization equals 22 + 4 = 26. Thus, 112! has 26 trailing zeros. Remark By the above example, the highest power b of 5 such that 5b divides 112! is given by b = ⌊112/5⌋ + ⌊112/25⌋ = 22 + 4 = 26.    In the above summands we haven’t considered ⌊112/125⌋ = 112 53 ,   4 112 5 , and so on, as their values are 0, because 125, 54 are greater than 112.

This method is applicable in general. For the highest power h of a prime p such that ph divides n! is given by       h = ⌊n/p⌋ + n p2 + · · · + n pk−1    where k is the smallest positive such that pk > n so that n pk = 0,   k+1  = 0, and so on. n p Example 4 Find the largest power of 3 that divides 207! . Solution We note that 5 is the smallest positive such that 35 = 243 > 207 so       that 207 35 = 0, 207 36 = 0, and so on. Hence the largest power h

of 3 that divides 207! is

         h = ⌊207/3⌋ + 207 32 + 207 33 + 207 34

The Fundamental Theorem of Arithmetic

183

= 69 + 23 + 7 + 2 = 101 Example 5 Find the largest power of 2 that divides 109! . Solution We note that 7 is the smallest positive such that 27 = 128 > 109 so       that 109 27 = 0, 109 28 = 0, and so on. Hence the largest power h

of 2 that divides 109! is

k k j k j k j j k j 6 5 4 3 2 h = ⌊109/2⌋ + 109/2 + 109/2 + 109/2 + 109/2 + 109/2 = 54 + 27 + 13 + 6 + 3 + 1 = 104 Theorem 3 Let h denote the highest power of 2 that divides n! and b the number of 1s in the binary representation of n. Then n = h + b. Example 6 We have see that the highest power of 2 that divides n! = 109! is h = 104. Using the Division Algorithm, the binary representation of n = 109is obtained as follows: 109 = 54 · 2 + 1 54 = 27 · 2 + 0 27 = 13 · 2 + 1 13 = 6 · 2 + 1

184

The Fundamental Theorem of Arithmetic 6=3·2+0 3=1·2+1 1=0·2+1

Hence the integer 109 can be written as 109 = 1 · 26 + 1 · 25 + 0 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 Writing the remainders from bottom to left, as numbers from left to right we obtain (109)2 = 1101101. [Aliter: Also writing the remainders from bottom to left, as numbers from left to right we obtain (109)2 = 1101101.] There are five 1s here. Also n = 109 = 104 + 5 = h + b. Hence the theorem is verified. Example 7 Using the canonical decompositions of 720 and 3528, ?nd their gcd. Solution It can be seen that 720 = 24 · 32 · 5 and 3528 = 23 · 32 · 72 . The only common prime factors are 2 and 3, so 5 or 7 cannot appear

The Fundamental Theorem of Arithmetic

185

in their gcd. Since 2 appears four times in the canonical decomposition of 720, but only thrice in the canonical decomposition of 3528, 23 is a factor in the gcd. Similarly, 32 is also a common factor, so (720, 3528) = 23 · 32 = 72. Theorem 4 Let a and b be positive integers with the following canonical decompositions: b a = p1a1 pa22 · · · pnan and b = p11 pb22 · · · pbnn

where ai ≥ 0, bi ≥ 0 (i = 1, 2, . . . , n)(We note that some primes will not be a factor of either of a or b, but not both. Then what we do is ensure that the exponents of such primes are zero. Thus, we can always assume that both decompositions contain exactly the same prime bases pi .) Then min{a1 , b1 } min{a2 , b2 } · · · pnmin{an , bn }. p2

(a, b) = p 1 For example,

720 = 24 · 32 · 51 · 70 and 3528 = 23 · 32 · 50 · 72 . Hence (720, 3528) = 2min{4, 3} · 3min{2, 2} · 5min{1, 0} · 7min{0, 2} = 23 · 32 · 50 · 70 = 8 · 9 · 1 · 1 = 72 as obtained above. Distribution of Primes Revisited By the division algorithm, every integer is of the form

186

The Fundamental Theorem of Arithmetic

4n + r, where r = 0, 1, 2, or 3; so every odd integer is of the form 4n + 1 or 4n + 3. For instance, 17 and 29 are of the form 4n + 1 :17 = 4 · 4 + 1 and 29 = 4 · 7 + 1, whereas 15 and 35 are of the form 4n + 3 :15 = 4 · 3 + 3 and 35 = 4 · 8 + 3. Theorem 5 The product of any two integers of the form 4n + 1 is also of the same form. Proof Let a and b be any two integers of the form 4n + 1, say, a = 4p + 1 and b = 4q + 1 for some integers p and q. Then ab = (4p + 1)(4q + 1) = 16pq + 4p + 4q + 1 = 4(4pq + p + q) + 1 = 4k + 1 wherek = 4pq + p + q is an integer. Thus, ab is also of the form 4n + 1. This completes the proof.? Remark This result can be extended to any ?nite number of such integers. Theorem 6 There are in?nitely many primes of the form 4n + 3. Proof The proof looks similar to Euclid’s proof, which established the infinitude of primes. (by contradiction) Suppose there are only finitely many primes of the form 4n + 3, say, p0 , p1 , . . . , pk , where p0 = 3 and p0 < p1 < · · · < pk . Consider the

187

The Fundamental Theorem of Arithmetic positive integer N = 4 p1 p2 · · · pk + 3. Clearly, N > pk and is also of the form 4n + 3.

Case 1: If N itself is a prime, then N would be larger than the largest prime pk of the form 4n + 3, which is a contradiction. Case 2: Suppose N is composite. Since N is odd, every factor of N is of the form 4n + 1or 4n + 3. If every factor is of the form 4n + 1, then, by the previous theorem, N would also be of the form 4n + 1. But, since N is of the form 4n + 3, at least one of the prime factors, say, p, must be of the form 4n + 3. Case 2a) Let p = p0 = 3. Then 3|N. Now, so 3|N and 3|3, so using the result “ a|band a|c implies a|αb + βc” it follows with a = 3, α = 1, b = N,β = −1, c = 3 that 3|(N − 3). i.e., 3|(4 p1 p2 · · · pk + 3 −3) i.e., | {z } N

3|4 p1 p2 · · · pk .i.e., 3|2 · 2 · p1 p2 · · · pk . Now using the result “Let p be

a prime and p|a1 a2 · · · an , where a1 , a2 , . . . , an are positive integers, then p|ai for some i, where 1 ≤ i ≤ n” it follows that 3|2 or 3|pi , where 1 ≤ i ≤ k, but both are impossible. Case 2b) Let p = pi , where 1 ≤ i ≤ k. Then p|N and p|4 p1 p2 · · · pk , so p|(N − 4 p1 p2 · · · pk ), that is, p|(4 p1 p2 · · · pk + 3 −4 p1 p2 · · · pk ), i.e., p|3 | {z } which is again a contradiction.

N

Both cases lead us to a contradiction, so our assumption must be false. Thus, there is an infinite number of primes of the given form. This completes the proof. Theorem 7 There are infinitely many primes of the form 4n + 1.

188

The Fundamental Theorem of Arithmetic

Theorem 8 (Dirichlet’s Theorem) If a and b are relatively prime, then the arithmetic sequence a, a + b, a + 2b, a + 3b, . . . contains in?nitely many primes. Special Cases: 1. By taking a = 3 and b = 4, we have there are infinitely many primes of the form 4n + 3. 2. By taking a = 1and b = 4, we have there are infinitely many primes of the form 4n + 1. Exercises Find the canonical decomposition of each composite number. 1. 1947

2.1976

3. 1863

4.227+1

Find the gcd of each pair, where p, q and r are distinct primes. 5. 23 · 3 · 5, 2 · 32 · 53 · 72 6. 24 · 32 · 75 , 34 · 5 · 112 7. p2 q 3 , pq 2 r 8. p3 qr3 , p3 q 4 r5 Prove each of the following 9. if p|an then p|a 10. The product of any n integers of the form 4k + 1is also of the same form. 11. There are infinitely many primes of the form 2n + 3 12. Every positive integer n can be written as n = 2e m, where e ≥ 0 and m is an odd integer.

The Fundamental Theorem of Arithmetic

189

13. A positive integer n is called square-full or powerful, if p2 |nfor every prime factor p of n. If n is square-full, show that it can be written in the form n = a2 b3 ,with a and b positive integers 14. An integer is said to be square-free if it is not divisible by the square of any integer greater than 1. (As an example, 6 is square free while 36 is not.) Prove the following: (a) An integer n > 1 is square-free if and only if n can be factored into a product of distinct primes. (b) Every integer n > 1 is the product of a square-free integer and a perfect square....