# Euler's totient function: how to prove |Um*n| = |Um| cross |Un| implies gcd(m,n) =1 where |Um*n| means all numbers <m*n relatively prime to it

#### elioruzan

##### New member
Hi everyone,
how can I prove that |Um*n| = |Um| cross |Un| implies gcd(m,n) =1 ?
where |Um*n| denotes all the numbers less than m*n that are relatively prime to it.
my lecturer proved us the other implication , which is gcd(m,n)=1 implies |Um*n| = |Um| cross |Un| using the chinese remainder theorem but said there is an equivalence between the two.
I tried to prove it the other direction myself , but it seems I have something missing.
Thank you for helping me .

I tried to prove it the other direction myself , but it seems I have something missing.
Can we see your work? That way we can printout what is missing.

Can we see your work? That way we can printout point out what is missing.
My mind reading skills are coming handy!!!!

One week later: if [imath]\phi (mn) = \phi(m)\phi(n)[/imath] then

$\Pi_{p|mn} \left(1-\frac{1}{p} \right) = \Pi_{p|m} \left(1-\frac{1}{p} \right)\Pi_{q|n} \left(1-\frac{1}{q} \right)$
But every multiplicand in the left hand side is also present in at least one term in the right hand side, i.e. [imath]\phi (mn) \leq \phi(m)\phi(n)[/imath]

Now, to prove by contradiction let's assume that [imath]\gcd(m,n) > 1[/imath]. Then some [imath]p[/imath] from the left hand side will appear in both products of the left hand side, i.e. as [imath]p[/imath] and [imath]q[/imath]. But since that [imath]p[/imath] can appear only once in the left hand side we get [imath]\phi (mn) < \phi(m)\phi(n)\; \blacksquare[/imath]