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
Joined
Feb 14, 2023
Messages
11
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 .
 
One week later: if ϕ(mn)=ϕ(m)ϕ(n)\phi (mn) = \phi(m)\phi(n) then

Πpmn(11p)=Πpm(11p)Πqn(11q)\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. ϕ(mn)ϕ(m)ϕ(n)\phi (mn) \leq \phi(m)\phi(n)

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