Lecture 4
(Definition) Complete Residue System:
A
complete residue system mod m
is a collection of integers
a
1
. . . a
m
such that
a
i
6≡ a
j
mod m
if
i = j
and any
integer n is congruent to some a
i
mod m
(Definition) Reduced Residue System:
A
reduced residue system mod m
is
a collection of integers
a
1
. . . a
k
such that
a
i
6≡ a
j
mod m
if
i = j
and
(a
i
, m) = 1
for all
i
, and any integer
n
coprime to
m
must be congruent to some
a
i
mod m
.
Eg., take any complete residue system mod
m
and take the subset consisting of
all the integers in it which are coprime to
m
- these will form a reduced residue
system
Eg. For m = 12
complete = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
reduced = {1, 5, 7, 11}
(Definition) Euler’s Totient Function:
The number of elements in a reduced
residue system mod
m
is called
Euler’s totient function
:
φ(m)
(ie., the number
of positive integers ≤ m and coprime to m)
Theorem 15 (Euler’s Theorem).
If (a, m) = 1, then a
φ(m)
≡ 1 mod m
Proof.
Lemma 16.
If
(a, m) = 1
and
r
1
. . . r
k
is a reduced residue system mod
m
,
k = φ(m)
,
then ar
1
. . . ar
k
is also a reduced residue system mod m.
Proof.
All we need to show is that
ar
i
are all coprime to
m
and distinct mod
m
,
since there are
k
of these
ar
i
and
k
is the number of elements in any residue
system mod
m
. We know that if
(r, m) = 1
and
(a, m) = 1
then
(ar, m) = 1
.
Also, if we had
ar
i
≡ ar
j
mod m
, then
m|ar
i
− ar
j
= a(r
i
− r
j
)
. If
(a, m) = 1
then m|r
i
− r
j
⇒ r
i
≡ r
j
mod m, which cannot happen unless i = j.
Choose a reduced residue system
r
1
. . . r
k
mod m
with
k = φ(m)
. By lemma,
ar
1
. . . ar
k
is also a reduced residue system. These two must be permutations of
6
6
FFermat, Euler, Wilson, Linear Congruences
我的内容管理
展开
