3
$\begingroup$

Prove that $(\mathbb{Z}_n , +)$, the integers (mod $n$) under addition, is a group.

To show that this is a group, I know I need to show three things (in our text, we do not need to show that addition is closed-- rather, we show these three items):

a) Associative Law

b) Existence of Identity

c) Existence of Inverse

This is what I have been working with so far:

a) Associative Law: First, assume that $n$ is a composite number and that $a,b \in \mathbb{Z}$ such that $a=nx$ and $b=ny$ for some integers, x and y. Then $a+nx+nx=n(x+y)$.

So, this is where I am stuck for the Associative Law. I'm not sure if I am headed down the correct path to show that $\mathbb{Z}_n$ is associative.

b) Existence of Identity: Generally, when showing the existence of an identity we can use this information for addition : $a + 0 = 0 + a =a$.

I am unsure how to insert the modular portion of the definition into the existence of this identity. I realize that for addition, we generally look at $0$ (rather than $1$ for multiplication).

c) Existence of Inverse: I need to show that for each element $a \in \mathbb{Z}_n$ that $a^{-1}=-a$. Again, I do not know how to insert the modular portion of definition into this aspect of the proof.

My question is how to incorporate this modular information into the proof that this is a group. We have not covered the integers modulo $n$, binary operations, nor groups in my intro to proofs course. I am trying to read my text to figure out how to prove this, but have a difficult time reading and interpreting math speak.

$\endgroup$
  • $\begingroup$ You're forgetting closure as well. $\endgroup$ – Kari Jul 25 '15 at 20:52
  • 1
    $\begingroup$ @Khallil As stated at the start of my post, per my text, we will not be showing closure and just show the other three properties of groups. $\endgroup$ – Mr. Meeseeks Jul 25 '15 at 20:54
  • $\begingroup$ @Khallil Closure isn't really a condition for an operation to be a group operation, because "binary operation" by definition means closed. Usually, closure is something you should check when you want to show something is a subgroup. $\endgroup$ – 6005 Jul 25 '15 at 21:37
8
$\begingroup$

A first important point: the elements of $\Bbb Z_n$ are not integers, but equivalence classes of the modulo $n$ relation. Some texts write these elements as $[0],[1],[2],\dots, [n-1]$ to emphasize they're equivalence classes (and hence sets of integers), where $[k]=\{x \in \Bbb Z: x\equiv k \pmod{n}\}$. In other words, the equivalence class of $k$ under this relation is the set of integers that leave a remainder $k$ when divided by $n$.

So you have $[a]=[b] \iff a\equiv b \pmod{n}\iff n \mid (a-b)$.

On these equivalence classes, you define addition as follows:

$$[a]+[b]=[a+b].$$

A way to become familiar with the operation is to check that it is well-defined, or to check that if $[a]=[c]$ and $[b]=[d]$, then $[a+b]=[c+d]$. (Try to check this, because the proofs of the group axioms are pretty much entirely based on the operation.)

As an example let's look at $\Bbb Z_3=\{[0],[1],[2]\}$.

Here $$[0]=\{\dots,-6,-3,0,3,6,\dots\} \\ [1]=\{\dots,-5,-2,1,4,7,\dots\} \\ [2]=\{\dots,-4,-1,2,5,8,\dots\}$$

We can write out the multiplication table (dropping the brackets for legibility):

\begin{array}{c|ccc} + & 0 & 1 & 2 \\ \hline 0 & 0 & 1 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 2 & 0 & 1 \end{array}

The table tells you that $[0]$ is the identity, and $[1]$ and $[2]$ are inverses. Note that $[1]+[2]=[1+2]=[3]=[0]$, where $[3]=[0]$ because here $n=3$.

Now, let's look at your proof.

a) Associative Law: First, assume that n is a composite number and that $a,b\in \Bbb Z$ such that $a=nx$ and $b=ny$ for some integers, $x$ and $y$. Then $a+nx+nx=n(x+y)$.

Is there a reason why you're assuming $n$ is composite? $\Bbb Z_n$ is a group also when $n$ is prime.

In your proof, by assuming that $a$ and $b$ are multiples of $n$ you're actually assuming they are elements of the equivalence class $[0]$, because $[nx]=x[n]=x[0]=[x0]=[0]$.

What you're required to show for the associative law, is that for three elements $[a],[b],[c]$ of $\Bbb Z_n$ (not integers, but equivalence classes) you have $[a]+([b]+[c])=([a]+[b])+[c]$.

The proof should follow from the way the operation of $+$ is defined for these equivalence classes and from associativity of addition of integers.

b) Existence of Identity: Generally, when showing the existence of an identity we can use this information for addition : a+0=0+a=a. I am unsure how to insert the modular portion of the definition into the existence of this identity. I realize that for addition, we generally look at 0 (rather than 1 for multiplication).

You want to show that $[0]=\{x \in \Bbb Z : x \equiv 0 \pmod{n}\}$, the equivalence class of all multiples of $n$, is the identity of $\Bbb Z_n$, or that for any $[a]\in \Bbb Z_n$ you have

$$[a]+[0]=[0]+[a]=[a]$$

This also follows from the definition of the operation: $[a]+[b]=[a+b]$.

c) Existence of Inverse: I need to show that for each element $a\in \Bbb Z_n$ that $a^{−1}=−a$. Again, I do not know how to insert the modular portion of definition into this aspect of the proof.

Since the operation here is addition, not multiplication, the inverses should be the negatives: try to show that the inverse of $[a]$ is $[-a]$ and that $[-a]$ is an element of $\Bbb Z_n$.

(I can give more details if you need them.)

$\endgroup$
  • $\begingroup$ Wouldn't the inverse of $\left[ a \right]$ be $\left[ n-a \right]$ as well? $\endgroup$ – Kari Jul 25 '15 at 22:33
  • 1
    $\begingroup$ @Khallil Yes. In fact, $[n-a]=[-a]$ in $\Bbb Z_n$. (Inverses are unique.) $\endgroup$ – coldnumber Jul 25 '15 at 22:33
  • $\begingroup$ I am presently trying to figure out the associative portion. Effectively, it seems as though I need to show for $ [a], [b], [c] \in \mathbb{Z}_n$ that $ ([a] + [b]) + [c] = [a] + ([b] + [c])$, for these equivalence classes in $\mathbb{Z}_n$. I still unsure of how to incorporate the modulo $n$ information, but this is where I was thinking of starting: $[a]+[b] \equiv (x+y)($mod$ \ n)$ and $[b]+[c] \equiv (y+z)($mod$ \ n)$ for some integers x,y, and z. Then, maybe try some fancy rearranging at this point? $\endgroup$ – Mr. Meeseeks Jul 25 '15 at 23:01
  • $\begingroup$ @mia.avery indeed, that is what you need to show. I think here you don't need to use the divisibility information, only the definition of the operation and the associativity of addition of integers. Note that your $x$ and $y$ are known here: $[a]+[b]=[a+b]$, so $[a]+([b]+[c])=[a]+[b+c]=[a+(b+c)]=[(a+b)+c]=\cdots$. Can you get to $([a]+[b])+[c]$ from there? $\endgroup$ – coldnumber Jul 25 '15 at 23:13
  • $\begingroup$ I guess maybe I'm making this too hard?? Do I really just need to state something like: $[a]+[b]+[c]=[a+b+c]$, so $[a]+([b]+[c])=[a+b+c]=([a]+[b])+[c]$, then site some theorem for the addition of sets? ...maybe? $\endgroup$ – Mr. Meeseeks Jul 25 '15 at 23:20

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.