[proofplan] We count units in residue class rings rather than reduced residue representatives directly. First we record the Bezout representation for coprime positive integers, then use it to prove the Chinese-remainder bijection between $\mathbb{Z}/mn\mathbb{Z}$ and $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$. This bijection is a ring isomorphism, so it restricts to a bijection on unit groups. Finally, [citetheorem:7884] identifies the sizes of these unit groups with the corresponding values of $\varphi$. [/proofplan] [step:Record the Bezout representation for coprime positive integers] We shall use the following elementary consequence of the [well-ordering principle](/theorems/721): if $x,y \in \mathbb{N}$ and $\gcd(x,y)=1$, then there exist $u,v \in \mathbb{Z}$ such that $ux+vy=1$. Indeed, define \begin{align*} S=\{\alpha x+\beta y : \alpha,\beta \in \mathbb{Z},\ \alpha x+\beta y>0\}. \end{align*} The set $S$ is nonempty because $x \in S$, so it has a least element $d$. Choose $\alpha_0,\beta_0 \in \mathbb{Z}$ such that $d=\alpha_0x+\beta_0y$. By the integer [division algorithm](/theorems/725), there exist $q,r \in \mathbb{Z}$ such that $x=qd+r$ and $0 \le r<d$. Since \begin{align*} r=x-qd=(1-q\alpha_0)x-q\beta_0y, \end{align*} the minimality of $d$ implies $r=0$. Hence $d \mid x$. The same argument with $y$ in place of $x$ gives $d \mid y$. Therefore $d$ is a positive common divisor of $x$ and $y$, so $d=1$ because $\gcd(x,y)=1$. Thus $1=\alpha_0x+\beta_0y$, as required. [/step] [step:Construct the Chinese remainder map as a ring isomorphism] For each $q \in \mathbb{N}$, let $R_q=\mathbb{Z}/q\mathbb{Z}$ denote the quotient ring, and let $\pi_q:\mathbb{Z}\to R_q$ be the quotient map. Define $\Phi:R_{mn}\to R_m\times R_n$, $\Phi(\pi_{mn}(a))=(\pi_m(a),\pi_n(a))$. This map is well-defined: if $\pi_{mn}(a)=\pi_{mn}(b)$, then $mn \mid a-b$, hence $m \mid a-b$ and $n \mid a-b$, so $\pi_m(a)=\pi_m(b)$ and $\pi_n(a)=\pi_n(b)$. Since addition and multiplication in quotient rings are induced from $\mathbb{Z}$, the map $\Phi$ preserves addition, multiplication, and the multiplicative identity. The kernel of $\Phi$ consists of those classes $\pi_{mn}(a)$ such that $m \mid a$ and $n \mid a$. Because $\gcd(m,n)=1$, the Bezout representation from the previous step gives $r,s \in \mathbb{Z}$ with $rm+sn=1$. If $m \mid a$ and $n \mid a$, then $mn \mid sna$ and $mn \mid rma$, hence \begin{align*} a=(rm+sn)a=rma+sna \end{align*} is divisible by $mn$. Thus $\ker \Phi=\{\pi_{mn}(0)\}$, so $\Phi$ is injective. To prove surjectivity, take an arbitrary pair $(\pi_m(b),\pi_n(c)) \in R_m\times R_n$. Choose $r,s \in \mathbb{Z}$ such that $rm+sn=1$, and define \begin{align*} a=snb+rmc. \end{align*} Modulo $m$, we have $sn=1-rm\equiv 1 \pmod m$ and $rmc\equiv 0 \pmod m$, so $\pi_m(a)=\pi_m(b)$. Modulo $n$, we have $sn b\equiv 0 \pmod n$ and $rm=1-sn\equiv 1 \pmod n$, so $\pi_n(a)=\pi_n(c)$. Hence $\Phi(\pi_{mn}(a))=(\pi_m(b),\pi_n(c))$, proving surjectivity. Therefore $\Phi$ is a ring isomorphism. [guided] The goal of this step is to turn one congruence modulo $mn$ into a pair of congruences modulo $m$ and modulo $n$. For each positive integer $q$, write $R_q=\mathbb{Z}/q\mathbb{Z}$ for the quotient ring and $\pi_q:\mathbb{Z}\to R_q$ for the quotient map. We define $\Phi:R_{mn}\to R_m\times R_n$, $\Phi(\pi_{mn}(a))=(\pi_m(a),\pi_n(a))$. First we verify that this is a well-defined map. The input $\pi_{mn}(a)$ can be represented by many integers $a$, so we must check that choosing a different representative does not change the output. If $\pi_{mn}(a)=\pi_{mn}(b)$, then $mn \mid a-b$. Since $m \mid mn$ and $n \mid mn$, it follows that $m \mid a-b$ and $n \mid a-b$. Therefore $\pi_m(a)=\pi_m(b)$ and $\pi_n(a)=\pi_n(b)$, so $\Phi$ is well-defined. Because quotient-ring addition and multiplication are inherited from addition and multiplication in $\mathbb{Z}$, this same formula also shows that $\Phi$ preserves sums, products, and the multiplicative identity. Now we prove injectivity. Suppose $\Phi(\pi_{mn}(a))=(\pi_m(0),\pi_n(0))$. This means exactly that $m \mid a$ and $n \mid a$. Since $\gcd(m,n)=1$, the Bezout representation proved in the previous step gives $r,s \in \mathbb{Z}$ such that $rm+sn=1$. Multiplying by $a$ gives $a=(rm+sn)a=rma+sna$. Because $n \mid a$, the term $rma$ is divisible by $mn$. Because $m \mid a$, the term $sna$ is divisible by $mn$. Hence their sum $a$ is divisible by $mn$, so $\pi_{mn}(a)=\pi_{mn}(0)$. Thus the kernel of $\Phi$ is trivial, and $\Phi$ is injective. Finally we prove surjectivity. Start with any pair $(\pi_m(b),\pi_n(c)) \in R_m\times R_n$. We want one integer whose residue is $b$ modulo $m$ and $c$ modulo $n$. Choose $r,s \in \mathbb{Z}$ with \begin{align*} rm+sn=1, \end{align*} and define \begin{align*} a=snb+rmc. \end{align*} Modulo $m$, the term $rmc$ vanishes and $sn=1-rm$ is congruent to $1$, so $\pi_m(a)=\pi_m(b)$. Modulo $n$, the term $snb$ vanishes and $rm=1-sn$ is congruent to $1$, so $\pi_n(a)=\pi_n(c)$. Therefore $\Phi(\pi_{mn}(a))=(\pi_m(b),\pi_n(c))$. Since the target pair was arbitrary, $\Phi$ is surjective. We have proved that $\Phi$ is a ring isomorphism. [/guided] [/step] [step:Restrict the ring isomorphism to a bijection of unit groups] For each $q \in \mathbb{N}$, let $U_q=R_q^\times$ be the group of units of the ring $R_q$. Since $\Phi:R_{mn}\to R_m\times R_n$ is a ring isomorphism, it sends units to units and non-units to non-units. More explicitly, an element $x \in R_{mn}$ is a unit iff there exists $y \in R_{mn}$ with $xy=1_{R_{mn}}$, and applying $\Phi$ gives $\Phi(x)\Phi(y)=1_{R_m\times R_n}$. The converse follows by applying $\Phi^{-1}$. An element $(u,v)\in R_m\times R_n$ is a unit iff $u\in U_m$ and $v\in U_n$, because multiplication in the product ring is componentwise. Therefore $\Phi$ restricts to a bijection $\Phi^\times:U_{mn}\to U_m\times U_n$. Taking cardinalities gives $|U_{mn}|=|U_m\times U_n|$. Since $U_m$ and $U_n$ are finite sets, the cardinality of their Cartesian product is $|U_m\times U_n|=|U_m||U_n|$. [/step] [step:Translate the unit count into the totient identity] By [citetheorem:7884], for every $q \in \mathbb{N}$ one has $|R_q^\times|=\varphi(q)$. Applying this with $q=mn$, $q=m$, and $q=n$, and using the unit-group bijection from the previous step, we obtain $\varphi(mn)=|U_{mn}|=|U_m||U_n|=\varphi(m)\varphi(n)$. This is the desired multiplicativity formula for $\varphi$ when $\gcd(m,n)=1$. [/step]