Results 1 to 2 of 2

Math Help - Counting Homomorphisms

  1. #1
    Member
    Joined
    Oct 2009
    Posts
    128

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by matt.qmar View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: July 13th 2011, 11:40 AM
  2. Homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 6th 2011, 11:39 AM
  3. Homomorphisms to and onto
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 23rd 2009, 09:21 AM
  4. Homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: May 20th 2008, 01:26 AM
  5. Homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: April 23rd 2007, 11:53 AM

Search Tags


/mathhelpforum @mathhelpforum