Lesson 30 Solutions

Exercise 1) Define a homomorphism from $\mathbb{Z}_8$ to $\mathbb{Z}_4$ , different from that defined in the lesson.

Solution: What we need to do here is define our own function, i.e., create our own function, and then check to see whether or not it’s a homomorphism. Let’s define the function $f:\mathbb{Z}_8\rightarrow \mathbb{Z}_4$ as follows: $f(a)=a \mod 4$ , where the “ $a \mod 4$ ” on the right hand side means to take the number $a\in \mathbb{Z}_8$ and calculate its value modulo 4. In this case, this means that

$f(0)=0, f(1)=1, f(2)=2, f(3)=3, f(4)=0, f(5)=1, f(6)=2, f(7)=3$

and this is depicted in figure 1.

figure 1

I claim that this is indeed a homomorphism, and to check this claim we simply need to calculate $f(a\cdot b)$ for every possible choice of $a,b\in \mathbb{Z}_8$ and see that, for the same choice, this expression equals $f(a)\cdot f(b)$ . However, there are a lot of different possible choices, and yet again I find myself to be lazy. Therefore, I’ll try to prove this more abstractly, and in a way that will end up being useful for when we need to prove similar statements when the number of possible pairs is infinite (for then performing all necessary calculations is fundamentally impossible!). First, though, I encourage the reader to simply stare at figure 1 and try a couple of examples. I.e., add 3 and 7 on the left and see where you land (i.e., at 2), then take the arrow over to the right (i.e., to 2). Then, start at 3 on the left and head along the arrow (to 3), and go back to 7 and head along its arrow (also to 3), and then add these two elements on the right (i.e., 3+3) and note that we cycle back to 2. Thus, in this case, $f(3\cdot 7)=f(3)\cdot f(7)$ . Try a few other cases on your own, and then continue on to learn the abstract proof.

Let’s simply consider what $f(a\cdot b)$ is for an arbitrary choice of $a,b\in \mathbb{Z}_8$ . In other words, we don’t know what these elements are—we’re leaving them completely abstract—and we’re going to see what we can say about them simply through our knowledge that they are in $\mathbb{Z}_8$ . Well, by definition of the group product (which is modular arithmetic here) on $\mathbb{Z}_8$ , we know that $a\cdot b=a+b \mod 8$ . Thus, if $a+b$ is less than 8 we leave it alone, and if it is bigger than 8 we simply cycle back through until it is smaller than 8 (for example, 6+7=13=8+5, so that we have “6+7 mod 8 = 5”).

Now, when we send this product over to $\mathbb{Z}_4$ , we’re simply taking the “mod 4” of the expression $a+b\mod 8$ . I.e., we’re calculating $(a+b \mod 8)\mod 4$ , where we’re first mapping $a+b$ to its remainder when divided by 8 (so that $0\leq (a+b\mod 8)\leq 7$ ), and then we’re taking the “mod 4” of this number so that if it is already less than 4 we leave it alone and if it’s greater than or equal to 4 we cycle back through. Let me be clear: we’re doing the “mod 8” bit because that’s the group product in $\mathbb{Z}_8$ , and then we’re doing the “mod 4” bit because that is how the function $f$ tells us to send our element over to $\mathbb{Z}_4$ .

However, taking the “mod 8” bit of $a+b$ and then taking the “mod 4” bit of whatever is left is precisely the same as taking the “mod 4” of $a+b$ initially. I.e., “modding out” by 8 and then by 4 is the same as just “modding out” by 4. A few examples should make this clear (in what follows we consider arbitrary integers, and not just those that can be obtained by adding elements of $\mathbb{Z}_8$ ). Namely, 41 equals $(5\times 8) +1$ and so we have $41\mod 8=1$ . Now, “modding 1 out” by 4 simply gives 1 right back. Thus, $(41 \mod 8)\mod 4=1$ . Similarly, it’s clear that $41 \mod 4=1$ , so we have $(41\mod 8)\mod 4=41\mod 4$ . Here’s another example. 54 equals $(6\times 8)+6$ , so $54\mod 8=6$ . Now, modding this out by 4, we see that $(54\mod 8)\mod 4=6\mod 4=2$ . Also, $54=(13\times 4)+2$ , so that $54\mod 4=2$ , and thus again we have $(54\mod 8)\mod 4=54\mod 4$ .

