false

Class Notes
(836,414)

Canada
(509,777)

York University
(35,328)

MATH 1190
(22)

Marshall Walker
(1)

Lecture

Unlock Document

Mathematics and Statistics

MATH 1190

Marshall Walker

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.
Deﬁniton. 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) (Reﬂexivity) 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 diﬀerent 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 deﬁnition 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 coeﬃcients 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 deﬁned 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 ﬁnd the numbers mod 6 which satisfy x = 3.
Checking x = 0,1,2,3,4,5, I ﬁnd 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 coeﬃcient = 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 ﬁnding 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 inﬁnitely many integer
solutions
x = x + m t,
0 d
where x0is a particular solution. I need to show that of these inﬁnitely 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 diﬀer 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 speciﬁc,
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 ﬁnd it in three diﬀerent
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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.