I know that there are $gcd(a,b)$ unique group homomorphisms between $\mathbb{Z}/a\mathbb{Z}$ and $\mathbb{Z}/b\mathbb{Z}$ for $a,b \in \mathbb{N}, a,b \geq 2$. I just want to prove it in a simple way.

A group homomorphism $\phi$ of the desired kind is uniquely defined by the choice of $\phi(\bar{1})$.

Let $X$ be the number of possible group homomorphisms. I want to show that $X$ divides $a$ and $b$, and is therefore exactly $gcd(a,b)$.

Assumption: $\phi(\bar{1}) \neq \bar{0}$ (the trivial case).

For a group homomorphism $\phi(a) + \phi(b) = \phi(a + b)$ has to apply. Therefore $b = |\phi(\bar{1})| \cdot k$ for some $k \in \mathbb{N} \Rightarrow |\phi(\bar{1})|$ divides $b$. This is required in order to express the neutral element as a sum of two other elements (and achieve the "wrap").

I just discarded my approach why $|\phi(\bar{1})|$ needs to divide $a$ as well as it was nonsense. It seems logical to me that this needs to apply, but I don't have an idea how to show it.

Can you help me to finish this? Is the first part correct? How would I describe it in a more formal way?

  • $\begingroup$ Careful. $1$ divides $6$ and $9$ but certainly isn't $\gcd(6,9)$. $\endgroup$ – user98602 Nov 6 '14 at 22:17
  • $\begingroup$ What do you mean by $|\phi(\bar{1})|$? $\endgroup$ – user44400 Nov 6 '14 at 22:19
  • $\begingroup$ @user44400 the order of $\phi(\bar{1})$, so the smallest integer x with $\left(\phi(\bar{1})\right)^x = e$ $\endgroup$ – muffel Nov 6 '14 at 22:22

You made a good start. What you have is that $a\phi(1) =\phi(a) = \phi(0)= 0$.

Now note that this means that $a$ is a multiple of the order of $\phi(1)$, that is the order is a divisor of $a$.

But, the order of each element in $\mathbb{Z}/b \mathbb{Z}$ is a divisor of $b$.

So, you get that the order of $\phi(1)$ divides $a$ and $b$, and you get the result soon.

| cite | improve this answer | |
  • $\begingroup$ thank you for your answer! Just one question: can you please explain why the order of each element in $\mathbb{Z}/b\mathbb{Z}$ is a divisor of $b$? $\endgroup$ – muffel Nov 6 '14 at 23:05
  • $\begingroup$ You are welcome. For your question. It is just like with the $a$. Given some element $c$ you certainly have $bc=0$ in $Z/bZ$. So $b$ is a multiple of the order of $c$, that is the order is a divsor of $b$. $\endgroup$ – quid Nov 6 '14 at 23:10
  • $\begingroup$ Thanks! But if I take $\mathbb{Z}/4\mathbb{Z} = \{0,1,2,3\}$, the order of $2$ is $3$ which is not a divider of 4. Am I missing something? $\endgroup$ – muffel Nov 6 '14 at 23:37
  • $\begingroup$ But 2 times 2 is 4 which is 0 so the order of 2 is 2. I am not sure which reasoning leads you to the order of 2 being 3. One thing you should be careful about: we are in a group here that is written additively (not multipilcatively as is common for groups too) so g has order d means dg = 0. $\endgroup$ – quid Nov 7 '14 at 10:59
  • 1
    $\begingroup$ my fault, sorry, now I got it. Thank you very much! $\endgroup$ – muffel Nov 7 '14 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.