5Modular arithmetic
IA Numbers and Sets
5.2 Multiple moduli
In this section, we are concerned with multiple equations involving different
moduli.
Suppose we are given
x ≡
2 (
mod
3) and
x ≡
1 (
mod
4). What is the general
solution to
x
? We work in mod 12. Since we are given that
x ≡
2 (
mod
3),
we know that
x ≡
2
,
5
,
8 or 11 (
mod
12). Similarly, since
x ≡
1 (
mod
4), we
must have
x ≡
1
,
5 or 9 (
mod
12). Combining these results, we must have
x ≡
5
(mod 12).
On the other hand, if
x ≡
5 (
mod
12), then
x ≡
5
≡
2 (
mod
3) and
x ≡
5
≡
1
(mod 4). So x ≡ 5 (mod 12) is indeed the most general solution.
In general, we have the Chinese remainder theorem.
Theorem
(Chinese remainder theorem)
.
Let (
m, n
) = 1 and
a, b ∈ Z
. Then
there is a unique solution (modulo mn) to the simultaneous congruences
(
x ≡ a (mod m)
x ≡ b (mod n)
,
i.e. ∃x satisfying both and every other solution is ≡ x (mod mn).
Proof.
Since (
m, n
) = 1,
∃u, v ∈ Z
with
um
+
vn
= 1. Then
vn ≡
1 (
mod m
)
and
um ≡
1 (
mod n
). Put
x
=
umb
+
vna
. So
x ≡ a
(
mod m
) and
x ≡ b
(mod n).
To show it is unique, suppose both
y
and
x
are solutions to the equation.
Then
y ≡ a (mod m) and y ≡ b (mod n)
⇔ y ≡ x (mod m) and y ≡ x (mod n)
⇔ m | y − x and n | y − x
⇔ mn | y − x
⇔ y ≡ x (mod mn)
This shows a congruence (mod
mn
) is equivalent to one (mod
n
) and another
(mod m).
We can easily extend this to more than two moduli by repeatedly applying
this theorem.
Proposition.
Given any (
m, n
) = 1,
c
is a unit mod
mn
iff
c
is a unit both
mod m and mod n.
Proof.
(
⇒
) If
∃u
such that
cu ≡
1 (
mod mn
), then
cu ≡
1 (
mod m
) and
cu ≡
1
(mod n). So c is a unit mod m and n.
(
⇐
) Suppose there exists
u, v
such that
cu ≡
1 (
mod m
) and
cv ≡
1 (
mod n
).
Then by CRT,
∃w
with
w ≡ u
(
mod m
) and
w ≡ v
(
mod n
). Then
cw ≡ cu ≡
1
(mod m) and cw ≡ cv ≡ 1 (mod n).
But we know that 1
≡
1 (
mod m
) and 1
≡
1 (
mod n
). So 1 is a solution to
cw ≡
1 (
mod m
),
cw ≡
1 (
mod n
). By the “uniqueness” part of the Chinese
remainder theorem, we must have cw ≡ 1 (mod mn).
Definition
(Euler’s totient function)
.
We denote by
φ
(
m
) the number of integers
a, 0 ≤ a ≤ m, such that (a, m) = 1, i.e. a is a unit mod m. Note φ(1) = 1.
Proposition.
(i) φ(mn) = φ(m)φ(n) if (m, n) = 1, i.e. φ is multiplicative.
(ii) If p is a prime, φ(p) = p − 1
(iii) If p is a prime, φ(p
k
) = p
k
− p
k−1
= p
k
(1 − 1/p)
(iv) φ(m) = m
Q
p|m
(1 − 1/p).
Proof. We will only prove (iv). In fact, we will prove it twice.
(i) Suppose m = p
k
1
1
p
k
2
2
···p
k
`
`
. Then
φ(m) = φ(p
k
1
1
)φ(p
k
2
2
) ···φ(p
k
`
`
)
= p
k
1
1
(1 − 1/p
1
)p
k
2
2
(1 − 1/p
2
) ···p
k
`
`
(1 − 1/p
`
)
= m
Y
p|m
(1 − 1/p)
(ii)
Let
m
=
p
k
1
1
p
k
2
2
···p
k
`
`
. Let
X
=
{
0
, ···m −
1
}
. Let
A
j
=
{x ∈ X
:
p
j
| x}
.
Then
|X|
=
m
,
|A
j
|
=
m/p
j
,
|A
i
∩ A
j
|
=
m/
(
p
i
p
j
) etc. So
φ
(
m
) =
|
¯
A
1
∩
¯
A
2
∩ ···
¯
A
`
| = m
Q
p|m
(1 − 1/p).
Example. φ(60) = 60(1 − 1/2)(1 − 1/3)(1 − 1/5) = 16.
If
a, b
are both units (mod
m
), then so is
ab
, for if
au ≡
1 and
bv ≡
1, then
(ab)(uv) ≡ 1. So the units form a multiplicative group of size φ(m).