Math1081 topic 2 notes with answers PDF

Preview

Summary

F. Kuo/T. Britz/D. Chan/D. Trenerry/C. Greenhill MATH1081 Discrete Mathematics §2 Integers, Modular Arithmetic, and Relations FACTORISATION We recall the commonly-used sets in our number system: Positive integers Z+ = {1, 2, 3, . . .}. Natural numbers N = {0, 1, 2, 3, . . .}. Integers Z = {. . . , −...

Description

F. Kuo/T. Britz/D. Chan/D. Trenerry/C. Greenhill

MATH1081 Discrete Mathematics

§2 Integers, Modular Arithmetic, and Relations FACTORISATION We recall the commonly-used sets in our number system: Positive integers Z+ = {1, 2, 3, . . .}.

Natural numbers N = {0, 1, 2, 3, . . .}.

Integers Z = {. . . , −2, −1, 0, 1, 2, . . .}.    Rational numbers Q = p  p, q ∈ Z, q 6= 0 . q

Real numbers R (includes Q and irrational numbers such as

√

2, π , e).

Note that Z+ ⊆ N ⊆ Z ⊆ Q ⊆ R. Number theory focuses on Z and its subsets. We can add, multiply, subtract, and divide in Q and R, / Z. but we cannot always divide in Z; for instance, 23 ∈ Let a and b be integers. If there is an integer m such that b = am, then we say b is a multiple of a, a is a factor or divisor of b, a divides b, b is divisible by a, am is a factorisation of b and we write a | b. We write a ∤ b if a does not divide b. If a and b are positive integers and a | b then we must have a ≤ b. a| b (“a divides b”) is a statement about divisibility that is either true or false. a (“a divided by b”) is a number that we get by carrying out division. b Be careful not to confuse the divisibility symbol a | b with division: a/b or ab . Divisibility by zero is well-defined but mostly pointless, since 0 | b only holds when b = 0.

Exercise. Compare the following notations. 12 = 0.25 12 | 48 true 12/48 = 0.25 48 48 48/12 = 4 =4 48 | 12 false 12

12 ∤ 48 false 48 ∤ 12 true

Properties of divisibility: Let a, b, and c be integers. Then (i) a | 0 ;

(Each integer is a factor of 0 and 0 is a multiple of every integer.)

(ii) if a | b then a | bc ;

(iii) if a | b and a | c then a | (b + c) ;

(iv) if a | b and a | c then a | (sb + tc) for all integers s and t ; (Important!) (v) if a | b and b | c then a | c.

(Transitivity of divisibility)

Proof. (v) Suppose that a | b and b | c. Then b = am and c = bn for some integers m and n. Thus, we have c = bn = (am)n = a(mn) = ak, where k = mn is an integer. Hence, a | c. (i) 0 = a × 0. Thus, a | 0. Exercise. Prove (ii)-(iv). (ii) Suppose that a | b. Then b = am for some integer m. Therefore, bc = (am)c = a(mc) = ak, where k = mc is an integer. Hence, a | bc. (iv) Suppose that a | b and a | c. Then b = am and c = an for some integers m and n. Thus, we have sb + tc = s(am) + t(an) = a(sm + tn) = ak , where k = sm + tn is an integer. Hence, a | (sb + tc). (iii) Just put s = t = 1 in (iv).

Simple divisibility tests: 2 3 4 5 6 7

Last digit is 0, 2, 4, 6, or 8. Sum of digits is divisible by 3. Last two digits form a number which is divisible by 4. Last digit is 0 or 5. Divisible by 2 and 3. Double the last digit and subtract it from the remaining leading truncated number. If the result is divisible by 7 then so was the original number. Apply this rule over and over again as necessary. 8 Last three digits form a number which is divisible by 8. 9 Sum of digits is divisible by 9. 10 Last digit is 0. 11 The difference between the sum of digits in the odd positions and the sum of digits in the even positions is divisible by 11. .. .

Exercise. Is 408254 a multiple of 3? Is 408254 divisible by 7? Does 11 divide 408254? 4 + 0 + 8 + 2 + 5 + 4 = 23, which is not a multiple of 3. Thus, 408254 is not a multiple of 3. 40825 − 8 = 40817; 4081 − 14 = 4067; 406 − 14 = 392; 39 − 4 = 35. Since 35 is divisible by 7, we conclude that 408254 is also divisible by 7. 4 + 8 + 5 − 0 − 2 − 4 = 11 which is divisible by 11. We conclude that 11 divides 408254.

An even number is an integer that is divisible by 2, so can be written as n = 2k for some integer k . An odd number is an integer that is not an even number so can be written as n = 2k + 1 for some integer k.

A prime is an integer larger than 1 whose only positive factors are 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . .. There are infinitely many primes; this has been known for over two thousand years. Primes of the form 2p − 1, where p is prime, are called Mersenne primes . The largest prime currently known (26 February 2018) is a Mersenne prime, 277,232,917 − 1, discovered in December 2017. It has 23,249,425 digits. Check out GIMPS for the latest information. n

Primes of the form 22 + 1 are known as Fermat primes. Only five Fermat primes are known: 3, 5, 17, 257, 65537. Twin primes are pairs of primes that differ by 2, such as 3 and 5, 5 and 7, 11 and 13, 17 and 19, and 1000000000061 and 1000000000063. There are thought to be infinitely many twin primes but no proof exists. An integer greater than 1 that is not a prime is called a composite number. 1 is neither prime nor composite.

The Fundamental Theorem of Arithmetic. Any positive integer n has a prime factorization, that is, can be expressed as a product of primes n = p1α1pα2 2 · · · pαk k

for distinct primes p1 , p2 , . . . , pk and exponents α1 , α2 , . . . , αk ∈ Z+, k ≥ 0. The factorisation is unique up to permuting factors. A prime number is a product of just one prime, namely itself. 1 is a product of no primes. Any positive divisor d of the above n has prime factorisation d = p1β1 pβ22 · · · pβkk , for some integers β1 , . . . , βk such that 0 ≤ β1 ≤ α1 , . . . , 0 ≤ βk ≤ αk . Example. 1000 = 23 × 53 ;

1001 = 7 × 11 × 13 ;

1002 = 2 × 3 × 167 .

Algorithm to find the prime factorisation of n: If n is prime, we are done. Otherwise, we can factorise n = ab with a, b positive factors not equal to 1. Repeat procedure with a and b. Exercise. Find the prime factorisation of 345 and all its positive factors. 345 = 3 × 115 = 3 × 5 × 23 Positive factors are:

1, 3, 5, 23, 3 × 5 = 15, 3 × 23 = 69, 5 × 23 = 115, 3 × 5 × 23 = 345

How do we determine whether or not a given positive integer n is prime? The obvious way to do this is to check whether n is a multiple of any of the n − 2 numbers 2, 3, . . . , n − 1. If none of these is a factor then n is prime; if any of them is a factor then n is composite. It is enough to check only the primes among these n−2 numbers. (Why?) √ It is enough to check only the primes up to n. (See below.) There are faster primality tests. (See MATH2400 and MATH3411.) Theorem. If n is composite then n has a prime factor at most equal to

√

n.

Equivalently... Theorem. If n has no prime factor less than or equal to

√

n then it is prime.

Proof. Let n > 2 be composite. Then n = ab with 1 < a < n√and 1 < b < n. Note that one of a or b must be less than or equal to n because otherwise we would have ab > n. √ Suppose without loss of generality that a ≤ n. If a is prime then we have √ found a prime factor of n that is less than or equal to n. If a is composite then √ a has a prime factor p. In this case, p is a prime factor of n with p ≤ a ≤ n. Exercise. Is 161 prime? Is 163 prime? Because 132 = 169, we only need to check the primes 2, 3, 5, 7, 11. 161 = 7 × 23 is not a prime. 163 is prime.

Let a and b be integers, not both zero. Any positive integer d that satisfies d | a and d | b is called a common divisor or a common factor of a and b. The largest such d is called the greatest common divisor of a and b, and is denoted by gcd(a, b). If gcd(a, b) = 1 then a and b are coprime or relatively prime to each other. Let a and b be positive integers. Each positive integer m that satisfies both a | m and b | m is called a common multiple of a and b. The smallest such m is called the least common multiple of a and b, and is denoted by lcm(a, b). If a and b are positive integers then gcd(a, b) × lcm(a, b) = ab. Example. The positive divisors of 12 are {1, 2, 3, 4, 6, 12}. The positive divisors of 42 are {1, 2, 3, 6, 7, 14, 21, 42}. The common divisors of 12 and 42 are {1, 2, 3, 6}. Thus, gcd(12, 42) = 6. The positive multiples of 12 are {12, 24, 36, 48, 60, 72, 84, . . . }. The positive multiples of 42 are {42, 84, 126, . . .}. Thus, lcm(12, 42) = 84. Example. Since prime factorisation can be used to find all divisors of an integer, it can also be used to find the gcd and lcm of two numbers. For example, consider 14175 = 34 × 52 × 7

and

16758 = 2 × 32 × 72 × 19 .

For the gcd, we multiply all the prime factors common to both: gcd(14175, 16758) = 32 × 7 = 63 . For the lcm, take the smallest product that includes all factors of both numbers: lcm(14175, 16758) = 2 × 34 × 52 × 72 × 19 = 3770550 . Exercise. Find the gcd and lcm of a = 23 × 3 × 52 × 11 and b = 3 × 5 × 7. gcd(a, b) = 3 × 5 = 15

and

lcm(a, b) = 23 × 3 × 52 × 7 × 11 .

Exercise. Suppose that a is positive and is a factor of b. What is gcd(a, b)? gcd(a, b) = a Exercise. What happens if we try to compute gcd(0, 0)? gcd(0, 0) is undefined, because every integer is a factor of 0 and we cannot establish the largest one.

a b Exercise. What is d = gcd( gcd(a,b) , gcd(a,b) )? a Now d divides gcd(a,b) , so d × gcd(a, b) divides a. Similarly, d × gcd(a, b) divides b, and hence d × gcd(a, b) is a common divisor of a and b. But gcd(a, b) is the greatest common divisor of a and b, which implies that gcd(a, b) ≥ d × gcd(a, b). Therefore d = 1.

Dividing by the gcd “removes” the common divisor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Now try Problem Set 2, Questions 1–5. EUCLIDEAN ALGORITHM & INTEGER ARITHMETIC A key tool in integer arithmetic is The Division Algorithm. Let a be an integer and b be a positive integer. Then there is a unique pair of integers q and r (called quotient and remainder ) such that a = q b + r and 0 ≤ r < b. Proof. See textbook [Epp, Section 4.4 and Exercise 18 of Section 3.7]. We see that 92 = 13 × 7 + 1.

Thus, when 92 is divided by 7, the quotient is 13 and the remainder 1.

We have −92 = (−13) × 7 +(−1) and −92 = (−14) ×7+ 6. Since the remainder should lie between 0 and 6, we conclude that when −92 is divided by 7, the quotient is −14 and the remainder 6.

Example. We can find the quotient and remainder by long division or by repeated subtraction. For example, we divide 92 and −92 by 7. 13 7 ) 92 7 22 21 1 long division

