Counting the number of homorphisms

[seshikanth]

Homework Statement

Hi,
I am trying to solve the following question:
count the number of homomorphism between Z/mZ and Z/nZ?
Can you tell me is my solution correct?

Homework Equations

The Attempt at a Solution

Let f be a homorphism.
f(mZ + a) = nZ + b ; a,b belong to G
Now, o(nZ+b) | n (from lagrangian theorem)
o(f(mZ+a)) = o(nZ+b); and o(f(mZ+a)) | o(mZ+a) which implies o(nZ+b) | m
Number of possiblities for o(nZ+b) = Number of common factors for m and n = Eulers Quotient for gcd(m,n)

Can you tell me if the approach correct? Because when i check the answers of the exercise question it is gcd(m,n) but here i am getting Euler's Qutient for gcd(m.n) = $$\varphi(gcd(m,n))$$

Thanks,

 

[lippyka]

Yes, your approach is correct. The number of homomorphisms between Z/mZ and Z/nZ is equal to the Euler's Quotient for gcd(m,n). This is because the homomorphism must map mZ to some subgroup of nZ, and the order of such a subgroup must divide both m and n. Thus, by the Lagrange's theorem, it must divide the greatest common divisor of m and n, which is gcd(m,n). Therefore, the number of homomorphisms is equal to the number of subgroups of nZ that have order gcd(m,n). This number is given by the Euler's Quotient for gcd(m,n), or \varphi(gcd(m,n)).