# Euler Phi Function is Multiplicative

## Theorem

The Euler $\phi$ function is a multiplicative function:

- $m \perp n \implies \phi \left({m n}\right) = \phi \left({m}\right) \phi \left({n}\right)$

where $m, n \in \Z_{>0}$.

## Proof

Let $R = \left\{{r_1, r_2, \ldots, r_{\phi \left({m}\right)}}\right\}$ and $S = \left\{{s_1, s_2, \ldots, s_{\phi \left({n}\right)}}\right\}$ be the reduced residue systems for the respective moduli $m$ and $n$.

We are to show that the set of $\phi \left({m}\right) \phi \left({n}\right)$ integers:

- $T = \left\{{n r + m s: r \in R, s \in S}\right\}$

is a reduced residue system for modulus $m n$.

We need to establish the following:

- Each integer in $T$ is prime to $m n$;
- No two integers in $T$ is congruent modulo $m n$;
- Each integer prime to $m n$ is congruent modulo $m n$ to one of these integers in $T$.

We prove each in turn:

As $p$ divides $m n$ but $m \perp n$, $p$ either divides $m$ or $n$ but not both, from Divisors of Product of Coprime Integers.

Suppose WLOG that $p \mathop \backslash m$.

Then as $p \mathop \backslash n r + m s$, we have $p \mathop \backslash n r$ and hence $p \mathop \backslash r$.

But then $p \mathop \backslash \gcd \left\{{m, r}\right\} = 1$ which is a contradiction.

Similarly if $p \mathop \backslash n$.

So there is no such prime and hence $n r + m s \perp m n$.

- Suppose $n r + m s = n r' + m s' \left({\bmod\, m n}\right)$, where $r, r' \in R, s, s' \in S$.

Then:

- $n \left({r - r'}\right) + m \left({s - s'}\right) = k \left({m n}\right)$ for some $k \in \Z$.

As $m$ divides two of these terms it must divide the third, so $m \mathop \backslash n \left({r - r'}\right)$.

Now $m \perp n$ so by Euclid's Lemma $m \mathop \backslash \left({r - r'}\right)$, or $r \equiv r' \left({\bmod\, m}\right)$.

But $r$ and $r'$ are part of the same reduced residue system modulo $m$, so $r = r'$.

Similarly for $n$: we get $s = s'$.

Hence distinct elements of $T$ can not be congruent modulo $m n$.

- Let $k \in \Z: k \perp m n$.

Since $m \perp n$, from Set of Integer Combinations equals Set of Multiples of GCD we can write $ k = n r' + m s' $ for some $r', s' \in \Z$.

Suppose there exists some prime number $p$ such that $p \mathop \backslash m$ and $p \mathop \backslash r'$.

Such a prime would be a common divisor of both $k$ and $m n$, contradicting $k \perp m n$.

Hence $r' \perp m$ and so is congruent modulo $m $ to one of these integers in $R$.

By the same argument, $s' \perp n$ and so is congruent modulo $n$ to one of these integers in $S$.

Writing $r' = r + a m, \, s' = s + b n$ we have:

- $k = n r' + m s' = n r + m s + m n \left({a + b}\right) \equiv n r + m s \left({\bmod\, m n}\right)$.

Hence the result.

$\blacksquare$

## Sources

- Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(1968): $\S 1.2.4$: Exercises $30$ - Allan Clark:
*Elements of Abstract Algebra*(1971)... (previous)... (next): $\S 25$ - P.M. Cohn:
*Algebra Volume 1*(2nd ed., 1982)... (previous)... (next): $\S 2.3$: Congruences