Number Theory Il 7.a≡b(modm)andc≡d(modn) imply ac≡bd(modn) Proof. We prove only parts 1 and 7; the other parts are proved similarly (part 1)Every integer divides 0, so n (a-a), which means a= a(mod n) (part 7) The assumption a= b(mod n) implies that ac bc(mod n) by part 5. Similarly, the assumption c= d(mod n) implies bc bd(mod n). Therefore, ac bd(mod n)by art 3 There is a close connection between modular arithmetic and the remainder operation which we looked at last time. To clarify this link, lets reconsider the partition of the integers defined by congruence modulo 3 6.-3.0.3.6.9 5,-2,1,4,7,10 Notice that two numbers are in the same set if and only if they leave the same remainder hen divided by 3. The numbers in the first set all leave a remainder of 0 when divided by 3, the numbers in the second set leave a remainder of 1, and the numbers in the third leave a remainder of 2. Furthermore, notice that each number is in the same set as its own remainder. For example 11 and 1l rem 3=2 are both in the same set. Let' s bundle all this happy goodness into a lemma Lemma 2( Congruences and Remainders). The following assertions hold 1.a≡( a rem n)(modn) 2. a=b(mod n) if and only if (a rem n)=(b rem n Proof.(of part 2) By the division algorithm, there exist unique pairs of integers q1, rI and 92, r2 such that a=gin +rI ( where0≤71<m) b= g2n+ra ( where0≤n2<m) In these terms, (a rem n)=rI and(b rem n)=r2. Subtracting the second equation from the first gives: a-b=(qh-q2)n+(r1-r2) (where -n<r1-r2< n) Now a = b(mod n)if and only if n divides the left side. This is true if and only if n divides the right side, which holds if and only if r1-r2 is a multiple of n. Given the bounds onr r2, this happens precisely when r1=r2, which is equivalent to(a rem n)=(b rem n). DNumber Theory II 5 7. a ≡ b (mod n) and c ≡ d (mod n) imply ac ≡ bd (mod n) Proof. We prove only parts 1 and 7; the other parts are proved similarly. (part 1) Every integer divides 0, so n | (a − a), which means a ≡ a (mod n). (part 7) The assumption a ≡ b (mod n) implies that ac ≡ bc (mod n) by part 5. Similarly, the assumption c ≡ d (mod n) implies bc ≡ bd (mod n). Therefore, ac ≡ bd (mod n) by part 3. There is a close connection between modular arithmetic and the remainder operation, which we looked at last time. To clarify this link, let’s reconsider the partition of the integers defined by congruence modulo 3: { . . . , −6, −3, 0, 3, 6, 9, . . . } { . . . , −5, −2, 1, 4, 7, 10, . . . . . . , −4, −1, 2, 5, 8, 11, . . . } { } Notice that two numbers are in the same set if and only if they leave the same remainder when divided by 3. The numbers in the first set all leave a remainder of 0 when divided by 3, the numbers in the second set leave a remainder of 1, and the numbers in the third leave a remainder of 2. Furthermore, notice that each number is in the same set as its own remainder. For example, 11 and 11 rem 3 = 2 are both in the same set. Let’s bundle all this happy goodness into a lemma. Lemma 2 (Congruences and Remainders). The following assertions hold: 1. a ≡ (a rem n) (mod n) 2. a ≡ b (mod n) if and only if (a rem n) = (b rem n) Proof. (of part 2) By the division algorithm, there exist unique pairs of integers q1, r1 and q2, r2 such that: a = q1n + r1 (where 0 ≤ r1 < n) b = q2n + r2 (where 0 ≤ r2 < n) In these terms, (a rem n) = r1 and (b rem n) = r2. Subtracting the second equation from the first gives: a − b = (q1 − q2)n + (r1 − r2) (where −n < r1 − r2 < n) Now a ≡ b (mod n) if and only if n divides the left side. This is true if and only if n divides the right side, which holds if and only if r1−r2 is a multiple of n. Given the bounds on r1 = r2, this happens precisely when r1 = r2, which is equivalent to (a rem n) = (b rem n)