March 2, 2018 - Shawn Zhong

$Division • Definition ○ If a and b are integers with a ≠ 0, ○ then a divides b if there exists an integer c such that b = ac. ○ When a divides b we say that a is a factor or divisor of b and that b is a multiple of a. ○ The notation a | b denotes that a divides b. ○ If a | b, then b/a is an integer. ○ If a does not divide b, we write a ∤ b. • Example ○ Determine whether 3 | 7 and whether 3 | 12. ○ 3 | 7 is false ○ 3 | 12 is true Properties of Divisibility • Theorem 1: Let a, b, and c be integers, where a ≠0. ○ If a | b and a | c, then a | (b + c); ○ If a | b, then a | bc for all integers c; ○ If a | b and b | c, then a | c. • Proof (i) ○ Suppose a | b and a | c, then it follows that ○ there are integers s and t with b = as and c = at. ○ Hence, b + c = as + at = a(s + t). ○ Hence, a | (b + c) • Corollary ○ If a, b, and c be integers, where a ≠0, such that a | b and a | c, ○ then a | mb + nc whenever m and n are integers. Division Algorithm • When an integer is divided by a positive integer, there is a quotient and a remainder. • This is traditionally called the “Division Algorithm,” but is really a theorem. • Division Algorithm ○ If a is an integer and d a positive integer, then ○ there are unique integers q and r, with 0 ≤ r d, such that ○ a = dq + r ○ d is called the divisor. ○ a is called the dividend. ○ q is called the quotient. ○ r is called the remainder. • Example: What are the quotient and reminder when 101 is divided by 11? ○ 101=11⋅9+2 ○ Thus the quotient is 9, and the remainder is 2 ○ 101 div 11 = 9 ○ 101 mod 11 = 2 • Example: What are the quotient and reminder when -11 is divided by 3? ○ −11=3⋅(−4)+1 Congruence Relation • Definition ○ If a and b are integers and m is a positive integer, ○ then a is congruent to b modulo m if m divides a – b. ○ The notation a ≡ b (mod m) says that a is congruent to b modulo m. ○ We say that a ≡ b (mod m) is a congruence and that m is its modulus. ○ Two integers are congruent mod m if and only if they have the same remainder when divided by m. ○ If a is not congruent to b modulo m, we write a ≢ b (mod m) • Determine whether 17 is congruent to 5 modulo 6 ○ 17 ≡ 5 (mod 6) because 6 divides 17 − 5 = 12. • Determine whether 24 and 14 are congruent modulo 6. ○ 24 ≢ 14 (mod 6) since 24 − 14 = 10 is not divisible by 6. The Relationship between (mod m) and mod m Notations • The use of “mod” in a ≡ b (mod m) and a mod m = b are different. ○ a ≡ b (mod m) is a relation on the set of integers. ○ In a mod m = b, the notation mod denotes a function. • The relationship between these notations is made clear in this theorem. • Theorem 3 ○ Let a and b be integers, and let m be a positive integer. ○ Then a ≡ b (mod m) if and only if ○ a mod m = b mod m. More on Congruence • Theorem 4 ○ Let m be a positive integer. ○ The integers a and b are congruent modulo m if and only if ○ there is an integer k such that a = b + km. • Proof: ○ If a ≡ b (mod m), then (by the definition of congruence) m | a – b. ○ Hence, there is an integer k such that a – b = km and equivalently a = b + km. ○ Conversely, if there is an integer k such that a = b + km, then km = a – b. ○ Hence, m | a – b and a ≡ b (mod m). Congruence of Sums and Products • Theorem 5 ○ Let m be a positive integer. ○ If a ≡ b (mod m) and c ≡ d (mod m), then § a + c ≡ b + d (mod m) § ac ≡ bd (mod m) • Proof: ○ Because a ≡ b (mod m) and c ≡ d (mod m) ○ by Theorem 4 there are integers s and t with b = a + sm and d = c + tm. ○ Therefore, § b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) and § b d = (a + sm) (c + tm) = ac + m(at + cs + stm). ○ Hence, a + c ≡ b + d (mod m) and ac ≡ bd (mod m). • Example ○ Because 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5) , it follows from Theorem 5 that ○ 18 = 7 + 11 ≡ 2 + 1 = 3 (mod 5) ○ 77 = 7 ∙ 11 ≡ 2 ∙ 1 = 2 (mod 5) Algebraic Manipulation of Congruence • Multiplying both sides of a valid congruence by an integer preserves validity. ○ If a ≡ b (mod m) holds then c∙a ≡ c∙b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Adding an integer to both sides of a valid congruence preserves validity. ○ If a ≡ b (mod m) holds then c + a ≡ c + b (mod m), where c is any integer, ○ holds by Theorem 5 with d = c. • Dividing a congruence by an integer does not always produce a valid congruence. ○ The congruence 14≡ 8 (mod 6) holds. ○ But dividing both sides by 2 does not produce a valid congruence since ○ 14/2 = 7 and 8/2 = 4, but 7≢4 (mod 6). Computing the mod m Function of Products and Sums • We use the following corollary to Theorem 5 to compute the remainder of the product or sum of two integers when divided by m from the remainders when each is divided by m. • Corollary: Let m be a positive integer and let a and b be integers. Then ○ (a + b) (mod m) = ((a mod m) + (b mod m)) mod m ○ ab mod m = ((a mod m) (b mod m)) mod m. Arithmetic Modulo m • Definitions ○ Let Zm be the set of nonnegative integers less than m: {0,1, …., m−1} ○ The operation +m is defined as a +_m b = (a + b) mod m. ○ This is addition modulo m. ○ The operation ∙m is defined as a ∙_m b = (a ∙ b) mod m. ○ This is multiplication modulo m. • Example: Find 7 +_11 9 and 7 ∙_11 9. ○ 7 +_11 9 = (7 + 9) mod 11 = 16 mod 11 = 5 ○ 7 ∙_11 9 = (7 ∙ 9) mod 11 = 63 mod 11 = 8 • The operations +_m and ∙_m satisfy many of the same properties as ordinary addition and multiplication. ○ Closure § If a and b belong to Zm , then a +_m b and a ∙_m b belong to Zm. ○ Associativity § If a, b, and c belong to Zm , then § (a +_m b) +_m c = a +_m (b +_m c) § (a ∙_m b) ∙_m c = a ∙_m (b ∙_m c). ○ Commutativity § If a and b belong to Zm , then § a +_m b = b +_m a § a ∙_m b = b ∙_m a. ○ Identity elements § The elements 0 and 1 are identity elements for addition and multiplication modulo m, respectively. § If a belongs to Zm , then a +_m 0 = a and a ∙_m 1 = a. ○ Additive inverses § If a≠ 0 belongs to Zm § then m − a is the additive inverse of a modulo m § and 0 is its own additive inverse. § a +_m (m− a) = 0 § 0 +_m 0 = 0 ○ Distributivity § If a, b, and c belong to Zm , then § a ∙_m (b +_m c) = (a ∙_m b) +_m (a ∙_m c) § (a +_m b) ∙_m c = (a ∙_m c) +_m (b ∙_m c). • Multiplicative inverses have not been included since they do not always exist. • For example, there is no multiplicative inverse of 2 modulo 6. • Using the terminology of abstract algebra ○ Zm with +_m is a commutative group ○ Zm with +_m and ∙_m is a commutative ring$

Shawn Zhong

Shawn Zhong

4.1 Divisibility and Modular Arithmetic

Search

WeChat Account