Let’s now put this all more abstractly (and in doing so things might seem to get a bit scary, but we must simply remember to stay calm and recall that notation is never scary!). Namely, the reason why modding out by 8 and then by 4 is the same as just modding out by 4 in one step is as follows. Suppose we take some arbitrary integer, let’s call it $a$ , and suppose we mod it out by 8. What we’re doing in this case is decomposing the integer $a$ in the following way: $a=(m\times 8) + l$ , where $m$ is some integer and $l$ is some integer greater than or equal to zero and less than 8, i.e. $0\leq l<8$ . In the “mod out by 8” step, we say that $a \mod 8=l$ . Then, when we mod out by $4$ , we’re decomposing $l$ as $l=p\times 4+q$ where now $0\leq q <4$ and, since we know that $0\leq l <8$ , we know that $p$ is either 0 or 1 (i.e., if $l$ is already less than 4, then we know that $p=0$ ). Thus, by doing the two step process of modding out by 8 and then by 4, we’re decomposing our original integer $a$ as $a=(m\times 8) + (p\times 4)+q$ where $0\leq q<4$ (all I’ve done is put in our new expression for $l$ ) and our final result for modding $a$ out by 8 and then again by 4 is the number $q$ . However, since 8 is 2 times 4, we have that $m\times 8=2m\times 4$ , and so we finally get $a=[(2m+p)\times 4]+q$ . Thus, when we mod out by 4 straight away, we also get $q$ ! This is because if we stare at the last expression, we see that we’ve just decomposed $a$ as “something times 4” plus “something that is greater than or equal to zero and less than 4”, which is what we need to do to mod out by 4. Thus, we’ve shown in complete generality that modding out by 8 and then by 4 is the same as modding out by 4 in one step. The same thing can always be said about “two-step modding out processes” when the second thing we mod out by is a factor of the first (just as 4 is a factor of 8), which is hopefully clear enough from this paragraph.

Now, to get back to our original problem, we have just shown that $f(a\cdot b)=(a+b\mod 8)\mod 4=(a+b) \mod 4$ . Let me emphasize this by giving it it’s own line:

$f(a\cdot b)=(a+b) \mod 4$ .

That’s the best that we can do right now, since we don’t know anything about $a$ or $b$ . So, let’s see what we can say about $f(a)\cdot f(b)$ . Well, with all that we’ve done so far, this will be a bit easier. Namely, we know that $f(a)\cdot f(b)=f(a)+f(b)\mod 4$ since this is the definition of the group product in $\mathbb{Z}_4$ . We then know that the function $f$ tells us to take our element in $\mathbb{Z}_8$ and mod it out by 4, so that $f(a)=a\mod 4$ and $f(b)=b\mod 4$ . Thus we have

$f(a)\cdot f(b)=(a\mod 4)+(b\mod 4)\mod 4$ .

But again, if we mod two integers out by 4, add them together, and then mod out by 4 again, we always get the same result as we would by simply adding them together (without first modding out by 4) and then modding out by 4 just once at the end. To see this, we note that in modding $a$ and $b$ both out by 4, we’re decomposing them as follows: $a=k\times 4+l$ and $b=m\times 4+n$ , where as usual $l$ and $n$ are both greater than or equal to 0 and less than 4 (i.e. $0\leq l,n<4$ ). Then $a\mod 4=l$ and $b\mod 4=n$ , so that

$f(a)\cdot f(b)=l+n\mod 4$ .

But again, by plugging in the above decompositions of $a$ and $b$ , we have $a+b=(k\times 4+l)+(m\times 4 +n)=(k+m)\times 4+(l+n)$ . Thus,

$(a+b)\mod 4=(l+n)\mod 4$ ,

where we leave the “mod 4” in on the right hand side of this equation because it might be the case that $l+n$ is still greater than 4 (e.g. if they’re both 3, or something), in which case we still need to mod out by 4 again. However, the left hand side of the most recently centered equation is precisely what we showed $f(a\cdot b)$ equaled, and the right hand side is still what $f(a)\cdot f(b)$ equals. This therefore means that

$f(a\cdot b)=f(a)\cdot f(b)$ !

