chapter 2 Modular arithmetic Flashcards
Definition 2.1.1
congruent
Let a, b, m ∈ Z with m > 1. We say that a is congruent to b modulo m, written a ≡ b (mod m),
if a = b + mk for some k ∈ Z. This is equivalent to m | (a − b).
We write a ̸≡ b (mod m) otherwise.
Example 2.1.2. 15 mod 3
19 mod 3
15 ≡ 0 (mod 3); 19 ≡ −2 (mod 3)
Example 2.1.3 (Clocks).
and modular arithmetic
Again, clocks are the prototypical example of modular arithmetic in every day life. To compute which hour will show on your clock b hours from now, you simply find the unique r ∈ {1, . . . , 12} such that r ≡ a + b (mod 1)2, where a is the hour showing up now.
11 oclock what time in 37hrs?
37≡13≡1 mod 12 12:00
Exercise 2.1.4. (1) a ≡ 0 (mod m) if and only if m | a
a ≡ 0 (mod m) means that a =0 +mk=mk for some k ∈ Z, by defn,
and that is exactly the meaning of m | a.
Exercise 2.1.4.
(2) a ≡ b (mod m) if and only if a and b have the same remainder on dividing by m.
means a and b have the same remainder upon division by m
Suppose that a ≡ b (mod m). This is equivalent to m|(a-b). Divide a and b by m and write
a=q_1m+r_1
b=q_2m+r_2
m|(A-b) = (q_1-1_2)m +(r_1-r_2)
thus m|(r_1-r_2).
Recall that 0 ≤ r_i < m, so −m < r_1 − r_2 < m.
(There is only one multiple of m between this)
The only number divisible by m in that interval is 0, so
m | (r1 − r2)
if and only if
r1 − r2 = 0, that is, r1 = r2.
Exercise 2.1.4
(3) Every integer is congruent modulo m to exactly one of the numbers 0, 1, 2, . . . , m −
1.
Alternatively, to exactly one of 1, 2, . . . , m. We say that {0, 1, . . . , m − 1} and {1, 2, . . . , m} are complete sets of residues modulo m.
(3) Let a ∈ Z and r ∈ Z be its remainder in the division by m. By the previous point, a ≡ r (mod m).
Moreover, if r′ ∈ {0, 1, . . . ,m−1}, its remainder by m is r′ itself, so by the previous point a ≡ r′ (mod m) if and only if r′ = r. This shows that there is a unique r′ ∈ {0, 1, . . . ,m − 1} such that a ≡ r′ (mod m).
If we want to find r′ ∈ {1, . . . ,m}, just take r = r′ when r > 0, and
r′ = m when r = 0.
Exercise 2.1.4.
(4) ≡ is an equivalence relation:
(a) a ≡ a for all a (reflexive);
(b) a ≡ b implies b ≡ a (symmetric);
(c) a ≡ b and b ≡ c imply a ≡ c (transitive).
- m | 0, so m | (a − a), meaning that a ≡ a (mod m);
- a ≡ b (mod m) means m | (a − b), but then also m | −(a − b) = (b − a), thus b ≡ a (mod m);
- if a ≡ b (mod m) and b ≡ c (mod m), then m | (a − b) and m | (b − c). This implies also that m | ((a − b) + (b − c)) = (b − c), hence
b ≡ c mod m.
congruence remarks
Every integer is congruent to exactly one of 0,1,…,m-1exactly one of 1,2,…m
n|0
complete sets of residues {1,…,n} and {0,1,…,n-1}
remember working on Z
working on Z with mod 2
evens and odds 2 congruence classes
z is partitioned into 2
n=3 we have 3 congruence classes
{3k:k∈ Z}
{3k+1: k∈ Z} ={…,-2,1,4,7,…}
and
{3k+2:k∈ z}
Arithmetic works nicely in these congruence mod m comparable + and -
Lemma 2.1.5 (Arithmetic of congruences)
The equivalence relation ≡ (mod m) is compatible with addition and multiplication, meaning that:
if a ≡ b and c ≡ d, then a + c ≡ b + d and ac ≡ bd.
PROOF
Arithmetic of congruences)
The equivalence relation ≡ (mod m) is compatible with addition and multiplication, meaning that:
if a ≡ b and c ≡ d, then a + c ≡ b + d and ac ≡ bd
Proof. Take a, b, c, d as in the hypothesis. By assumption, m | (a − b) and m | (c − d). In
particular
m | ((a − b) + (c − d)) = ((a + c) − (b + d))
thus a + c ≡ b + d (mod m). For the product, we need to show that m divides (ac − bd).
We use a trick:
ac − bd = ac − bc + bc − bd = (a − b)c + b(c − d).
Clearly m | (a − b)c + b(c − d), so b | (ac − bd), which means that ac ≡ bc (mod m). □
Example 2.1.6. Show that if a ≡ b and c ≡ d, then a − c ≡ b − d, and also a^k ≡ b^k for all
k = 0, 1, 2, . . .
Since −1 ≡ −1, we also have −c ≡ −d, thus a − c ≡ b − d.
For aᵏ we proceed by induction: clearly a_0 = 1 ≡ 1 = b_0;
if aᵏ ≡ bᵏ, then aᵏ⁺¹ = (aᵏ)a ≡
(bᵏ)b = bᵏ⁺¹, and so by induction aᵏ≡ bᵏ for all k.
Corollary 2.1.7
CONGRUENCE CLASSES
Let Z/mZ be the set of the congruence classes for the equivalence relation ≡ (mod m); said differently, it is the quotient of Z by the relation ≡ (mod m).
Then Z/mZ is a cyclic group under addition of size m.
In group theory, the ‘cyclic group of order m’ is also called Cm. The main difference between C_m and Z/mZ is that the former is just an abstract group, the latter has multiplication as well.
Corollary 2.1.7
CONGRUENCE CLASSES
manual
PROOF
Manual proof. Simply recall that a group is a set with a binary operation which is
associative, has an identity, and every element has an inverse.
* a + (b + c) ≡ (a + b) + c (mod m);
* a + 0 ≡ 0 + a ≡ a (mod m);
* a + (−a) ≡ 0 (mod m).
The set {0, 1, . . . , m − 1} is a complete set of residues and it has size m, so the quotient
has size m. Finally, it is cyclic: its generator is the congruence class of 1.
Corollary 2.1.7
CONGRUENCE CLASSES
group theoretic
PROOF
Group theoretic proof. Note that
{a ∈ Z : a ≡ 0 (mod m)} = {mk : k ∈ Z} = mZ.
The set mZ is obviously closed under addition and inverses, so it is a subgroup of Z.
Thus we can take the quotient group Z/mZ. Now recall the definition of quotient
group: two elements a, b ∈ Z are equivalent if and only if a − b ∈ mZ, thus if and only
if m | (a − b), if and only if a ≡ b (mod m). So the quotient group Z/mZ is exactly the
set of congruences we have discussed so far. Since Z is cyclic (it is generated by 1), then Z/mZ is also cyclic and generated by
the quotient of 1. The size is m because again {0, 1, 2, . . . , m − 1} is a complete set of
residues
(2 cosets of a +mZ=b+mZ holds IFF a-b ∈mZ
overline(a)
The class of a modulo m is typically denoted by a-, or a + mZ, or [a].
Lemma 2.1.8 (Inverses and cancellation)
gcd(a, m) = 1 if and only if there exists b ∈ Z with ab ≡ 1 (mod m).
In particular, if gcd(a, m) = 1 and ax ≡ ay (mod m), then x ≡ y (mod m)
(Any integer coprime to m is invertible mod m)
PROOF
gcd(a, m) = 1 if and only if there exists b ∈ Z with ab ≡ 1 (mod m).
In particular, if gcd(a, m) = 1 and ax ≡ ay (mod m), then x ≡ y (mod m)
Proof. Suppose that gcd(a, m) = 1. By Bézout’s Lemma, there are s, t ∈ Z such that
sa + tm = 1. Let b = s: by definition, ab ≡ 1 (mod m). Conversely, suppose that
there is some b such that ab ≡ 1 (mod m). Then ab = 1 + km for some k ∈ Z, that is,
ab − km = 1, thus the greatest common divisor of a and m is 1.
necessary condition for inverse b of a mod m
Note that the condition gcd(a, m) = 1 is necessary: for instance, 8 ≡ 12 (mod 4), but
4 ̸≡ 6 (mod 4)!
Exercise 2.1.9. Show that if gcd(a, m) > 1, there are x, y ∈ Z such that ax ≡ ay
(mod m) and x ̸≡ y (mod m).
Let d ∈ N be the greatest common divisor of a and m. Then a(m/d)≡
0 ≡ a(2m/d) (mod m).
Now suppose that d > 1.
Then
m/d̸ ≡ 0 (mod m) and so
x := 2(m/d)̸≡ m/d =: y (mod m) satisfy the desired conclusion.
Exercise 2.1.10. Show that p is prime if and only if for every a ∈ Z, either a ≡ 0 (mod p) or there is b ∈ Z with ab ≡ 1 (mod p).
For every a ∈ Z we have either gcd(a, p) = 1 or gcd(a, p) = p, because those are the only positive divisors of p. In the former case, there is b such that ab ≡ 1 (mod p); in the latter, a ≡ 0 (mod p).
GROUP corollary under x
Corollary 2.1.11. The set
(Z/mZ)×
:= {a ∈ Z/mZ : gcd(a, m) = 1}
is well defined and it is a group under multiplication
checking group axioms: associativity a +b+c ≡a+b+c mod m
operation is taking representatives of equivalence classes and + mod m of congruence
inverse a+ -a ≡0 mod m
PROOF
Corollary 2.1.11. The set
(Z/mZ)×
:= {a ∈ Z/mZ : gcd(a, m) = 1}
is well defined and it is a group under multiplication
Proof. First, we need to check that if a- = b-, then gcd(a, m) = 1 implies gcd(b, m) = 1.
Indeed, if gcd(a, m) = 1 there is c such that ac ≡ 1 (mod m), but then bc ≡ ac ≡ 1 (mod m) too, hence gcd(b, m) = 1.
Next, recall that multiplication in Z/mZ is associative, just because it was on Z:
a(bc) ≡ (ab)c (mod m). Likewise, 1 is the multiplicative identity, and of course
1 ∈ (Z/mZ)× , because gcd(1, m) = 1.
Finally, if a, b are coprime with m, then gcd(ab, m) = 1 by Corollary 1.1.12, so (Z/mZ)× is closed under multiplication. Moreover, for each a ∈ (Z/mZ) × , there is b ∈ Z/mZ
such that ab ≡ 1 (mod m); such b must necessarily be in (Z/mZ)×
as well. Therefore,
(Z/mZ)× is a group under multiplication.
remark 2.1.12 rings
Remark 2.1.12. The quotient of Z/mZ is actually a ring, that is to say, a set with a sum and product satisfying certain properties (associativity, distributivity, etc). (In fact, if you know rings, you can verify that mZ is an ideal of Z, and so quotienting by mZ
gives us a ring.)
We do not use this language now, for simplicity, but keep this idea in the background: we will talk again about rings towards the end of the module
