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 \backslash m$.
Then as $p \backslash n r + m s$, we have $p \backslash n r$ and hence $p \backslash r$.
But then $p \backslash \gcd \left\{{m, r}\right\} = 1$ which is a contradiction.
Similarly if $p \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 \backslash n \left({r - r'}\right)$.
Now $m \perp n$ so by Euclid's Lemma $m \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 Integer Combinations 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 \backslash m$ and $p \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$
