Modulo question

**sjenkins** · June 17th 2008, 07:05 PM

I am working with the least helpful textbook in the world and am confused with the concept of modulo. Can someone please explain exactly what it is? I have never heard this word before this particular class. How can I find inverse of modulo? Such as...

Show that 937 is an inverse of 13 modulo 2436

and

Find an inverse of 2 modulo 17

Please, I can't go on in this course until I get a firm grasp of modulo!

**ThePerfectHacker** · June 17th 2008, 07:07 PM

Originally Posted by sjenkins

Show that 937 is an inverse of 13 modulo 2436

Show that $(937)(13) - 1$ is divisible by $2436$ .

Find an inverse of 2 modulo 17

Find an integer $x$ so that $2x - 1$ is divisible by $17$ .

**Moo** · June 18th 2008, 11:24 AM

Hi =)

Originally Posted by sjenkins

I am working with the least helpful textbook in the world and am confused with the concept of modulo. Can someone please explain exactly what it is? I have never heard this word before this particular class. How can I find inverse of modulo? Such as...

Show that 937 is an inverse of 13 modulo 2436

and

Find an inverse of 2 modulo 17

Please, I can't go on in this course until I get a firm grasp of modulo!

Continuing TPH's explanation, the inverse x of 13 modulo 2436 is such that :

$13x \equiv 1 (2436)$ , that's equivalent to what TPH said.

If you weren't given 937, first check that 13 is coprime with 2436.
Then, use the Euclidian algorithm. You'll get 1 at a moment because it's the gcd.

Let 2436=a and 13=b. We'll find u (and v) such that av+bu=1 <=> bu=1+a(-v) <=> 13u=1 mod a
that is to say u is the inverse of 13

$2436=\textbf{13}*187+\textbf{5} \quad \implies \quad 5=a-187b$

$13=2*\textbf{5}+\textbf{3} \quad \implies \quad 3=13-5*2=b-2(a-187b)=-2a+375b$

$5=\textbf{3}+\textbf{2} \quad \implies \quad 2=5-3=(a-187b)-(-2a+375b)=3a-562b$

$3=2+1 \quad \implies \quad 1=3-2=(-2a+375b)-(3a-562b)=-5a+937b$

$1=-5*2436+937*13 \quad \implies \quad 937*13=1+5*2436=1 \mod 2436$

Yay !

[tex]

**leinad** · July 22nd 2009, 10:20 AM

Hello math helpers, I hope that I do not get accused of hijacking this thread but I think my question is relevant.

I am just starting to learn some elementary group theory and I am puzzled as to how one goes about proving that addition modulo n is associative. Strangely I have found a proof that shows the addition of congruence classes modulo n is associative and I understand that but I cannot seem to apply it to addition modulo n for integers.

Any help would be most appreciated.

**Gamma** · July 22nd 2009, 05:13 PM

There is not much to show honestly, it is just because regular addition is associative.
$(a+b)+c=a+b+c=a+(b+c) \Rightarrow (a+b)+c =a+(b+c)$ (mod n)

It basically just comes down to the fact that reduction of integers modulo n is well-defined, that is if $a=b$ then $a$ (mod n) $= b$ (mod n)

**leinad** · July 22nd 2009, 11:27 PM

Gamma thank-you very much for taking the time to answer my question. As ever the proof comes down to something I have not yet covered.

**Gamma** · July 23rd 2009, 10:50 AM

I was thinking a little more about this question you have asked, and I was thinking it is probably more useful for you to prove essentially that this modulo reduction operation is a homomorphism under addition.

You probably have not gotten to this yet in your book, but the concept of a homomorphism will be important, so you might as well start to think about it now.

Consider the function $\phi:\mathbb{Z} \Rightarrow \mathbb{Z}_n,\phi(x)=x$ (mod n).

Now what you need to show is that it doesn't make a difference if you add two integers before you apply $\phi$ or after you apply $\phi$ to them separately. In symbols I mean:

$\phi(x)+\phi(y)=\phi(x+y)$
Simply apply the division algorithm to x and y to see that

$\phi(x)+\phi(y)=\phi(r+nk)+\phi(s+nl)=r+s$ (mod n)
$\phi(x+y)=\phi\left((r+nk)+(s+nl)\right)=\phi\left ((r+s) + n(k+l)\right)=r+s$ (mod n)

