Euler’s phi function is multiplicative

This post gives a proof that Euler’s phi function is multiplicative. The proof is a simpler and more elegant proof, as compared to the one presented here. The combinatorial argument is greatly simplified using the Chinese remainder theorem (abbreviated CRT).

The letter m is used below to denote the modulus in modular arithmetic. The phi function \phi(m) is defined to be the count of all the integers 0 \le a \le m-1 such that a and m are relatively prime. If m is prime, then \phi(m)=m-1 since all integers from 1 to m-1 have no factors in common with m (other than 1). If m=10, then \phi(10)=4 since 1, 3, 7, and 9 are the only numbers that are relatively prime to m=10.

To properly work with the phi function, conmsider the following setting. Given a modulus m, a set of interest is \mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}. This is the set of all least resdues modulo m, i.e., every integer is congruent modulo m to exactly one element of \mathbb{Z}_m. Another set of interest is \mathbb{Z}_m^*, which is the set of all elements a in \mathbb{Z}_m such that a and m are relatively prime. In other words, \phi(m) is defined to be the cardinality of the set \mathbb{Z}_m^*.

The set \mathbb{Z}_m is called the ring of integers modulo m since it satisfies the definition of a ring with regard to addition and multiplication modulo m. The set \mathbb{Z}_m^* with the multiplication modulo m is a group, i.e. every element of \mathbb{Z}_m^* has a multiplicative inverse with respect to the binary operation of multiplication modulo m. The set \mathbb{Z}_m^* is called the multiplicative group of integers modulo m. The fact that \mathbb{Z}_m^* is a group is established by the following theorem, which is proved here.

Theorem 1
Let a be an integer in \mathbb{Z}_m. The following conditions are equivalent.

  1. The numbers a and m are relatively prime, i.e. \text{GCD}(a,m)=1.
  2. There is a b \in \mathbb{Z}_m such that a \cdot b \equiv 1 \ (\text{mod} \ m).
  3. Some positive power of a modulo m is 1, i.e., a^n \equiv 1 \ (\text{mod} \ m) for some positive integer n.

Another interesting fact to point out is that when m is a prime number, \mathbb{Z}_m is a field, i.e. it is a commutative ring in which every non-zero element has a multiplicative inverse. Another terminology that is used by some authors is that the elements in \mathbb{Z}_m that have multiplicative inverses are called units. Thus \mathbb{Z}_m^* is also called the group of units of the ring of integers modulo m. Our notation here is not standard. The usual notation for the ring \mathbb{Z}_m is \mathbb{Z}/m\mathbb{Z}. The usual notation for \mathbb{Z}_m^* is (\mathbb{Z}/m\mathbb{Z})^*.

The phi function is multiplicative in the following sense.

Theorem 2
Let m and n be positive integers such that they are relatively prime. Then \phi(m \times n)=\phi(m) \times \phi(n).

Theorem 2 is established by the following results.

Lemma 3
Let m and n be positive integers such that they are relatively prime. Then the set \mathbb{Z}_{mn} and the set \mathbb{Z}_m \times \mathbb{Z}_n have the same cardinality.

Proof
To prove that the two sets have the same cardinality, we define a bijection f: \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n, i.e. f is a one-to-one function that maps \mathbb{Z}_{mn} onto the set \mathbb{Z}_m \times \mathbb{Z}_n. For each a \in \mathbb{Z}_{mn}=\left\{0,1,2,\cdots,m \cdot n-1 \right\}, define f(a)=(c, d) where c \in \mathbb{Z}_m with c \equiv a \ (\text{mod} \ m) and d \in \mathbb{Z}_n with d \equiv a \ (\text{mod} \ n).

To see that f is one-to-one, let f(a)=f(b). Then we have a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). By the Chinese remainder theorem, a \equiv b \ (\text{mod} \ mn). Since a,b \in \mathbb{Z}_{mn}, a=b.

To show that f maps \mathbb{Z}_{mn} onto the set \mathbb{Z}_m \times \mathbb{Z}_n, let (c,d) \in \mathbb{Z}_m \times \mathbb{Z}_n. Consider the equations x \equiv c \ (\text{mod} \ m) and x \equiv d \ (\text{mod} \ n). By CRT, these two equations have a simultaneous solution a that is unique modulo m \times n. This means that f(a)=(c, d). \square

Lemma 4
Let m and n be positive integers such that they are relatively prime. Then the set \mathbb{Z}_{mn}^* and the set \mathbb{Z}_m^* \times \mathbb{Z}_n^* have the same cardinality.

