|
[ Pobierz całość w formacie PDF ]
15.2 are valid. 60 CHAPTER 15. CONGRUENCES Exercise 15.4. (a) Show that a is even ⇔ a ≡ 0 (mod 2) and a is odd ⇔ a ≡ 1 (mod 2). (b) Show that a is even ⇔ a mod 2 = 0 and a is odd ⇔ a mod 2 = 1. Exercise 15.5. Show that if m0 and a is any integer, there is a unique integer r ∈{0, 1, 2, . . . , m- 1} such that a ≡ r (mod m). Exercise 15.6. Find integers a and b such that 0 a 15, 0 b 15 and ab ≡ 0 (mod 15). Exercise 15.7. Find integers a and b such that 1 a 15, 1 b 15, and ab ≡ 1 (mod 15). Exercise 15.8. Show that if d | m and d 0, then a ≡ b (mod m) ⇒ a ≡ b (mod d). The next two theorems show that congruences and equations share many similar properties. Theorem 15.2 (Congruence is an equivalence relation). For all a, b, c and m0 we have (1) a ≡ a (mod m) [reflexivity] (2) a ≡ b (mod m) ⇒ b ≡ a (mod m) [symmetry] (3) a ≡ b (mod m) and b ≡ c (mod m) ⇒ a ≡ c (mod m) [transitivity] Proof of (1). a - a =0 =0 · m, so m | a - a. Hence a ≡ a (mod m). Proof of (2). If a ≡ b (mod m), then m | a - b. Hence a - b = mq. Hence b - a = m(-q), so m | b - a. Hence b ≡ a (mod m). Proof of (3). If a ≡ b (mod m) and b ≡ c (mod m) then m | a - b and m | b - c. By the linearity property m | (a - b) +(b - c). That is, m | a - c. Hence a ≡ c (mod m). Recall that a polynomial is an expression of the form f(x) =anxn + an-1xn-1 + · · · + a1x + a0. Here we will assume that the coefficients an, . . . , a0 are integers and x also represents an integer variable. Here, of course, n ≥ 0 and n is an integer. 61 Theorem 15.3. If a ≡ b (mod m) and c ≡ d (mod m), then (1) a ± c ≡ b ± d (mod m) (2) ac ≡ bd (mod m) (3) an ≡ bn (mod m) for all n ≥ 1 (4) f(a) ≡ f(b) (mod m) for all polynomials f(x) with integer coefficients. Proof of (1). To prove (1) since a - c = a +(-c), it suffices to prove only the “+ case.” By assumption m | a - b and m | c - d. By linearity, m | (a - b) +(c - d), that is m | (a + c) - (b + d). Hence a + c ≡ b + d (mod m). Proof of (2). Since m | a - b and m | c - d by linearity m | c(a - b) +b(c - d). Now c(a - b) +b(c - d) =ca - bd, hence m | ca - bd, and so ca ≡ bd (mod m), as desired. Proof of (3). We prove an ≡ bn (mod m) by induction on n. If n =1, the result is true by our assumption that a ≡ b (mod m). Assume it holds for n = k. Then we have ak ≡ bk (mod m). This, together with a ≡ b (mod m) using (2) above, gives aak ≡ bbk (mod m). Hence ak+1 ≡ bk+1 (mod m). So it holds for all n ≥ 1, by the PMI. Proof of (4). Let f(x) =cnxn + · · · + c1x + c0. We prove by induction on n that if a ≡ b (mod m) then cnan + · · · + c0 ≡ cnbn + · · · + c0 (mod m). If n =0 we have c0 ≡ c0 (mod m) by Theorem 15.2 (1). Assume the result holds for n = k. Then we have (∗) ckak + · · · + c1a + c0 ≡ ckbk + · · · + c1b + c0 (mod m). 62 CHAPTER 15. CONGRUENCES By part (3) above we have ak+1 ≡ bk+1 (mod m). Since ck+1 ≡ ck+1 (mod m) using (2) above we have (∗∗) ck+1ak+1 ≡ ck+1bk+1 (mod m). Now we can apply Theorem 15.3 (1) to (∗) and (∗∗) to obtain ck+1ak+1 + ckak + · · · + c0 ≡ ck+1bk+1 + ckbk + · · · + c0 (mod m). So by the PMI, the result holds for n ≥ 0. Before continuing to develop properties of congruences, we give the fol- lowing example to show one way that congruences can be useful. Example 15.3. (This example was taken from [1] Introduction to Analytic Number Theory, by Tom Apostol.) The first five Fermat numbers F0 =3, F1 =5, F2 =17, F3 = 257, F4 =65, 537 are primes. We show using congruences without explicitly calculating F5 that F5 =232 + 1 is divisible by 641 and is therefore not prime : 22 =4 2 24 = 22 =42 =16 2 28 = 24 =162 = 256 2 216 = 28 = 2562 =65, 536 65, 536 ≡ 154 (mod 641). So we have By Theorem 15.3 (3): That is, Since 216 ≡ 154 (mod 641). 2 216 ≡ (154)2 (mod 641). 232 ≡ 23, 716 (mod 641). 23, 716 ≡ 640 (mod 641) 232 +1≡ 0 (mod 641). 63 and 640 ≡-1 (mod 641) we have 232 ≡-1 (mod 641) and hence So 641 | 232 +1, as claimed. Clearly 232 +1 = 641, so 232 +1 is composite. Of course, if you already did Exercise 12.1 (p. 44) you will already know that 232 +1=4, 294, 967, 297 = (641) · (6, 700, 417) and that 641 and 6, 700, 417 are indeed primes. Note that 641 is the 116th prime, so if you used trial division you would have had to divide by 115 primes before reaching one that divides 232 + 1, and that assumes that you have a list of the first 116 primes. Theorem 15.4. If m0 and a ≡ r (mod m) where 0 ≤ r m then a mod m = r. Exercise 15.9. Prove Theorem 15.4. [Hint: The Division Algorithm may be useful.] Exercise 15.10. Find the value of each of the following (without using Maple!). (1) 232 mod 7 (2) 1035 mod 7 (3) 335 mod 7 [Hint: Use Theorem 15.4 and the ideas used in the example on page 62.] Exercise 15.11. Let gcd (m1, m2) =1. Prove that (15.1) a ≡ b (mod m1) and a ≡ b (mod m2) if and only if (15.2) a ≡ b (mod m1m2). [Hint. Use Lemma 11.1, page 38.] 64 CHAPTER 15. CONGRUENCES Chapter 16 Divisibility Tests for 2, 3, 5, 9, 11 Recall from Definition 4.2 on page 14 that the decimal representation of the [ Pobierz całość w formacie PDF ] |
Podobne
|