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
p1
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
p1
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
p1
(
p
1)!
(
p
1)!.
So a
p1
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
···
p1
2
p1
2
···
(
2)(
1)
(
1)
p1
2
p1
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
p1
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
p1
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.