13 7 ) 92 91 1

−13 7 ) −92 −91 −1

−14 7 ) −92 −98 6

simplified

incorrect

correct

Exercise. Find the quotient and remainder when −1001 is divided by 101. −1001 = (−10) × 101 + 9. Thus, the quotient is −10 and the remainder is 9. Theorem. Let a, b, q, and r be integers such that a = q b + r, where a and b are not both zero. Then gcd(a, b) = gcd(b, r).

Proof. Write d1 = gcd(a, b) and d2 = gcd(b, r). Since d2 | b and d2 | r, we have d2 | (q b + r) and thus d2 | a. Thus d2 is a common divisor of a and b. But since d1 is the greatest common divisor of a and b, we must have d2 ≤ d1 . Conversely, we can write r = a − q b. Since d1 | a and d1 | b, we have d1 | (a − q b) and thus d1 | r. This shows that d1 is a common divisor of b and r, and hence d1 ≤ d2 .

Since d2 ≤ d1 and d1 ≤ d2 , we conclude that d1 = d2 .

Euclidean Algorithm. Use the above theorem together with the Division Algorithm repeatedly to calculate the greatest common divisor of two numbers. Note that we undeline a, b, r and the successive remainders as we need to keep track of them, particularly later.

Example. We use the Euclidean Algorithm to compute the greatest common divisor of 16758 and 14175 as follows: 16758 = 1 × 14175 + 2583, so gcd(16758, 14175) = gcd(14175, 2583). 14175 = 5 × 2583 + 1260, so gcd(14175, 2583) = gcd(2583, 1260). 2583 = 2 × 1260 + 63, so gcd(2583, 1260) = gcd(1260, 63). 1260 = 20 × 63 + 0, thus 63 | 1260 and so gcd(1260, 63) = 63. Hence, gcd(16758, 14175) = 63. Moreover, we have 16758 × 14175 lcm(16758, 14175) = = 3770550 . gcd(16758, 14175) Exercise. Use the Euclidean Algorithm to find gcd(854, 651). 854 651 203 42 35

