Main content

## Computer science theory

### Course: Computer science theory > Unit 2

Lesson 5: Modular arithmetic- What is modular arithmetic?
- Modulo operator
- Modulo Challenge
- Congruence modulo
- Congruence relation
- Equivalence relations
- The quotient remainder theorem
- Modular addition and subtraction
- Modular addition
- Modulo Challenge (Addition and Subtraction)
- Modular multiplication
- Modular multiplication
- Modular exponentiation
- Fast modular exponentiation
- Fast Modular Exponentiation
- Modular inverses
- The Euclidean Algorithm

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# What is modular arithmetic?

## An Introduction to Modular Math

When we divide two integers we will have an equation that looks like the following:

Sometimes, we are only interested in what the $A$ by $B$ .

For these cases there is an operator called the modulo operator (abbreviated as mod).

**remainder**is when we divideFor these cases there is an operator called the modulo operator (abbreviated as mod).

Using the same $A$ , $B$ , $Q$ , and $R$ as above, we would have: $A\text{mod}B=R$

We would say this as $A$ $B$ $R$ . Where $B$ is referred to as the

*modulo**is equal to***modulus**.For example:

## Visualize modulus with clocks

Observe what happens when we increment numbers by one and then divide them by 3.

The remainders start at 0 and increases by 1 each time, until the number reaches one less than the number we are dividing by. After that, the sequence

**repeats**.By noticing this, we can visualize the modulo operator by using circles.

We write 0 at the top of a circle and continuing clockwise writing integers 1, 2, ... up to one less than the modulus.

For example, a clock with the 12 replaced by a 0 would be the circle for a modulus of 12.

To find the result of $A\text{mod}B$ we can follow these steps:

- Construct this clock for size
$B$ - Start at 0 and move around the clock
steps$A$ - Wherever we land is our solution.

(If the number is positive we step clockwise, if it's

**negative**we step**counter-clockwise**.)## Examples

$8\text{mod}4=?$

With a modulus of 4 we make a clock with numbers 0, 1, 2, 3.

We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0, 1, 2, 3, 0.

We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0, 1, 2, 3, 0.

We ended up at $8\text{mod}4=\mathbf{0}$ .

**0**so$7\text{mod}2=?$

With a modulus of 2 we make a clock with numbers 0, 1.

We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0, 1.

We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0, 1.

We ended up at $7\text{mod}2=\mathbf{1}$ .

**1**so$-5\text{mod}3=?$

With a modulus of 3 we make a clock with numbers 0, 1, 2.

We start at 0 and go through 5 numbers in

We start at 0 and go through 5 numbers in

**counter-clockwise**sequence (5 is**negative**) 2, 1, 0, 2, 1.We ended up at $-5\text{mod}3=\mathbf{1}$ .

**1**so## Conclusion

If we have $A\text{mod}B$ and we increase $A$ by a

**multiple of**$\mathbf{B}$ , we will end up in the same spot, i.e.for $A\text{mod}B=(A+K\cdot B)\text{mod}B$ any integer.$\mathbf{K}$

For example:

## Notes to the Reader

### mod in programming languages and calculators

Many programming languages, and calculators, have a mod operator, typically represented with the % symbol. If you calculate the result of a negative number, some languages will give you a negative result.

e.g.

e.g.

`-5 % 3 = -2.`

### Congruence Modulo

You may see an expression like:

$A\equiv B\text{}(\text{mod}C)$

This says that $A$ is $B$ modulo $C$ . It is similar to the expressions we used here, but not quite the same.

**congruent**toIn the next article we will explain what it means and how it is related to the expressions above.

## Want to join the conversation?

- In the last example, the answer is 1. I understand how you got the answer using the clock, but I thought the point of the modulo operator was to find the remainder, and if you divide -5 by 3, the remainder would be 2. Why are these answers different??(131 votes)
- It is true that 5 divided by 3 gives you a remainder of 2

However, it is NOT true that -5 divided by 3 gives you a remainder of 2. It gives you a remainder of 1.

We can do some long division to prove it:

First we'll do the simple 5/3`_1_R2`

3 / 5

-3 (Since 1 * 3 = 3)

---

2

We can check our result:`5 = 1 * 3 + 2`

Now we can do -5/3`_-2_R1`

3 / -5

-(-6) (Since -2 * 3= -6)

---

1

We can check our result:`-5 = -2 * 3 + 1`

