----- > [!proposition] Proposition. ([[multiplicativity of Euler phi function]]) >The [[Euler phi function]] is multiplicative: if [[greatest common divisor]]$(m,n)=1$, then $\phi(mn)=\phi(m)\phi(n)$. ^5af49d > [!proof]- Proof. ([[multiplicativity of Euler phi function]]) > For $\ell \in \mathbb{N}$, define $\varphi_{\ell}:=\{ a \in [\ell]: \text{gcd}(a,\ell)=1 \}$. (So, $\phi(n)=|\phi(\ell)|$.) Suppose $m,n$ are such that [[greatest common divisor]]$(m,n)=1$. We want to show that $|\varphi_{mn}|=|\varphi_{n}| | \varphi_{m}|=|\varphi_{n} \times \varphi_{m}|$, and will do so by constructing a [[bijection]] $\Phi: \varphi_{mn} \leftrightarrow \varphi_{m} \times \varphi_{n}$. The claim is that defining $\Phi(\ell):= (\ell \text{ mod }m, \ell \text{ mod }n)$ establishes the desired correspondence. \ That $\Phi$ indeed maps between $\varphi_{mn}$ and $\varphi_{m} \times \varphi_{n}$ is true by [[product of two numbers that are coprime to a third]] and [[mod preserves coprimeness]]: $\text{gcd}(\ell,mn)=1$ implies $\text{gcd}(\ell,m)=\text{gcd}(\ell,n)=1$ implies $\text{gcd}(\ell \text{ mod }m, m)=1$; likewise $\text{gcd}(\ell,mn)=1$ implies $\text{gcd}(\ell \text{ mod }n, n)=1$. \ Now to show $\Phi$ is a [[bijection]]: by the [[Chinese remainder theorem]], the system $\begin{align} x \text{ mod }m=a \\ x \text{ mod } n = b \end{align} $ has a unique solution ($\text{mod }mn$). Thus, if $(a,b) \in \varphi_{m} \times \varphi_{n}$, then there exists $x$ such that $(a,b)=(x \text{ mod } a, x \text{ mod }b)$ and this $x$ is unique modulo $mn$. Now, because we can find integers $\alpha$ and $\beta$ for which $x=a+ \alpha m=b+\beta m$ and $\text{gcd}(a,m)=1$ since $a \in \varphi_{m}$, $\text{gcd}(x,m)=1$. Likewise, since $\text{gcd}(b,m)=1$ since $b \in \varphi_{n}$, $\text{gcd}(x,n)=1$. Therefore, $\text{gcd}(x,mn)=1$ and so $x \in \varphi(mn)$. \ Thus, for all $(a,b)$ in $\varphi_{m} \times \varphi_{n}$, there exists $x \in \varphi_{mn}$ such that $\Phi(x)=(a,b)$. Moreover, this $x$ is unique (modulo $mn$, which is exactly what we need). Hence $\Phi$ is [[injection|injective]] and [[surjection|surjective]]. ^a4bb81 ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```