= = = = =

1 × 651 + 203 3 × 203 + 42 4 × 42 + 35 1 × 35 + 7 5 × 7 +0.

We can use the Euclidean Algorithm to find an integer solution x and y to the equation ax + by = gcd(a, b) . This is done by working backward through the Euclidean Algorithm; this process is known as the Extended Euclidean Algorithm. Example. We look for an integer solution of x and y to the equation 16758 x + 14175 y = 63 . Recall that we obtained gcd(16758, 14175) = 63 by the Euclidean Algorithm: 16758 14175 2583 1260

= = = =

1 × 14175 + 2583 5 × 2583 + 1260 2 × 1260 + 63 20 × 63 + 0 .

(3) (2) (1)

We work backwards, re-writing the remainders using (1)–(3): 63 = = = = = Thus,

2583 − 2 × 1260 2583 − 2 (14175 − 5 × 2583) 11 × 2583 − 2 × 14175 11 (16758 − 14175) − 2 × 14175 11 × 16758 − 13 × 14175

by equation (1) by equation (2) collect like terms by equation (3) collect like terms .

16758 × 11 + 14175 × (−13) = 63 .

Hence, 16758x + 14175y = 63 has an integer solution x = 11 and y = −13. Doubling this equation we see that 16758x + 14175y = 126 has an integer solution x = 22 and y = −26, since 16758 × (11×2) + 14175 × (−13×2) = 63×2.

