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]

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 .

 

[blamocur]

Have you tried using Euler's product formula ?

 

[Steven G]

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.

 

[khansaheb]

Can we see your work? That way we can printout point out what is missing.

My mind reading skills are coming handy!!!!

 

[blamocur]

Have you tried using Euler's product formula ?

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

[math]\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)[/math]
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]