So now if you think about your question, associativity of addition under modular addition follows from the fact that addition is associative in $\mathbb{Z}$ and since this reduction mod n preserves addition, the associativity is inherited from $\mathbb{Z}$

**leinad** · July 24th 2009, 04:43 AM

Originally Posted by Gamma

I was thinking a little more about this question you have asked, and I was thinking it is probably more useful for you to prove essentially that this modulo reduction operation is a homomorphism under addition.

You probably have not gotten to this yet in your book, but the concept of a homomorphism will be important, so you might as well start to think about it now.

Consider the function $\phi:\mathbb{Z} \Rightarrow \mathbb{Z}_n,\phi(x)=x$ (mod n).

Now what you need to show is that it doesn't make a difference if you add two integers before you apply $\phi$ or after you apply $\phi$ to them separately. In symbols I mean:

$\phi(x)+\phi(y)=\phi(x+y)$
Simply apply the division algorithm to x and y to see that

$\phi(x)+\phi(y)=\phi(r+nk)+\phi(s+nl)=r+s$ (mod n)
$\phi(x+y)=\phi\left((r+nk)+(s+nl)\right)=\phi\left ((r+s) + n(k+l)\right)=r+s$ (mod n)

So now if you think about your question, associativity of addition under modular addition follows from the fact that addition is associative in $\mathbb{Z}$ and since this reduction mod n preserves addition, the associativity is inherited from $\mathbb{Z}$

Hi Gamma

Many thanks for your continued interest, I very much appreciate it.

I understand your proof that $x$ (mod n) $+ y$ (mod n) $= (x + y)$ (mod n), the equivalent for addition I am assuming is $(x+0) + (y+0) = (x + y)+0$ ?

If this is the case than I can see that addition modulo n mimics addition in this way. It is then tempting to say that addition modulo n inherits other properties of addition like associativity. However I cannot see how the associativity can be directly proved using the $x$ (mod n) = $r +nk$ expressions that you have used or the above result. Is there much more to this inheritence than you have outlined or can we not directly prove the associativity of addition modulo n (i.e using good old fashioned algebra)?

many thanks

**Gamma** · July 24th 2009, 09:22 AM

See the thing we need to remember that when dealing with modular arithmetic is that they are equivalence classes.
a~b (mod n) iff n|(a-b).

So you usually denote the equivalence class containing a as $[a]=\{x\in \mathbb{Z}|n|(x-a)\}= \{a+nk|k\in \mathbb{Z}\}$ . So what we really need to do is check that the following sets are the same.

$([a]+[b])+[c]=[a]+([b]+[c])$

$[(a+nk) + (b + nl)]+(c+nj)=[(a+b)+n(k+l)]+(c+nj)=$ $(a+b+c)+n(k+l+j)=a+nk+[(b+c)+n(l+j)]=a+nk+[(b+nl) + (c+nj)]=$

The above quantity shows fwhen read from left to right that $([a]+[b])+[c]\subset [a]+([b]+[c])$
And from right to left we get $([a]+[b])+[c]\supset [a]+([b]+[c])$
so
$([a]+[b])+[c]=[a]+([b]+[c])$

I think this is the proof you are looking for, but you notice the proof still comes down to the fact that addition in the integers is associative, this is because we have simply imposed an equivalence relation on the integers.

**leinad** · July 24th 2009, 10:05 AM

Thanks again Gamma

I do not have the time to go through this now but I will soon. It is all starting to clear in my head a little.

I will post again soon in reply.

cheers

**leinad** · July 28th 2009, 04:01 AM

Hi there Gamma

May I thank-you once again for your help, I appreciate it very much.

I see your point that using $[a]=\{x\in \mathbb{Z}|n|(x-a)\}= \{a+nk|k\in \mathbb{Z}\}$ to denote the congruence class containing $a$ , you have shown, using the associativity property of addition, that addition of congruence classes is also associative. Forgive my ignorance but do we not need to show this for the sets containg just $a$ , $b$ and $c$ or is this somehow automatically proved?

For example can I modify your proof somehow by using your previous definition of an interger using the division algorithm $a=r+nf$ say, to get
$(a+b)+c$ (mod n)= $(r+nf + s + ng)+(t+nh)$ (mod n)=??= $a+(b+c)$ (mod n).

Or do we just now somehow limit the set notation for the congruence class containing a to be the set just containing a, for example something like
$[a]=\{x\in \mathbb{Z}|n|(x-a),x-a=a\}= a$ ?

