I've tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn't look like the proof I find in textbooks, where am I going wrong?
Proof:
We try to show that the number of relative primes to $mn$ in $\{1, 2, \ldots , mn-1\}$ is equal to the number of relative primes to $m$ in $\{1,\ldots,m-1\}$ times the number of relative primes to $n$ in $\{1,\ldots,n-1\}$.
We could write $\varphi(mn)$ as the quantity of $a \in \{1,\ldots,mn-1\}:\gcd(a,mn)=1$.
Since $\gcd(a,mn) = 1 \Leftrightarrow \gcd(a,m) = 1 = \gcd(a,n)$ if $\gcd(m,n)=1$.
Since $\gcd(a,m)=1$ defines a number of $a\in \{ 1, \ldots m-1\}$, it defines $\varphi(m)$. The same is valid for $\gcd(a,n)$.
This means there are $\varphi(m)$ cases where $\gcd(a,m)=1$ and $\varphi(n)$ where $\gcd(a,n)=1$. So there are $\varphi(m)\varphi(n)$ cases where $\gcd(a,m) =1 =\gcd(a,n)$. Or there are $\varphi(m)\varphi(n)$ cases where $\gcd(a,mn) =1$.
We conclude $\varphi(mn)=\varphi(m)\varphi(n)$
Remarks
- I've looked at the other proofs on math.stackexchange, but none seem to use the same argument.
- Books mention the Chinese Remainder Theorem and its bijective property, where does this get involved?
Possible answer ?
(i can't answer directly yet because of to low reputation) I think I solved it myself... (although I don't feel 100% sure about it, can anyone help me understand it further?)
In the proof I suggested above there is clear error:
There are $\varphi(m)$ cases where $\gcd(a,m)=1$ and there are $\varphi(n)$ cases where $\gcd(a,n)=1$. So there are $\varphi(m)\varphi(n)$ cases where $\gcd(a,m)=1=\gcd(a,n)$
This doesn't make any sense to have 2 conditions ($\gcd(a,m)=1=\gcd(a,n)$) to have more cases then just one of these conditions.
Correct(?) proof
Let's retake the above untill $\gcd(a,mn) = 1 \Leftrightarrow \gcd(a,m)=1=\gcd(a,n)$. The righthanded side of this equality can be written als a system of congruences. (where $\gcd(m,n)=1$) $$\left\{ \begin{align}a &\equiv r_1 \pmod{m}\\ a &\equiv r_2 \pmod{n}\end{align} \right.$$
With the additional conditions $\gcd(a,m)=1=\gcd(a,n)$. These conditions can be rewritten als $\gcd(a,m)=\gcd(m,r_1)=1$ and $\gcd(a,n)=\gcd(n,r_2)=1$ (according to the Euclidean algorithm, because $r_1$ is the remainder of the division of $a$ with $m$, etc...)
According to the Chinese Remainder Theorem the system above has a solution. There is a certain $a$ which satisfies both congruences. How many choices are there for $r_1$ and $r_2$?
There are $\varphi(m)$ choices for $r_1$ (because $\gcd(m,r_1)=\gcd(r_1,m)=1$). And there are $\varphi(n)$ choices for $r_2$ (same reason). This means there are $\varphi(m)\varphi(n)$ possible couples $(r_1,r_2)$, which provide a solution tot the system, and tot the equality $\gcd(a,m)=1=\gcd(a,n)$. Resulting in the requested theorem.
Remarks
- Is this valid?
- What is the exact use of the CRT in this proof?
Your proof looks fine (see my comment). The CRT kicks in here, many times, in the form of:
$$\text{If we define the rings}\;\;\Bbb Z_n:=\Bbb Z/n\Bbb Z\;,\;n\in\Bbb N\;,\;\;\text{then the CRT tells us that}$$
$$\Bbb Z_n\times\Bbb Z_m\cong \Bbb Z_{(n,m)}\implies\Bbb Z_n^*\times\Bbb Z_m^*\cong \Bbb Z_{(n,m)}^*$$
and since we know that $\;|\Bbb Z_n^*|=\varphi(n)\;$ then we're done.