The essence of modular arithmetic

.

Introduction :

Why do we need modular arithmetic?

Let’s look at an example of a finite set of integers from everyday life:

Example 1.4. Consider the hours on a clock. If you keep adding one hour, you obtain:

1h,2h,3h,…,11h,12h,1h,2h,3h,…,11h,12h,1h,2h,3h,…

Even though we keep adding one hour, we never leave the set.

Let’s look at a general way of dealing with arithmetic in such finite sets.

Example 1.5. We consider the set of the nine numbers:

{0,1,2,3,4,5,6,7,8}

We can do regular arithmetic as long as the results are smaller than 9. For instance:

2×3 = 6

4+4 = 8

But what about 8+4? Now we try the following rule: Perform regular integer arithmetic and divide the result by 9. We then consider only the remainder rather than the original result. Since 8+4 = 12, and 12/9 has a remainder of 3, we write: 8+4 ≡ 3 mod 9

Intuition:

The number after the mod is called the ring size, which is the maximum known number in the new setting which is the modular world or ring

Let’s consider the clock example in the 12 settings:

Let’s say it’s 16:00 now, how do you interpret that to normal hours? You subtract 12 hours form 16 and you get 4, then it’s 4 PM

So the next time you see the question: what is 17 mod 7 ask your self: in a world contains numbers from 0 to 6 only what would be 17

Use the hour intuition to calculate it if you want, keep subtracting 7s from the modulus until the result is less than the modulus. And that’s the result.

Also the question of 7+5 mod 2: ask yourself in a world that consists only of numbers less than 2: [0,1] what would be 7+5?

I hope that helps :)

References :

Paar C., Pelzl J. (2010) Introduction to Cryptography and Data Security. In: Understanding Cryptography. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04101-3_1:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store