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?