Tripling this equation we see that 16758x + 14175y = 189 has an integer solution x = 33 and y = −39, since 16758 × (11×3) + 14175 × (−13×3) = 63×3.

However, 16758x + 14175y = 60 has no integer solution, since 63 ∤ 60 but 63| LHS.

We generalise these examples as follows: The B´ ezout Property. Consider the equation ax + by = c , where a, b, and c are integers, with a and b not both zero. (i) If c = gcd(a, b) then the equation has integer solutions; (ii) If c = k gcd(a, b) for some k ∈ Z then the equation has integer solutions. In fact: if (x, y ) = (x0 , y0 ) is a solution to ax + by = gcd(a, b) then (x, y) = (kx0 , ky0 ) is a solution to ax + by = k gcd(a, b). (iii) If c is not a multiple of gcd(a,b) then the equation has no integer solution.

Proof of (iii) Let d = gcd(a, b). By assumption, c is not a multiple of d. For a contradiction, suppose that x, y are integers such that ax + by = c. Then d divides both a and b, so d divides the LHS. Hence d must also divide the RHS; that is, d divides c. But this contradicts our assumption that c is not a multiple of d. It follows that there are no integer solutions to ax + by = c, proving (iii). Exercise. Use the Extended Euclidean Algorithm to find integer solutions to the equations a) 520x − 1001y = 13,

