# Thread: Counting Homomorphisms

1. ## Counting Homomorphisms

Hello,

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

We know that it is gcd(n,k), but we I am trying to show we can count them the sum of $\displaystyle \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 $\displaystyle \Phi(x) = mx\ mod\ k$ for some $\displaystyle m \in Z_k$
and we know by homomorphism properties that $\displaystyle |m|$ divides k and $\displaystyle |m|$ divdes n. We use upper-case Phi for a homomorphism.

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

I can show obviously that $\displaystyle \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 $\displaystyle \phi(d)$, why is that?

Thanks!

2. Originally Posted by matt.qmar
Hello,

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

We know that it is gcd(n,k), but we I am trying to show we can count them the sum of $\displaystyle \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 $\displaystyle \Phi(x) = mx\ mod\ k$ for some $\displaystyle m \in Z_k$
and we know by homomorphism properties that $\displaystyle |m|$ divides k and $\displaystyle |m|$ divdes n. We use upper-case Phi for a homomorphism.

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

I can show obviously that $\displaystyle \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 $\displaystyle \phi(d)$, why is that?

Thanks!
Think about what the generators are for these groups.