Since $a$ and $b$ were left completely arbitrary in this discussion, it must be the case that the above equation is true for all choices of $a,b\in \mathbb{Z}_8$ , and this is exactly what we needed to show to prove that the function $f$ that we defined is indeed a homomorphism.

Phew! That was intense, but we’re done! If the “homomorphism-ness” of this $f$ was clear from the get-go, then great. If it wasn’t, then hopefully this discussion helped. Either way, it’s important to a) know how to prove things abstractly and b) get used to doing so, since our arguments will continue to get more and more abstract (and cool!). That said, rest assured, the solution to the next problem is much easier than this one.

Exercise 2) Define a homomorphism from $\mathbb{Z}$ to $\mathbb{Z}$ (i.e., to itself).

Solution: Alright, compared to the above problem, this one is a breeze. There are many homomorphisms $f:\mathbb{Z}\rightarrow \mathbb{Z}$ that we could define, but I’ll just do one explicitly and then give a nod to how some other ones might go. There are two important points here. One is that we need to create, define, construct our own function. Math is not a natural resource that springs up from the Earth, it needs to be created. The second point is that in order to prove that the function $f:\mathbb{Z}\rightarrow \mathbb{Z}$ that we define is indeed a homomorphism, we need to proceed abstractly. This is because we can’t concretely calculate every possible $f(a\cdot b)$ and $f(a)\cdot f(b)$ because there are infinitely many choices of $a,b\in \mathbb{Z}$ , seeing as $\mathbb{Z}$ is itself infinite. Regardless, let’s proceed.

Let me define the following function. Let $f:\mathbb{Z}\rightarrow \mathbb{Z}$ be the function defined by $f(a)=2\times a$ , i.e., it sends each integer to “2 times itself”. We note immediately that this function is not surjective, since for example the integer 1 is never hit by our function, since 1 is not two times anything. In fact, and hopefully obviously, no odd numbers are hit by this function. But that’s fine, the quality of being a homomorphism is completely independent of surjectivity or injectivity.

Now we need to check that this function actually is a homomorphism. But to see this is simple, once we recall that the group product on $\mathbb{Z}$ is simply addition (and since this is a map from $\mathbb{Z}$ to itself, we have the same group product in both the domain and the codomain of the function). Let’s first consider $f(a\cdot b)$ for some arbitrary $a,b\in \mathbb{Z}$ . We have $a\cdot b=a+b$ , so that

$f(a\cdot b)=f(a+b)$

and by the definition of $f$ we have $f(a+b)=2\times (a+b)$ . Similarly, we have that $f(a)=2\times a$ and $f(b)=2\times b$ , so that

$f(a)\cdot f(b)=f(a)+f(b)=(2\times a) + (2\times b)=2\times (a+b)$ .

This is precisely what we found for $f(a\cdot b)$ , so we’ve just shown that

$f(a\cdot b)=f(a)\cdot f(b)$ ,

and again since $a,b\in \mathbb{Z}$ were left completely arbitrary this whole time, it is clear that the above statement is true for all possible $a,b\in \mathbb{Z}$ . To summarize, we have the following quick proof:

$f(a\cdot b)=f(a+b)=2(a+b)=2a+2b=f(a)+f(b)=f(a)\cdot f(b)$ .

This completes the problem. I should mention though that we can get many more homomorphisms using the same construction as follows. We simply fix some integer and call it $M$ (in the above discussion, $M=2$ ). We then define the function $f_M:\mathbb{Z}\rightarrow \mathbb{Z}$ by $f_M(a)=M\times a$ (so that the $f$ defined above would be the same as $f_2$ in this definition, where the subscript is just there to remind us what our multiplication factor defining the function is). Proving this is a homomorphism is completely simple, and in fact to do so I’m simply going to copy/past the above proof, add in subscripts (just for notational consistency) and only change the three 2’s to three M’s:

$f_M(a\cdot b)=f_M(a+b)=M(a+b)=Ma+Mb=f_M(a)+f_M(b)=f_M(a)\cdot f_M(b)$ .

And Wa-La! Since there are infinitely many integers, and therefore infinitely many different choices of $M$ , each different choice giving rise to a different homomorphism $\mathbb{Z}\rightarrow \mathbb{Z}$ , we’ve effectively just defined infinitely many different homomorphisms! Cool!