Any help as ever will be welcomed.

**Gamma** · July 28th 2009, 06:41 AM

Originally Posted by leinad

Hi there Gamma

For example can I modify your proof somehow by using your previous definition of an interger using the division algorithm $a=r+nf$ say, to get
$(a+b)+c$ (mod n)= $(r+nf + s + ng)+(t+nh)$ (mod n)=??= $a+(b+c)$ (mod n).

This comes back to my point of modular arithmetic being well defined. If you have the same number in the integers and reduce it mod n, it is still equal. It is an equivalence relation and in particular it is reflexive.

If a=a for an integer a. then certainly $n|(a-a) \Leftrightarrow a \equiv a$ (mod n).

$(a+b)+c$ (mod n)= $(r+nf + s + ng)+(t+nh)$ (mod n)= $r+nf + s + ng+t+nh$ (mod n)= $r+nf + (s + ng+t+nh)$ (mod n)= $a+(b+c)$ (mod n)

**leinad** · July 30th 2009, 07:53 AM

Hi Gamma

Thanks again for your efforts. It seems I am having an all too familiar evaporation of understanding! I think this whole modular arithmetic thing is too unfamiliar right now. I am going to take a little time and mull over the things you have shown me and I will get back to you soon.

cheers

**leinad** · September 7th 2009, 03:13 AM

Hi there math helpers.

As you can see I have been trying to follow this thread for a while now and am still struggling despite huge amounts of help from Gamma. I am reasonably familiar now I think with the concept of modulo n, addition modulo n, congruence classes etc.

I am trying to show that addition modulo n is associative, the usual way to write this is
$(a + b) + c (mod n) = a + (b + c) (mod n)$ .

Now I think this notation is confusing. For example if I use some notation that Gamma used in one of his previous replies, that is $\phi(x)=x(mod n)$ then in words this means obviously to divide x by n and take the remainder. The expression $\phi(x+y)$ then means to add x and y and to then divide by n and take the remainder. So my question is can I write
$(a + b) + c (mod n) = a + (b + c) (mod n)$
as
$\phi( \phi(a+b) + c)=\phi( a + \phi(b+c))$
or should it be
$\phi((a+b) +c)=\phi(a + (b+c))$
??
If the last expression is correct then I can see that the proof of associativity is easy, if the first expression is the correct one then I am still struggling with this proof!

Any help would be greatly appreciated.

**aidan** · September 7th 2009, 11:34 AM

Originally Posted by sjenkins

...
I am ... confused with the concept of modulo.
Can someone please explain exactly what it is?
...

simply put modulo is the REMAINDER after division.

Do the long division on this:

$\dfrac{2536}{2436}$

Quotient equals 1 w/Remainder of 100
2536 mod 2436 = 100 (mod is short for modulo)

now long divide the following but discard the quotients, keeping the remainder

2536 modulo 2436 = 100
12181 modulo 2436 = 1 (12181/2436 = 5 w/remainder of 1)
12182 modulo 2436 = 2 (12182/2436 = 5 w/remainder of 2)
85274 modulo 2436 = 14 )85274/2436 = 35 w/remainder of 14)

Inverses (without too much overkill)
What is the inverse of 5
You should say 1/5

What is the inverse of 13?
How about 1/13.

So:

$5 \times \dfrac{1}{5} = 1$

$13 \times \dfrac{1}{13} = 1$

A number times its inverse equals 1.

Show that 937 is an inverse of 13 modulo 2436.

What you are searching for is some number (say B) such that

13 x B is equivalent to 13 x 1/13 = 1 [modulo the modulus]

or

13 x B = 1 + 2436 x (SomeQuotient)

$\dfrac{13 \times B}{2436} \equiv$ SomeQuotient w/remainder of 1

you want a remainder of 1 AFTER the division

13 x 937 = 2436 x 5 + 1

$\dfrac{13 \times 937}{2436}$ = 5 w/REMAINDER OF 1

In this case 937 is the equivalent of 1/13.

.

Thread: Modulo question

LinkBack

Thread Tools

Display

Modulo question

proving that addition modulo n is associative

Good old fashioned algebra

thanks

equivalence class containing a Vs class just containg a

problems with notation for modulo n

Similar Math Help Forum Discussions

modulo question

modulo question

modulo question

Modulo Question: Proof

question on inverse modulo m

Search Tags