b) 520x − 1001y = −26, and

c) 520x − 1001y = 1.

Note that we solve 520x + 1001z = 13 then put y = −z . 1001 = 1 × 520 + 481 13 = 481 − 12 × 39 520 = 1 × 481 + 39 = 481 − 12 (520 − 481) 481 = 12 × 39 + 13 = 13 × 481 − 12 × 520 39 = 3 × 13 + 0 = 13 (1001 − 520) − 12 × 520 = 13 × 1001 − 25 × 520 . . . . . . . . . . . . . . . . . . . . . . Now try Problem Set 2, Questions 9, 11 and 12.

MODULAR ARITHMETIC Recall the Division Algorithm: If a is an integer and m is a positive integer then there exist unique integers q and r, called the quotient and the remainder, respectively, such that a = q m + r and 0 ≤ r < m. We define a mod m (reads “a modulo m”) to be this remainder r. We essentially “ignore” multiples of the modulus m. Exercise. Evaluate 11 mod 3 = 2

5 mod 7 = 5

− 11 mod 3 = 1

− 5 mod 7 = 2

Let m be a positive integer. Two integers a and b are congruent modulo m, denoted by a ≡ b (mod m), if (a mod m) = (b mod m), that is, if a and b have the same remainder when divided by m. Example. Any two odd numbers are congruent modulo 2. Equivalent definitions of congruence: (i) a ≡ b (mod m),

(ii) (a mod m) = (b mod m), (iii) m | (a − b),

(iv) a = b + km for some integer k. Proof. (i) and (ii) are equivalent by definition. (iii) and (iv) are equivalent by definition. Let us prove that (ii) implies (iii). Suppose that (a mod m) = (b mod m) = r for some integer 0 ≤ r < m. Then a = q1 m + r and b = q2 m + r for some integers q1 and q2 . Thus, a − b = (q1 m + r) − (q2 m + r) = (q1 − q2 )m = km , where k = q1 − q2 is an integer. Hence, we have m | (a − b).

Finally, let us prove that (iv) implies (ii). (Why does this prove the result?) Suppose a = b + km and (a mod m) = r for integers k and r with 0 ≤ r < m. Then we have a = qm + r for some integer q, and b = a − km = (qm + r) − km = (q − k)m + r = ℓm + r , where ℓ = q − k is an integer. Hence, we have (b mod m) = r = (a mod m).

This concludes the proof.

Properties of congruence: If a ≡ b (mod m) and c ≡ d (mod m) then (i) a + c ≡ b + d (mod m);

(ii) a − c ≡ b − d (mod m);

(iii) ac ≡ bd (mod m);

(iv) an ≡ bn (mod m) for all n ≥ 0;

(v) ℓa ≡ ℓb (mod m) for all integers ℓ;

(vi) a ≡ b (mod n) for all integers n satisfying n | m. Proof. Suppose that a = b + k1 m and c = d + k2 m for some integers k1 and k2 . (i) Then a + c = (b + k1 m) + (d + k2 m) = (b + d) + (k1 + k2 )m = (b + d) + km, where k = k1 + k2 is an integer. Thus, a + c ≡ b + c (mod m). (ii) Similar to (i). (iii) We have

ac = (b + k1 m)(d + k2 m) = bd + (bk2 + k1 d + k1 k2 m)m = bd + km, where k = bk2 + k1 d + k1 k2 m is an integer. Thus, ac ≡ bd (mod m). (iv) Apply (iii) repeatedly.

(v) Follows from (iii) since ℓ ≡ ℓ (mod m).

