Appendix A: Mathematical Facts - Codes: The Guide to Secrecy from Ancient to Modern Times - page 478

Proof . See [169, Theorem 2.29, page 69].

✷
The natural generalization of Fermat's Little Theorem (given below) is the
following, which provides the modulus for the RSA enciphering and deciphering
exponents, for instance.

Definition A.22 ( Euler's φ -Function )
For any n the Euler φ -function , also known as Euler's Totient φ ( n ) is

defined to be the number of m

∈ N

∈ N such that m<n and gcd( m,n )=1 .

Theorem A.13 ( The Arithmetic of the Totient )
If n = j =1 p a j j where the p j are distinct primes, then

1 .

k k k

= n
p j n

1
p j

p a j − 1
j

1) p a j − 1
j

φ ( p a j )= ( p a j

j

φ ( n )= − )= ( p j − −

j =1 j =1 j =1

Proof . See [169, Theorem 2.22, page 65].

✷

Theorem A.14 ( Euler's Generalization of Fermat's Little Theorem )
If n such that gcd( m,n )=1 , then m φ ( n )

∈ N and m ∈ Z ≡ 1 (mod n ) .

Proof . See [167, Theorem 2.3.1, page 90].

✷

Corollary A.2 ( Fermat's Little Theorem )
If a and p is prime such that gcd( a,p )=1 , then a p − 1

∈ Z ≡ 1 (mod p ) .

) ∗ is φ ( n ) . Hence, if

Example A.6 Let n ∈ N . Then the cardinality of ( Z /n Z

| φ ( n ) . ) ∗ ,

G is a subgroup of ( Z /n Z | G

The calculus of integer orders and related primitive roots is an underlying
fundamental feature of cryptographic problems such as the discrete log problem.

Definition A.23 ( Modular Order of an Integer)
Let m

∈ Z , n ∈ N and gcd( m,n )=1 . The order of m modulo n is the

smallest e 1 (mod n ) , denoted by e = ord n ( m ) , and we say

that m belongs to the exponent e modulo n .

∈ N such that m e ≡

Note that the modular order of an integer given in Definition A.23 is the
same as the element order in the group (

Z Z

) ∗ . /n

Proposition A.3 ( Divisibility by the Order of an Integer)
If m such that gcd( m,n )=1 , then m d

∈ Z , d,n ∈ N ≡ 1 (mod n ) if and

only if ord n ( m ) d . In particular, ord n ( m ) φ ( n ) .