# Counting Homomorphisms

• Dec 8th 2010, 10:44 PM
matt.qmar
Counting Homomorphisms
Hello,

I am trying to find the number of group homomorphisms from $Z_n$ to $Z_k$.

We know that it is gcd(n,k), but we I am trying to show we can count them the sum of $\phi(d)$ running over all common divisors "d" of k and n, for Euler's phi-function. It follows from number theory that this sum is the gcd. Note we use lower-case phi.

I am this far:
We know $\Phi(x) = mx\ mod\ k$ for some $m \in Z_k$
and we know by homomorphism properties that $|m|$ divides k and $|m|$ divdes n. We use upper-case Phi for a homomorphism.

let $|m| = d$. Then d is a common divisor of k and n.

I can show obviously that $\Phi$ is a homomorphism by properties of modular addition and multiplication.

I am just trying to find a way to count the number of each homomorphisms for each common divisor d? I know it MUST be $\phi(d)$, why is that?

Thanks!
• Dec 8th 2010, 10:59 PM
Drexel28
Quote:

Originally Posted by matt.qmar
Hello,

I am trying to find the number of group homomorphisms from $Z_n$ to $Z_k$.

We know that it is gcd(n,k), but we I am trying to show we can count them the sum of $\phi(d)$ running over all common divisors "d" of k and n, for Euler's phi-function. It follows from number theory that this sum is the gcd. Note we use lower-case phi.

I am this far:
We know $\Phi(x) = mx\ mod\ k$ for some $m \in Z_k$
and we know by homomorphism properties that $|m|$ divides k and $|m|$ divdes n. We use upper-case Phi for a homomorphism.

let $|m| = d$. Then d is a common divisor of k and n.

I can show obviously that $\Phi$ is a homomorphism by properties of modular addition and multiplication.

I am just trying to find a way to count the number of each homomorphisms for each common divisor d? I know it MUST be $\phi(d)$, why is that?

Thanks!

Think about what the generators are for these groups.