The -2 seems strange since we might think 3 goes into 5, -1 times. But this would make our remainder negative (which is not allowed)

Let's see what would happen, if we allowed negative remainders (we don't, but computers do!) it would look like this:`_-1_R-2`

3 / -5

-(-3) (Since -1 * 3= -3)

---

-2

We can check our result:`-5 = -1 * 3 + (-2)`

Notice that if we go 2 steps counter clockwise on the modular circle for 3 that we end up at 1.

Notice that if we add one multiple of 3 to -2 we end up at 1.

Again, we don't allow negative remainders, but it may give you some intuition for what is going on, and for how congruence modulo works later.

Hope this makes sense(302 votes)

- Who invented Modular Arithmetic?(22 votes)
- Johann Carl Friedrich Gauss is usually attributed with the invention/discovery of modular arithmetic. In 1796 he did some work that advanced the field, and in 1801 published the book Disquisitiones Arithmeticae which, amongst other things, introduced congruence modulo and the ≡ symbol. So he is the person that laid out the modern approach to modular arithmetic that we use today.

Gauss is one of the most influential mathematicians of all time. His name is well known amongst mathematicians.(84 votes)

- -17 mod 7

-7*2=-14

-17 '=' -7 *2 +-3

-7 *2 +-3=-17

why does the site say 4? :((8 votes)- You said -7 *2 = -14, but -14 is actually bigger than -17. We have to go a little further. The next step would be -7*3 = -21, which is smaller than -17. Now from -21, how much do we need to add to get to -17? The answer is 4. Hope this helped! :)(49 votes)

- What happens if the modulus is negative?(13 votes)
- The modulus must be a positive integer i.e. an integer > = 1(26 votes)

- Is the following method (I devised it by observation ) a known / valid method of getting the negative integers reminder?

if A % B = C

then -A % B = B - C

ex: -19 % 4 can be solved with these steps:

19 % 4 = 3

-19 % 4 = 4 - 3 = 1

If valid but not known previously attribute it to me please. all rights reserved.(14 votes)- Yes, it works. It's a cool discovery, but you weren't the first one to discover it.

Here's a simple explanation of how it works.

For our mod n circle.

- positive numbers go clockwise around the circle

- negative numbers go anti-clockwise around the circle

To find where a number has ended up on the circle, in clockwise units, if you have a number measured in anti-clockwise units you have:

#clockwise_units = size_of_circle - #anti_clockwise_units

Remember that the size of the circle for mod n is n.

Later on, you will find that -x (mod n) is congruent to n-x (mod n).

Hope this makes, and good luck with more discoveries(23 votes)

- Can someone explain the concept of calculating mod with out the circles?

How would you do 13 mod 10?(3 votes)- 13 mod 10.

1 R 3

10/13

10

3

The remainder is 3. 13 mod 10 is 3.

I think this method of modulus is easier than the modulus method. What do you think?(13 votes)

- how is 3mod10 = 3?? it should be 0..isnt it??(5 votes)
- 3 / 10 = 0 with a remainder of 3

3 mod 10 gives us the remainder when we divide 3 by 10.

Thus 3 mod 10 = 3(6 votes)

- It seems a typo that '(5 is negative)' just under the -5 mod 3 = ?. I think 5 is a positive number, -5 is negative. (I have already asked this at Crowdin, but no answer for three weeks. )

Best,

H.(2 votes)- Indeed, 5 is a positive number, and -5 is a negative number.

However, for the example:

"-5 mod 3 = ?

With a modulus of 3 we we make a clock with numbers 0,1,2

We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is negative) 2,1,0,2,1"

The "(5 is negative)" is explaining why we are going counter-clockwise as opposed to clockwise

i.e. if we were looking at 5 mod 3 we would start at 0 and go through 5 numbers in a clockwise sequence, (1,2,0,1,2) but in the example we have -5 mod 3, so we start at 0 and go through 5 numbers in a counter-clockwise sequence (2,1,0,2,1)

Hope this makes sense(8 votes)

- There is no video. A congruent B (modulo C). Does this mean that when A or B is divided by C the remainder will be the same?(3 votes)
- You are correct when you say

if we have A ≡ B (mod C) then this will mean when A or B is divided by C the remainder will be the same

For more info, check out:

https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/congruence-modulo(6 votes)

- still dont understand it

more example please(5 votes)