Hello,

I am trying to find the number of group homomorphisms from

to

.

We know that it is gcd(n,k), but we I am trying to show we can count them the sum of

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

for some

and we know by homomorphism properties that

divides k and

divdes n. We use upper-case Phi for a homomorphism.

let

. Then d is a common divisor of k and n.

I can show obviously that

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

, why is that?

Thanks!