(vi) Suppose that n | m. Since a ≡ b (mod m), we have m | (a − b). Thus, n | (a − b), so a ≡ b (mod n).

Example. Suppose x, y ∈ Z with x ≡ 3 (mod 7), y ≡ 5 (mod 7). Find 2x + xy mod 7. By (v), 2x ≡ 2 × 3 = 6 (mod 7). By (iii), xy ≡ 3 × 5 = 15 ≡ 1 (mod 7). So (i) gives 2x + xy ≡ 6 + 1 = 7 ≡ 0 (mod 7). Hence 2x + xy mod 7 = 0. Exercise. Find x3 + 2x2 y mod 7. We calculate that x3 + 2x2 y ≡ 33 + 2 × 32 × 5 (mod 7) = 27 + 90 = 117 ≡ 5 (mod 7).

Upshot: You can substitute with congruence equations much as you can with ordinary equations. Here’s a nice application of modular arithmetic. Example. The last two digits of the number 1234567 are the number 67. This can be formally expressed as 1234567 mod 100 = 67

or

1234567 ≡ 67 (mod 100) .

Similarly, to find the last two digits of the number 71234567 , we need to evaluate 71234567 mod 100. We have 72 ≡ 49 (mod 100) ;

73 ≡ 49 × 7 ≡ 343 ≡ 43 (mod 100) ; 74 ≡ 43 × 7 ≡ 301 ≡ 1 (mod 100) .

Then it is easy to obtain, for example,

78 ≡ (74 )2 ≡ 12 ≡ 1 (mod 100) ; 7444 ≡ (74 )111 ≡ 1111 ≡ 1 (mod 100) ; 7446 ≡ (74 )111 × 72 ≡ 1111 × 49 ≡ 49 (mod 100) ;

and in particular, we have

71234567 ≡ 74×308641+3 ≡ (74 )308641 × 73 ≡ 1308641 × 43 ≡ 43 (mod 100) .

Exercise. Simplify 10123456789 mod 41. We calculate that 102 103 104 105

≡ 100 ≡ 18 (mod 41) ; ≡ 18 × 10 ≡ 180 ≡ 16 (mod 41) ; ≡ 16 × 10 ≡ 160 ≡ 37 (mod 41) ; ≡ 37 × 10 ≡ 370 ≡ 1 (mod 41) .

Thus, 10123456789 ≡ 105×24691357+4 ≡ (105 )24691357 × 104 ≡ 124691357 × 37 ≡ 37 (mod 41) .

Example. We have seen that simplifying an mod m becomes quite easy if there is a small number k such that ak ≡ 1 (mod m). It is also useful if ak ≡ −1 (mod m) for some small k. In intermediate calculations, work with numbers between −m/2 and m/2.

For example, we will try to simplify 5115511 mod 29. We have

52 ≡ 25 ≡ −4 (mod 29) ; usual remainder 25 not used! 53 ≡ (−4) × 5 ≡ −20 ≡ 9 (mod 29) ; 54 ≡ 9 × 5 ≡ 45 ≡ 16 ≡ −13 (mod 29) ; 55 ≡ (−13) × 5 ≡ −65 ≡ −7 (mod 29) ; 56 ≡ (−7) × 5 ≡ −35 ≡ −6 (mod 29) ; 57 ≡ (−6) × 5 ≡ −30 ≡ −1 (mod 29) .

Thus, 5115511 ≡ 57×16501+4 ≡ (57 )16501 × 54 ≡ (−1)16501 × (−13) ≡ (−1) × (−13) ≡ 13 (mod 29) .

Example. Unfortunately, if gcd(a, m) 6= 1 then we cannot find a positive integer k with ak ≡ ±1 (mod m), because no such k exists! Instead we keep an eye out for any “pattern” in the powers. For example, let’s try to simplify 654321 mod 100. We have 61 ≡ 6 (mod 100) ; 62 ≡ 36 (mod 100) ;

63 ≡ 36 × 6 ≡ ...