# Why does the surjectivity of the remainder function $\rho:\Bbb{Z}\rightarrow\Bbb{Z}_n$ imply identities in $\Bbb{Z}$ are valid in $\Bbb{Z}n$?

I am reading Mac Lane and Saunders Algebra 3rd Edition Chapter 1 Section 8. After defining the remainder function $$\rho:\mathbb{Z}\rightarrow\mathbb{Z}n$$ they define modular addition $$\oplus:\mathbb{Z}n\rightarrow\mathbb{Z}n$$ and note the following identity (29):

$$\rho(k+m)=(\rho k)\oplus(\rho m)$$.

After proving the commutative law for $$\oplus$$ explicitly, they write:

Put differently: $$\rho:\mathbb{Z}\rightarrow\mathbb{Z}n$$ is a surjection; by (29) it carries $$+$$ to $$\oplus$$, hence it carries the commutative law for $$+$$ to the commutative law for $$\oplus$$."

I don't understand this. Why does $$\rho$$ being a surjection and (29) help us infer the commutativity of $$\oplus$$ from the commutativity of $$+$$?.

Then later they define modular multiplication but instead of explicitly proving that modular multiplication is commutative, associative, distributes over $$\oplus$$, and has 1 as unit, they just write:

Since $$\rho$$ is a surjection, identities such as the distributive law valid in $$\mathbb{Z}$$ are valid in $$\mathbb{Z}_n$$, Q.E.D.

How this is a valid proof that modular multiplication is commutative, associative, distributes over $$\oplus$$, and has 1 as unit?

Then they say:

These arguments show that identities valid for addition and multiplication in $$\mathbb{Z}$$ imply corresponding identities for the new addition and multiplication in $$\mathbb{Z}_n$$. They do not show that other properties valid in $$\mathbb{Z}$$ carry over to $$\mathbb{Z}_n$$.

Note that this is well before morphisms are introduced in the text. I have no doubt that making use of knowledge of morphisms would make all this clear. But I don't see how surjectivity itself allows us to make such arguments. I feel like I'm missing something obvious. To be clear, I don't have any trouble proving all of this stuff explicitly. I just don't understand why the surjectivity of $$\rho$$ helps prove these things directly.

• See e.g. here for the standard argument. Commented Oct 24, 2020 at 9:46

We can figure this out by making it more abstract.

We have a binary operation $$\square:A\rightarrow A$$, a function $$f:A\rightarrow B$$, and binary operation $$\bigtriangleup:B\rightarrow B$$. We also know (we can prove) that

$$f(a_1)\bigtriangleup f(a_2) = f(a_1\square a_2).$$

If $$f$$ is surjective then each element of $$B$$ can be denoted as $$f(a)$$ for some $$a:A$$. This implies that we can rewrite $$b_1\bigtriangleup b_2$$ as $$f(a_1)\bigtriangleup f(a_2)$$ where $$f(a_1)=b_1$$ and $$f(a_2)=b_2$$. In other words, $$f$$ being surjective means that the above equation describes any application of $$\bigtriangleup$$ to any two inputs in its domain.

The relation between $$\bigtriangleup$$ and $$\square$$ above is saying "identities valid for $$\square$$ imply corresponding identities for $$\bigtriangleup$$ whenever the inputs of $$\bigtriangleup$$ are both outputs of $$f$$." Commutativity, associativity, etc. are examples of such identities.

The surjectivity of $$f$$ and the above identity together then mean "identities valid for $$\square$$ imply corresponding identities for $$\bigtriangleup$$," similar to what the authors of the textbook wrote in the text I quoted.

• You've got it ^_^. This was unfortunately timed, as I just added an answer with similar information. It's great that you figured it out by yourself, though! Commented Oct 24, 2020 at 4:53

Welcome to MSE!

There is some fun model theory happening here, but I'll refrain from mentioning it because you aren't familiar with morhpisms yet. If you're interested, I go into some detail in my answer here.

The idea is that "identities" are preserved under morphisms. Let's work with commutativity first:

Let $$x,y \in \mathbb{Z}/n$$. Then, by surjectivity, $$x = \rho(\tilde{x})$$ and $$y = \rho(\tilde{y})$$. But we know that, in $$\mathbb{Z}$$,

$$\tilde{x} + \tilde{y} = \tilde{y} + \tilde{x}$$

So when we hit everything in sight by $$\rho$$, we see

$$x \oplus y = \rho(\tilde{x}) \oplus \rho(\tilde{y}) = \rho(\tilde{x} + \tilde{y}) = \rho(\tilde{y} + \tilde{x}) = \rho(\tilde{y}) \oplus \rho(\tilde{x}) = y \oplus x$$

So $$\oplus$$ is commutative too.

In general, this strategy will always work for equations. If $$p = q$$ is some equation in $$\mathbb{Z}$$, then $$p = q$$ will also be true in $$\rho[\mathbb{Z}]$$, which, by surjectivity, is all of $$\mathbb{Z}/n$$.

Let's see this again with distributivity. Say we know that $$\rho(x \times y) = \rho(x) \otimes \rho(y)$$, which is not difficult to show. Then

\begin{align} x \otimes (y \oplus z) &= \rho(\tilde{x}) \otimes (\rho(\tilde{y}) \oplus \rho(\tilde{z}))\\ &= \rho(\tilde{x} \times (\tilde{y} + \tilde{z}))\\ &= \rho(\tilde{x} \times \tilde{y} + \tilde{x} \times \tilde{z})\\ &= \rho(\tilde{x}) \otimes \rho(\tilde{y}) \oplus \rho(\tilde{x}) \otimes \rho(\tilde{z})\\ &= x \otimes y \oplus x \otimes z \end{align}

Notice this is the same strategy as before. The idea is to:

1. Write the left hand side of your desired equation.
2. Write each element on the left hand side as $$\rho$$ of something.
3. Use the fact that $$\rho$$ preserves all the operations to move the stuff inside of $$\rho$$
4. Use the fact that the equation holds in $$\mathbb{Z}$$ to make the substitution and get the desired right hand side inside of $$\rho$$
5. Re-apply $$\rho$$ to get back to the original operations
6. Conclude the equation also holds in $$\mathbb{Z}/n$$.

Here surjectivity is crucial, because it lets us move the equation inside of $$\rho$$ for any elements we want. Without surjectivity, we would only be able to show that our desired equations hold for elements in the image of $$\rho$$. At least, with this proof technique. As I said before, there is some model theory happening here, and this proof technique works in much more general settings with arbitrary algebras and homomorphisms.

I hope this helps ^_^