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.