Class Notes (836,414)
Canada (509,777)
York University (35,328)
MATH 1190 (22)
Lecture

Discrete mathmatics

13 Pages
392 Views
Unlock Document

Department
Mathematics and Statistics
Course
MATH 1190
Professor
Marshall Walker
Semester
Fall

Description
7-23-2006 Congruences and Modular Arithmetic • a is congruent to b mod n means that n | a − b. Notation: a = b (mod n). • Congruence mod n is an equivalence relation. Hence, congruences have many of the same properties as ordinary equations. • Congruences provide a convenient shorthand for divisibility relations. Definiton. Let a, b, and m be integers. a is congruent to b mod m if m | a − b; that is, if a − b = km for some integer k. Write a = b (mod m) to mean that a is congruent to b mod m. m is called the modulus of the congruence; I will almost always work with positive moduli. Notice that a = 0 (mod m) is equivalent to m | a. Thus, divisibility is a special case of congruence. In many cases, this means that you can reduce proving results about congruences to results about divisibility that were proved earlier. Example. 101 = 3 (mod 2) and 2 = 101 (mod 3). Proposition. Congruence mod m is an equivalence relation: (a) (Reflexivity) a = a (mod m) for all a. (b) (Symmetry) If a = b (mod m), then b = a (mod m). (c) (Transitivity) If a = b (mod m) and b = c (mod m), then a = c (mod m). Proof. I’ll prove transitivity and leave the proofs of the other two properites to you. Suppose a = b (mod m) and b = c (mod m). Then there are integers j and k such that a − b = jm, b − c = km. Add the two equations: a − c = (j + k)m. This implies that a = c (mod m). Example. Consider congruence mod 3. There are 3 congruence classes: {...,−3,0,3,6,...}, {... − 4,−1,2,5,...}, {...− 5,−2,1,4,...}. Each integer belongs to exactly one of these classes. Two integers in a given class are congruent mod 3. (If you know some group theory, you probably recognize this as constructing Z 3rom Z.) When you’re doing things mod 3, it is if there were only 3 numbers. I’ll grab one number from each of the classes to represent the classes; for simplicity, I’ll use 0, 2, and 1. 1 Here is an addition table for the classes in terms of these representatives: + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 Here’s an example: 2 + 1 = 0, because 2 + 1 = 3 as integers, and 3’s congruence class is represented by 0. This is the table for addition mod 3. I could have chosen different representatives for the classes — say 3, −4, and 4. A choice of repre- sentatives, one from each class, is called a complete system of residues mod 3. But working mod 3 it’s natural to use the numbers 0, 1, and 2 as representatives — and in general, if I’m working mod n, the obvious choice of representatives is the set {0,1,2,...,n − 1}. This set is called the least nonnegative system of residues mod n, and it is the set of representatives I’ll usually use. (Sometimes I’ll get sloppy and call it the least positive system of residues, even though it includes 0.) Proposition. If a = b (mod m) and c = d (mod m), then a + c = b + d (mod m) and ac = bd (mod m). Note: You can use the second property and induction to show that if a = b (mod m), then an = n b (mod m) for all n ≥ 1. Proof. Suppose a = b (mod m) and c = d (mod m). Then m | a − b and m | c − d. Therefore, m | (a − b) + (c − d) = (a + c) − (b + dso a + b = b + d (mod m) . To prove the second congruence, return to the relations m | a − b and m | c − d. By definition of divisibility, there are integers j and k such that a − b = jm and c − d = km. Thus, a = b + jm and c = d + km. Multiply these two equations and do some algebra on the right side: 2 ac = (b + jm)(d + km) = bd + bkm + djm + jkm = bd + m(bk + dj + jkm). Hence, ac − bd = m(bk + dj + jkm) and m | ac − bd, so ac = bd (mod m) . Corollary. If a = b (mod m), then a ± c = b ± c (mod m) and ac = bc (mod m) . Proof. Apply the preceding result to the congruences a = b (mod m) and c = c (mod m). These results say that congruences behave like equations: • You can add two congruences. 2 • You can multiply two congruences. • You can add a number to both sides of a congruence. • You can multiply both sides of a congruence by a number. For instance, you can solve single-variable linear congruences using the same approach that you would use to solve linear equations. Example. Solve the congruence 2x + 11 = 7 (mod 3). First, reduce all the coefficients mod 3: 2x + 2 = 1 (mod 3). Next, add 1 to both sides, using the fact that 2 + 1 = 0 (mod 3): 2x = 2 (mod 3). Finally, multiply both sides by 2, using the fact that 2 ▯ 2 = 4 = 1 (mod 3): x = 1 (mod 3). That is, any number in the set {...,−5,−2,1,4,...} will solve the original congruence. Remark. Notice that I accomplished division by 2 (in solving 2x = 2 (mod 3) by multiplying by 2. The reason this works is that, mod 3, 2 is its own multiplicative inverse. Recall that two numbers x and y are multiplicative inverses if x▯y = 1 and y▯x = 1. For example, in 3 5 the rational numbers,5 and 3 are multiplicative inverses. Division by a number is defined to be multiplication 1 by its multiplicative inverse. Thus, division by 3 means multiplication by. 3 In the integers, only 1 and −1 have multiplicative inverses. When you perform a “division” in Z — such as dividing 2x = 6 by 2 to get x = 3 — you are actually factoring and using the Zero Divisor Property: 2x = 6, 2x − 6 = 0, 2(x − 3) = 0, x − 3 = 0, x = 3. (I used the Zero Divisor Property in making the third step: Since 2 ▯= 0, x − 3 must be 0.) In doing modular arithmetic, however, many numbers may have multiplicative inverses. In these cases, you can perform division by multiplying by the multiplicative inverse. Here is a multiplication table mod 3, using the standard residue system {0,1,2}: ∗ 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 You can construct similar tables for other moduli. For example, 2 and 3 are multiplicative inverses mod 5, because 2 ▯ 3 = 1 (mod 5). So if you want to “divide” by 3 mod 5, you multiply by 2 instead. This doesn’t always work. For example, consider 2x = 4 (mod 6). 3 2 does not have a multiplicative inverse mod 6; that is, there is no k such that 2k = 1 (mod 6). You can check by trial that the solutions to the equation above are x = 2 (mod 6) and x = 5 (mod 6) — just look at 2x (mod 6) for x = 0,1,2,3,4,5. Proposition. If ac = bc (mod m) and d = (c,m), then m a = b mod . d Proof. Write ac − bc = km, where k ∈ Z. Then c m (a − b) = k . d d c m c (Notice that and are integers, since d | c and d | m.) Now divides the right side, but it’s d m d d relatively prime to . Therefore, it must divide k: d k = cj for some j ∈ Z. d Hence, c c m (a − b) = j ▯ , d d d m a − b = j ▯ . d m This proves that a = b mod . d Example. Consider the equation from the last example: 2x = 4 (mod 6). This is (2 ▯ 1)x = (2 ▯ 2) (mod 6). Apply the last result with a = 1, b = 2, c = 2, and m = 6. Now (2,6) = 2, so the result says I can “divide everything by 2”: x = 2 (mod 3). Since the original congruence was mod 6, I have to find the numbers mod 6 which satisfy x = 3. Checking x = 0,1,2,3,4,5, I find that x = 2 (mod 6) or x = 5 (mod 6). Example. In 2x = 4 (mod 7), 2 is a common factor of 2 and 4, and (2,7) = 1, so x = 2 (mod 7). Alternatively, notice that 2 ▯ 4 = 1 (mod 7), so if I multiply the equation by 4, I get x = 2 (mod 7). 4 10 Example. What is the least positive residue of 99 (mod 7)? 99 = 1 (mod 7), so 10 10 99 = 1 = 1 (mod 7). Example. If p is prime, then (x + y) = x + y p (mod p). By the Binomial Theorem, Xp p (x + y) = x yp−i. i i=0 p p! A typical coefficient = is divisible by p for i ▯= 0,p. So going mod p, the only terms that p p i i!(p − i)! remain are x and y . For example (x + y) = x + y 2 (mod 2) and (x + y) = x + y 3 (mod 3). The result is not true if the modulus is not prime. For example, (1 + 1) = 0 (mod 4), but 1 + 1 = 2 (mod 4). ▯c2006 by Bruce Ikenaga 5 7-24-2006 Solving Congruences • A linear congruence ax = b (mod m) has solutions if and only if (a,m) | b. • You can solve linear congruences by finding modular inverses, by using the Euclidean algorithm, and by turning the congruence into a linear Diophantine equation. Theorem. Let d = (a,m), and consider the equation ax = b (mod m) . (a) If d▯ |b, there are no solutions. (b) If d | b, there are exactly d distinct solutions mod m. Proof. Observe that ax = b (mod m) ⇔ ax + my = b for some y. Hence, (a) follows immediately from the corresponding result on linear Diophantine equations. The result on linear Diophantine equations which corresponds to (b) says that there are infinitely many integer solutions x = x + m t, 0 d where x0is a particular solution. I need to show that of these infinitely many solutions, there are exactly d distinct solutions mod m. Suppose two solutions of this form are congruent mod m: m m x 0 t1= x0+ 2 (mod m) . d d Then m m t1= t2 (mod m) . d d m m m m Now d divides both sides, and,m = d , so I can divide this congruence throdgto obtain t1= t2 (mod d). Going the other way, suppo1e t2=(mod d). This means that1t and2t differ by a multiple of d: t1− t2= kd. So m m m d 1 − d t2= d ▯ kd = km. This implies that m m t1= 2 (mod m) d d so m m x 0 t1= x0+ 2 (mod m) . d d 1 Let me summarize what I’ve just shown. I’ve proven that two solutions of the above form are equal mod m if and only if their marameter values are equal mod d. That is, if I let t range over a complete system of residues mod d, then0x + t ranges over all possible solutions mod m. To be very specific, d x + m t (mod m) for t = 0,1,2,...,d − 1 0 d are all the solutions mod m. Example. 6x = 7 (mod 8). Since (6,8) = 2▯ |7, there are no solutions. Example. 3x = 7 (mod 4). Since (3,4) = 1 | 7, there will be 1 solutions mod 4. I’ll find it in three different ways. Using linear Diophantine equations. 3x = 7 (mod 4) implies 2x + 4y = 7 for some y. By inspection 0 = 1, 0 = 1 is a particular solution. (3,4) = 1, so the general solution is x = 1 + 4t, y = 1 − 3t. The y equation is irrelevant. The x equation says x = 1 (mod 4). Using the Euclidean algor
More Less

Related notes for MATH 1190

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit