Modular Arithmetic Tutorial for Beginners (Free)

Intro

Modular arithmetic is used in programming and computer science in general.

So every beginner programmer should have a basic understanding of modular arithmetic.

This tutorial aims to help develop this basic understanding, by giving simple and concise explanation.

How it works

With modular arithmetic you count till you reach a certain limit. When you reach this limit you start over again.

That is how simple it actually is.

The limit you set is called the modulus and can be any integer (whole number).

We use modular arithmetic every day without realising it.

Think about a normal clock. When it reaches 12 o’clock, the counting starts over again. So the modulus here is 12.

If we take a digital clock, the modulus is 24. When it reaches 12 o’clock, the counting still continues 13, 14, 15 … till it reaches 24.

Conversion

Any whole number can be converted to a modular number.

Often it is necesarry to do this or at least to understand that this happens.

We take the number 23 and a modulus of 5.

Something has to be done to the 23 in order to fit the modulus of 5.

You have to look at how many times 5 fits in 23.

We have to divide 23 by 5 and take the remainder.

Then you only use the remainder of the number. The remainder here is 3, so in more formal notation:

23 ≡ 3 mod 5

We use the “congruence symbol”, a three barred equal sign to indicate that 23 is equivalent to 3 modulus 5.

Addition

Addition in modular arithmetic works like regular addition.

Add two numbers together, divide the sum by the modulus while keeping the remainder.

Example:

3 mod 5 + 8 mod 5 ≡ 1 mod 5

Because, 3 + 8 = 11

11 – 5*2 = 1

Multiplication

Multiplication is not very different. Just multiply the numbers together, divide by the modulus and take the remainder. You actually just take out a factor of the modulus from the sum.

3 mod 5 * 8 mod 5 ≡ 4 mod 5

3 * 8 = 24

24 – 5*4 = 4

It is a good idea to make a few tables like the following to get used to this kind of arithmetic.

+01234
001234
112340
223401
334012
440123
Addition
*01234
000000
101234
202413
303042
404321
Multiplication

Subtraction

Subtraction can be confusing. First, a simple example:

18 mod 20 – 9 mod 20 ≡ 9 mod 20

But what if the initial answer is negative like the next one:

9 mod 20 – 17 mod 20

9 – 17 = -8

You have to actually add the modulus till the answer is positive:

-8 +20 = 12

So,

-8 ≡ 12 mod 20

Division

Division is much complexer. It does not work like regular division.

If you have:

18 ≡ 8 mod 10

And you want to divide both sides by 2:

9 ≡ 4 mod 10

As you can see, this doesn’t make any sense. So division is not always possible.

You have to look at two numbers, the number you want to divide with and the modulus.

Then look at the gcd of these two numbers. The gcd is the biggest number you can divide both numbers with.

If the gcd is bigger than 1, division won’t work.

Let’s take a look at the next example:

12 ≡ 2 mod 5

We try to divide by 2 again:

6 ≡ 1 mod 5

As you can see this time the result makes sense, because 2 and 5 have a gcd of 1. While in the example before 2 and 10 have a gcd of 2.