1. ## Questions about modular arithmetic

Hi there

I am a little bit confused about modular arithmetic. I don't quite understand what it really means when one number is logically equivalent to another. For example in my book it says:

7 ≡ 2 (mod 5)

what is it about 7 that makes it logically equivalent to 2 (mod 5)? I also believe the book says that 18 is logically equivalent to 3. Does that perhaps mean that 18 is divisible by 3?

In my book it also says that:

h(064212848) = 037149212 mod 111 = 14 , but I don't see how this can be correct. I mean, I am sure the book is correct, I just don't understand why hehe. I really hope someone can help me. Thank you!

2. ## Re: Questions about modular arithmetic

Hi, 7 = 2 (mod 5) means that if you divide 7 by 5 the reainder is 2

7 = 1(5) + 2

Another example:

100 = 1 (mod 33) because 100 = 3(33)+ 1

I helped you ?

Steve

3. ## Re: Questions about modular arithmetic

Originally Posted by Nora314
Hi there

I am a little bit confused about modular arithmetic. I don't quite understand what it really means when one number is logically equivalent to another. For example in my book it says:

7 ≡ 2 (mod 5)

what is it about 7 that makes it logically equivalent to 2 (mod 5)? I also believe the book says that 18 is logically equivalent to 3. Does that perhaps mean that 18 is divisible by 3?

In my book it also says that:

h(064212848) = 037149212 mod 111 = 14 , but I don't see how this can be correct. I mean, I am sure the book is correct, I just don't understand why hehe. I really hope someone can help me. Thank you!
Modular arithmetic is sometimes called "clock arithmetic", because it's very similar to how clocks work, because they "repeat" or "loop" every 60 seconds, every 60 minutes, every 12 hours, etc... There's no such thing as say "80 past 12".

Say the time was 5:40pm and you knew it took half an hour to cook dinner, what time should you tell your family to be home by? Obviously you can't do 5:40 + 0:30 = 5:70, because you know after 60 minutes, the number of minutes repeats, while the number of hours is increased. Rather, it's 6:10.

So to answer your question, why is 7 equivalent to 2 mod 5, mod 5 means that the numbers will be repeating after 5. So if you counted out the first seven numbers, remembering that you have to repeat the pattern after 5, you end up with 1, 2, 3, 4, 5, 1, 2. The seventh number is 2, so we can say that 7 is equivalent to 2, as long as you are in mod 5.

As for 18 being logically equivalent to 3 (I assume in mod 5), we know that the numbers will repeat after every five digits, and there are three fives in 18, with a remainder of 3. That means that you'll go through the loop three times, and then count 1, 2, 3. Therefore 18 is equivalent to 3 in mod 5.

4. ## Re: Questions about modular arithmetic

Thank you so much both of you! Ah, I love you people on MHF, I post a question and someone always replies with really cool answers

Thank you Prove It, I see this in a different way now when I think of it as a clock, that was a very nice way of explaining it.
And MathTutor, thank you it helped too, thanks for including another example.

5. ## Re: Questions about modular arithmetic

Originally Posted by Nora314
Hi there

I am a little bit confused about modular arithmetic. I don't quite understand what it really means when one number is logically equivalent to another. For example in my book it says:

7 ≡ 2 (mod 5)

what is it about 7 that makes it logically equivalent to 2 (mod 5)? I also believe the book says that 18 is logically equivalent to 3. Does that perhaps mean that 18 is divisible by 3?

In my book it also says that:

h(064212848) = 037149212 mod 111 = 14 , but I don't see how this can be correct. I mean, I am sure the book is correct, I just don't understand why hehe. I really hope someone can help me. Thank you!
What do you mean by h(064212848)?

6. ## Re: Questions about modular arithmetic

Originally Posted by Nora314
I am a little bit confused about modular arithmetic. I don't quite understand what it really means when one number is logically equivalent to another. For example in my book it says:
7 ≡ 2 (mod 5)
Drop the concept "one number is logically equivalent to another"
That has no place here if you are just starting to learn this topic.
Here the symbol $\equiv$ is use mathematically to mean equivalent class.
To say that integers $m\equiv n\mod k$ means that $m~\&~n$ have the same remainder when divided by $k$.

Thus $13\equiv 19\mod 6$ but $16\not\equiv 23\mod 5~.$

7. ## Re: Questions about modular arithmetic

Thank you Plato I am new to discrete mathematics and I thought that the symbol "≡" meant logically equivalent, since that is what the book used that symbol for before. I really liked your explenation.

What do you mean by h(064212848)?
Well, in my book, after they explain modular arithmetic they try to talk about how it can be applied to real life situations. So they talk about the Hashing Functions. The Hashing function is apperiantly supposed to be used to track down customer records in, let's say, an insurance company.

They say one type of Hashing function is:

h(k) = k mod m

The book also says that m is supposed to represent memory locations in a computer, and k which in this case is 064212848 would be someone's social security number.
So they say that to find h(k) you only need to compute the remainder when k is divided by m.

In this case: h(064212848) = 064212848 mod 111 = 14. I just don't see how when you divide 064212848 with 111 the remainder is 14.
This is all the information the book gives.

8. ## Re: Questions about modular arithmetic

Originally Posted by Nora314
In this case: h(064212848) = 064212848 mod 111 = 14. I just don't see how when you divide 064212848 with 111 the remainder is 14.
This is all the information the book gives.
This webpage may help
[Modulo operation - Wikipedia, the free encyclopedia
Page down to find this "Knuth[5] described floored division where the quotient is defined by the floor function q=floor(a/n) and the remainder r is"