This is our first post of an introductory discussion on Euler’s phi function. The next post on phi function is here.
___________________________________________________________________________________________________________________
Setting Up the Scene
The starting point of this discussion is the relative primality of two integers. Two positive integers and
are relatively prime if
is the only common divisor of
and
. Note that
and
need not be prime. For example,
and
are relatively prime, as are
and
. It is clear that
and
are relatively prime if and only if they share no common prime factors. The last point is equivalent to the condition that the greatest common divisor of
and
is
. Our notation for greatest common divisor is
.
If and
are relatively prime, we also say that
is relatively prime to
or
is relatively prime to
. In the remainder of the blog post,
is always a positive integer that is the modulus used for modular arithmetic.
In modular arithmetic where the modulus is , we only need to focus on
distinct numbers, namely the elements in the set
. Any integer is congruent modulo
to exactly one element of this set (the elements of this set are also called the least residues modulo
). For convenience, we use the notation
.
An even more interesting set is the set of all integers in
such that
and the modulus
are relatively prime. To facilitate the discussion, we describe this set as follows:
When the modulus is a prime number,
, the non-zero elements of
. When the modulus is not prime, there are fewer least residues that are relatively prime to the modulus. The following shows
for the first several integers.
The following theorem gives some indication why is an interesting set, which provides alternative characterizations of
.
Theorem 1
Let be an integer in
. The following conditions are equivalent.
.
- There is a
such that
.
- Some positive power of
modulo
is
, i.e.,
for some positive integer
.
The number indicated in condition 2 is said to be the multiplicative inverse of
. Theorem 1 says that only the least residues that are relatively prime to the modulus have multiplicative inverses. Condition 3 tells us that to have a power congruent to one, which is of interest in many situations, the base must be relatively prime to the modulus.
We need the following lemma to prove Theorem 1.
Lemma 2
If , then for any positive integer
,
is also relatively prime to
.
Proof of Lemma 2
Suppose . By the extended Euclidean algorithm, we have the following:
for some integers and and
.
We prove by induction on . When
, lemma is true. Suppose that
is relatively prime to
where
. We show that
is relatively prime to
. Multiple both sides of (1) by
. We have
. Let
. Note that
is a divisor of the left-hand side of
. So
is a divisor of
. Now we know that
is a common divisor of
and
. Then
, which means that
is relatively prime to
.
Proof of Theorem 1
Suppose that for some positive integer
. If
, then let
. If
, then let
. Either way, there is
such that
.
Suppose there is a such that
. Then we have
for some integer .
Let . Since
divides both numbers in the left-hand side of (2),
. Then
.
Suppose . Consider the
and then consider their least residues modulo
. By Lemma 2, each
and
are relatively prime. Hence the least residue of
and
are also relatively prime. But there are only finitely many least residues modulo
. So there exist positive integers
the least residues of
and
are identical.
We have . Since
and
are relatively prime, we can cancel out
on both sides. Thus
.
___________________________________________________________________________________________________________________
Euler’s Phi Function
The Euler’s phi function, denoted by , is the number of integers
where
such that
and the modulus
are relatively prime. In light of the above discussion,
is the number of elements in the set
. It is also the case that
is the number of elements in
that satisfies any one of the three conditions in Theorem 1.
If the modulus is a prime number, then
. The following shows several values of
.
When the modulus is a prime number, Fermat’s little theorem tells us that
for any
. This fact is true even when the modulus is not prime if the power is kept as
. We have the following theorem.
Theorem 3 (Euler’s Theorem)
We have for any integer
that is relatively prime to the modulus
.
Theorem 3 can also be stated as: for any
. The proof is amazingly similar to that of Fermat’s little theorem (see the post Proving Fermat’s Little Theorem). We use the following lemma in proving Theorem 3.
Lemma 4
If integers and
satisfy any condition in Theorem 1, then so does the product
.
Proof of Lemma 4
Since the 3 conditions in Theorem 1 are equivalent, it does not matter which one we pick. Condition 2 is probably the most convenient. So we show that if has a multiplicative inverse and
has a multiplicative inverse, then
has a multiplicative inverse modulo
.
Suppose and
for some integers
and
in
. We multiply the two congruences and obtain:
if is in
, then it is the multiplicative inverse of
. If not, then take the least residue mod
.
Proof of Theorem 3
Let be an integer that is relatively prime to the modulus
, i.e.,
. Let
enumerate the
many elements of
. Multiply these elements by
and we have the following set:
Consider the least residues modulo of the members of the set
. We have:
Note that for each ,
and
. We have two claims.
- The numbers
and
are distinct whenever
.
- Each
is relatively prime to the modulus
, i.e.,
for each
.
The first claims tells us that the set has
many distinct elements. The second claims tells us that the set
is a subset of
. Since the subset
has
many distinct elements and
has
many distinct elements, they must equal. So we have
. With this information, we have the following congruence equation.
Because each is relatively prime to the modulus, we can cancel out all
and obtain:
So the theorem hinges on the two claims listed above. We now prove them one by one. To show the first claim, suppose . Then
. We can cancel out
on both sides since
is relatively prime to
. We have
. Since both
and
are least residues mod
, for them to be congruent to each other, the only possibility is
. Thus
. The contrapositive of what we just show is that if
, then
. So the numbers
are all distinct.
To show the second claim, note that . Both
and
are relatively prime to
. So by Lemma 4,
is relatively prime to
. Hence
is relatively prime to the modulus
.
___________________________________________________________________________________________________________________
Comments
The setting for the phi function deserves some comments. The sets and
defined above can be considered as algebraic objects.
The set along with addition and multiplication modulo
is a ring. Thus
is often called the ring of integers modulo
.
Based on Theorem 1 and Lemma 4, the set with the multiplication modulo
is a group, i.e., it is a set with a binary operation called multiplication such that every element has an inverse.
Let the modulus is a prime number. As indicated above,
. An interesting angle is that
can be considered a commutative ring in which every non-zero element has a multiplicative inverse, i.e.,
is a field (in fact a finite field).
Though we do not focus too much on the algebraic side of things in this blog, , as a field, plays an important role in number theory and has applications in cryptography.
___________________________________________________________________________________________________________________
Pingback: Counting Fermat witnesses | Exploring Number Theory
Pingback: The Fermat primality test | Mathematical Cryptography
Pingback: Euler’s phi functon is multiplicative | Exploring Number Theory
Pingback: Euler’s phi function is multiplicative | Exploring Number Theory
Pingback: Speeding up modular exponentiation using CRT | Exploring Number Theory