Proof
The same mapping f defined in the proof of Lemma 3 is used. We show that when f is restricted to the set \mathbb{Z}_{mn}^*, it is a bijection from \mathbb{Z}_{mn}^* onto the set \mathbb{Z}_m^* \times \mathbb{Z}_n^*. First, we show that for any a \in \mathbb{Z}_{mn}^*, f(a) is indeed in \mathbb{Z}_m^* \times \mathbb{Z}_n^*. To see this, note that a and m \times n are relatively prime. So it must be that a and m are relatively prime too and that a and n are relatively prime.

The function f is one-to-one as shown above. The remaining piece is that for each (c,d) \in \mathbb{Z}_m^* \times \mathbb{Z}_n^*, there is some a \in \mathbb{Z}_{mn}^* such that f(a)=(c,d). As in the proof of Lemma 3, there is some a \in \mathbb{Z}_{mn} such that f(a)=(c,d). Note that a and m are relatively prime and a and n are relatively prime. This means that a and m \times n are relatively prime (see Lemma 4 here). Thus the function f is a one-to-one from \mathbb{Z}_{mn}^* onto \mathbb{Z}_m^* \times \mathbb{Z}_n^*. \square

Proof of Theorem 2
Lemma 4 shows that the set \mathbb{Z}_{mn}^* and the set \mathbb{Z}_m^* \times \mathbb{Z}_n^* have the same cardinality. First, \phi(m \times n) is the cardinality of the set \mathbb{Z}_{mn}^*. Theorem 2 is established by noting that \phi(m) \times \phi(n) is the cardinality of \mathbb{Z}_m^* \times \mathbb{Z}_n^*. \square

____________________________________________________________________________

Evaluating the phi function

The combinatorial argument for \phi(m \times n)=\phi(m) \times \phi(n) is greatly simplified by using the Chinese remainder theorem. Compare the above proof with the lengthier proof in an earlier post (see Theorem 3 here). With the multiplicative property of the phi function, we can evaluate the phi function for any positive integer.

For any positive integer m, consider its unique prime factorization m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}. Then we have:

    \displaystyle \begin{aligned} \phi(m)&=\phi(p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}) \\&=\phi(p_1^{e_1}) \times \phi(p_2^{e_2}) \times \cdots \times \phi(p_t^{e_t}) \\&=p_1^{e_1-1} \cdot (p_1-1) \times p_2^{e_2-1} \cdot (p_2-1) \times \cdots \times p_t^{e_t-1} \cdot (p_t-1) \\&=p_1^{e_1} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times p_2^{e_2} \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times p_t^{e_t} \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times  \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times  \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=m \cdot \biggl(1-\frac{1}{p_1}\biggr) \times  \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times  \cdot \biggl(1-\frac{1}{p_t}\biggr)\end{aligned}

In the above evaluation, this fact is used. For any prime p, \phi(p^n)=p^{n-1} \times (p-1) (see see Theorem 2 here). We also use the extended version of Theorem 2: if m_1,m_2,\cdots,m_t are pairwise relatively prime, then

    \phi(m_1 \times m_2 \times \cdots \times m_t)=\phi(m_1) \times \phi(m_2) \times \cdots \times \phi(m_t).

The extended result is to extend the product to more than two numbers. It is derived by a simple inductive argument.

____________________________________________________________________________

A formula for the phi function

The above evaluation leads us to the following way to express the phi function. For m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}, we have the following:

    \displaystyle \phi(m)=m \ \prod \limits_{p \lvert m} \biggl( 1-\frac{1}{p} \biggr)

In the above product, the p ranges over all prime divisors of m. A quick example: for 33075=3^3 \cdot 5^2 \cdot 7^2,

    \displaystyle \begin{aligned}\phi(33075)&=33075 \times \biggl( 1-\frac{1}{3} \biggr) \times \biggl( 1-\frac{1}{5} \biggr) \times \biggl( 1-\frac{1}{7} \biggr) \\&=33075 \times \frac{2}{3} \times \frac{4}{5} \times \frac{6}{7} \\&=315 \times 2 \times 4 \times 6 \\&=15120 \end{aligned}

One comment. For the above formula to work, we only need to know the prime divisors of the number, not necessarily the powers of the primes. For example, for 33075, we only need to know that the prime divisors are 3, 5 and 7.

____________________________________________________________________________

\copyright \ 2015 \text{ by Dan Ma}

Advertisements

One thought on “Euler’s phi function is multiplicative

  1. Pingback: Speeding up modular exponentiation using CRT | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s