5Modular arithmetic
IA Numbers and Sets
5.3 Prime moduli
Modular arithmetic has some nice properties when the modulus is a prime
number.
Theorem (Wilson’s theorem). (p − 1)! ≡ −1 (mod p) if p is a prime.
Proof.
If
p
is a prime, then 1
,
2
, ··· , p −
1 are units. Among these, we can pair
each number up with its inverse (e.g. 3 with 4 in modulo 11). The only elements
that cannot be paired with a different number are 1 and
−
1, who are self-inverses,
as show below:
x
2
≡ 1 (mod p)
⇔ p | (x
2
− 1)
⇔ p | (x − 1)(x + 1)
⇔ p | x − 1 or p | x + 1
⇔ x ≡ ±1 (mod p)
Now (
p −
1)! is a product of (
p −
3)
/
2 inverse pairs together with 1 and
−
1. So
the product is −1.
Theorem
(Fermat’s little theorem)
.
Let
p
be a prime. Then
a
p
≡ a
(
mod p
)
for all a ∈ Z. Equivalently, a
p−1
≡ 1 (mod p) if a 6≡ 0 (mod p).
Proof. Two proofs are offered:
(i)
The numbers
{
1
,
2
, ···p −
1
}
are units modulo
p
and form a group of order
p − 1. So a
p−1
≡ 1 by Lagrange’s theorem.
(ii)
If
a 6≡
0, then
a
is a unit. So
ax ≡ ay
iff
x ≡ y
. Then
a,
2
a,
3
a, ···
(
p −
1)
a
are distinct mod
p
. So they are congruent to 1
,
2
, ···p −
1 in some order.
Hence
a ·
2
a ···
3
a ···
(
p −
1)
a ≡
1
·
2
·
3
···
(
p −
1). So
a
p−1
(
p −
1)!
≡
(
p −
1)!.
So a
p−1
≡ 1 (mod p).
Neither Wilson nor Fermat’s theorem hold if the modulus is non-prime.
However, Fermat’s theorem can be generalized:
Theorem (Fermat-Euler Theorem). Let a, m be coprime. Then
a
φ(m)
≡ 1 (mod m).
Proof. Lagrange’s theorem: The units mod m form a group of size φ(m).
Alternatively, let
U
=
{x ∈ N
: 0
< x < m,
(
x, m
) = 1
}
. These are
the
φ
(
m
) units. Since
a
is a unit,
ax ≡ ay
(
mod m
) only if
x ≡ y
(
mod m
).
So if
U
=
{u
1
, u
2
, ··· , u
φ(m)
}
, then
{au
1
, au
2
, ···au
φ(m)
}
are distinct and are
units. So they must be
u
1
, ···u
φ(m)
in some order. Then
au
1
au
2
···au
φ(m)
≡
u
1
u
2
···u
φ(m)
. So
a
φ(m)
z ≡ z
, where
z
=
u
1
u
2
···u
φ(m)
. Since
z
is a unit, we
can multiply by its inverse and obtain a
φ(m)
≡ 1.
Definition
(Quadratic residues)
.
The quadratic residues are the “squares” mod
p, i.e. 1
2
, 2
2
, ··· , (p − 1)
2
.
Note that if
a
2
≡ b
2
(
mod p
), then
p | a
2
−b
2
= (
a −b
)(
a
+
b
). Then
p | a −b
or
p | a
+
b
. So
a ≡ ±b
(
mod p
). Thus every square is a square of exactly two
numbers.
Example.
If
p
= 7, then 1
2
≡
6
2
≡
1, 2
2
≡
5
2
≡
4, 3
2
≡
4
2
≡
2. So 1
,
2
,
4 are
quadratic residues. 3, 5, 6 are not.
Proposition.
If
p
is an odd prime, then
−
1 is a quadratic residue if and only if
p ≡ 1 (mod 4).
Proof.
If
p ≡
1 (
mod
4), say
p
= 4
k
+ 1, then by Wilson’s theorem,
−
1
≡
(
p −
1)!
≡
1
·
2
···
p−1
2
−
p−1
2
···
(
−
2)(
−
1)
≡
(
−
1)
p−1
2
p−1
2
!
2
= (
−
1)
2k
(2
k
!)
2
≡
(2k!)
2
. So −1 is a quadratic residue.
When
p ≡ −
1 (
mod
4), i.e.
p
= 4
k
+ 3, suppose
−
1 is a square, i.e.
−
1
≡ z
2
.
Then by Fermat’s little theorem, 1
≡ z
p−1
≡ z
4k+2
≡
(
z
2
)
2k+1
≡
(
−
1)
2k+1
≡ −
1.
Contradiction.
Proposition.
(Unproven) A prime
p
is the sum of two squares if and only if
p ≡ 1 (mod 4).
Proposition. There are infinitely many primes ≡ 1 (mod 4).
Proof.
Suppose not, and
p
1
, ···p
k
are all the primes
≡
1 (
mod
4). Let
N
=
(2
p
1
···p
k
)
2
+1. Then
N
is not divisible by 2 or
p
1
, ··· , p
k
. Let
q
be a prime
q | N
.
Then
q ≡ −
1 (
mod
4). Then
N ≡
0 (
mod q
) and hence (2
p
1
···p
k
)
2
+ 1
≡
0
(
mod q
), i.e. (2
p
1
···p
k
)
2
≡ −
1 (
mod q
). So
−
1 is a quadratic residue mod
q
,
which is a contradiction since q ≡ −1 (mod 4).
Proposition.
Let
p
= 4
k
+ 3 be a prime. Then if
a
is a quadratic residue, i.e.
a ≡ z
2
(mod p) for some z, then z = ±a
k+1
.
Proof.
By Fermat’s little theorem,
a
2k+1
≡ z
4k+2
≡ z
p−1
≡
1. If we multiply by
a, then a
2k+2
≡ a (mod p). So (±a
k+1
)
2
≡ a (mod p).
This allows us to take square roots efficiently. This efficiency requires an
effective way of computing powers of
a
efficiently. This can be done by repeated
squaring. For example, to find
a
37
, we can calculate this by
a
37
=
a
32
a
4
a
1
=
((((
a
2
)
2
)
2
)
2
)
2
·
(
a
2
)
2
·a
. Thus calculation of
a
n
has time complexity
O
(
log n
), as
opposed to O(n) if you take powers manually.
Suppose
a
is a square mod
n
, where
n
=
pq
and
p, q
are distinct primes. Then
a
is a square mod
p
and a square mod
q
. So there exists some
s
with (
±s
)
2
≡ a
(
mod p
) and some
t
with (
±t
)
2
≡ a
(
mod q
). By the Chinese remainder theorem,
we can find a unique solution of each case, so we get 4 square roots of
a
modulo
n.