Main content

### 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

© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Congruence modulo

## Congruence Modulo

You may see an expression like:

This says that $A$ is $B$ modulo $C$ .

**congruent**toWe will discuss the meaning of

**congruence modulo**by performing a thought experiment with the**regular modulo operator**.Let's imagine we were calculating mod 5 for all of the integers:

Suppose we labelled 5

Think of these slices as buckets, which hold a set of numbers. For example, 26 would go in the slice labelled$26\text{mod}5=\mathbf{1}$ .

Above is a figure that shows some integers that we would find in each of the slices.

**slices**0, 1, 2, 3, 4. Then, for each of the integers, we put it into a**slice**that matched the value of the integer mod 5.Think of these slices as buckets, which hold a set of numbers. For example, 26 would go in the slice labelled

**1**, becauseAbove is a figure that shows some integers that we would find in each of the slices.

It would be useful to have a way of expressing that numbers belonged in the

**same slice**. (Notice 26 is in the same slice as 1, 6, 11, 16, 21 in above example).A common way of expressing that two values are in the same slice, is to say they are in the same

The way we express this mathematically for mod C is:$A\equiv B\text{}(\text{mod}C)$

**equivalence class**.The way we express this mathematically for mod C is:

The above expression is pronounced $A$ is $B$ modulo $C$ .

**congruent to**Examining the expression closer:

is the symbol for congruence, which means the values$\equiv $ and$A$ are in the same$B$ **equivalence class**.tells us what$(\text{mod}C)$ **operation**we applied toand$A$ .$B$ - when we have both of these, we call “
”$\equiv $ **congruence modulo** .$C$

e.g. $26\equiv 11\text{}(\text{mod}5)$

Note, that this is different from $A\text{mod}C$ : $26\ne 11\text{mod}5$ .

## Insights into Congruence Modulo

We can gain some further insight behind what congruence modulo means by performing the same thought experiment using a positive integer

First, we would label

Then, for each of the integers, we would put it into a slice that matched the value of the integer

Below is a figure that shows some representative values that we would find in each of the slices.

**.**$C$ First, we would label

**slices**$C$ **.**$0,1,2,\dots ,C-2,C-1$ Then, for each of the integers, we would put it into a slice that matched the value of the integer

**.**$\text{mod}C$ Below is a figure that shows some representative values that we would find in each of the slices.

If we looked at the bucket labelled

**0**we would find:If we looked at the bucket labelled

**1**we would find:If we looked at the bucket labelled

**2**we would find:If we looked at the bucket for

**we would find:**$C-1$ **From this experiment we can make a key observation:**

The values in each of the slices are equal to the label on the slice plus or minus some

**multiple of**$\mathbf{C}$ .

This means the difference between

**any two values**in a slice is

**some multiple of**$\mathbf{C}$ .

This observation can help us understand equivalent statements and

**equivalence classes**next.

## Want to join the conversation?

- "Note, that this is different from A mod C. 26 ≠ 11 mod 5" But A mod C would be 26 mod 5, according to the definitions of A, B, and C given in this example, so I don't quite see how this statement matches up. Are you trying to stress that 11 mod 5 isn't actually equal to 26? Hope Khan Academy can clarify that statement a little bit (:(25 votes)
- What is being stressed is the difference between ≡ and =

26 ≡ 11 (mod 5)

Proof: 26 mod 5 = 1 and 11 mod 5 = 1, Both are in the equivalence class for 1

However it would be incorrect to write:

26 = 11 mod 5

since 11 mod 5 = 1 , so this equation would be saying that

26 = 1 , which is not true

Hope this makes sense(113 votes)

- I was wondering if anyone could help me with these sort of questions: "Find the general solution of the simultaneous congruences

5x ≡ 2 mod 8, 3x ≡ 5 mod 11."

Thanks(4 votes)- it appears to me that the prior answer was to the wrong question...

you are seeking every integer x such that 5x%8==2 AND 3x%11==5, right?

because both 5x and 3x must be integers we begin with the infinite series

... -30, -15, 0, 15, 30, 45 ...

for our values to test for both 5x and 3x; we can ignore all other numbers

applying the rule 5x%8==2, we find 5x==-30 works and of course every eighth entry before or after it will also work, so 5x is ... -30, 90, 210, ...

applying the other rule, 3x%11==5, we find 60 works, as will every 11th entry before or after it, so 3x is ... -105, 60, 225, ...

so now we know that 3x is 60+165n for some integer n AND 5x is 90+120m for some integer m

so x is 20+55n and x is 18+24m for some still unknown m and n

so we find a match of the two series

20, 75, 130, 185, 240, 295, 350, 405, 460, 515, 570, 625, 680 ...

and

18, 42, 66, 90, 114, 138, 162, 186, 210, 234, 258, 282, ...

and the first match is 570

(i actually mentally cheated by changing the

second series to

90, 210, 330, 450, 570, 690, ...

because a match must be a multiple of 5)

well, 55 and 24 are relatively prime so the other matches will be 570+(55)(24)z for some integer z

that's x==570+1320z, a general solution to both modular congruences (is that misspelled?)

now because i did this all without a calculator, i should check for arithmetic and logical errors

(a) does 570 actually work?

5(570)%8 is 2850%8 is 50%8 is 2 which works

3(570)%11 is 1710%11 is 500%11 is 60%11 is 5 which works

and (b) will both clocks wrap after 1320?

11 * 8 * 15 is 1320 so yes

and (c) can both clocks wrap over a smaller interval than 1320?

these three factors are relatively prime so no

someone with an actual math background can probably phrase this better (and shorter), hoping someone does...(2 votes)

- In one of his previous lessons, Brit mentioned the term "primitive root". I forgot to ask what that term meant, but I saw Liam Adams' question and now I'd like to ask, what is a primitive root?(2 votes)
- A primitive root, g, that when repeatedly multiplied by itself (mod n) generates all the numbers coprime to n.

It is also called a generator (mod n).

If n is prime it will generate all the numbers between 1 and n-1.

e.g.

3 is a generator, or primitive root (mod 7) since:

g^1 mod 7 = 3 mod 7 = 3

g^2 mod 7 = 9 mod 7 = 2

g^3 mod 7 = 27 mod 7 = 6

g^4 mod 7 = 81 mod 7 = 4

g^5 mod 7 = 243 mod 7 = 5

g^6 mod 7 = 729 mod 7 = 1

5 is also a primitive root mod 7. (try it yourself)(8 votes)

- I don't understand the "Insights into Congruence Modulo" diagram. Help?(4 votes)
- The diagram shows how the integers modulo C are related.

The diagram is split into C pieces: 0, 1, 2, 3, ..., C-2, C-1.

In the piece with 0, we can find:

..., -4C, -3C, -2C, -C, 0, C, 2C, 3C, 4C, ...

Notice how all of these are multiples of C.

In the piece with 1, we can find:

..., -4C+1, -3C+1, -2C+1, -C+1, 1, C+1, 2C+1, 3C+1, 4C+1, ...

Notice how all of these are multiples of C plus 1.

In fact, in any piece with*n_*, there will be multiples of C plus*_n*. That's how the modulo C operator works and that's what the diagram shows.

I hope this helps you understand the diagram!(4 votes)

- what is modulus congruence in simple?(1 vote)
- Modulus congruence means that both numbers, 11 and 16 for example, have the same remainder after the same modular (mod 5 for example). 11 mod 5 has a remainder of 1. 11/5 = 2 R1. 16 mod 5 also has a remainder of 1. 16/5 = 3 R1. Therefore 11 and 16 are congruent through mod 5.(8 votes)

- The above explanation does not clearly explain the how to arrive at the determination of the slice for negative numbers (it assumes you can do that without explaining how).(3 votes)
- " for each of the integers, we would put it into a slice that matched the value of the integer mod C."

-the integers includes negative integers

To see how to calculate the mod for negative integers have a look at:

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/e/modulo-operator

(The hints for the exercises will show you step by step)(2 votes)

- What is a modulus?(2 votes)
- A modulus is B in this expression: A mod B = C.

e.g. In the expression 5 mod 2 = 1, the modulus is the 2.(2 votes)

- 𝑥^103≡4 𝑚𝑜𝑑 11,solve for x?(1 vote)
- From fermat's little theorem we have:

a^(p-1) mod p = 1

where:

- p is a prime number

- a is coprime to p i.e. gcd(a,p)=1

So:

x^10 mod 11 = 1

x^103 mod 11 = 4 mod 11

which we can group like:

(x^10)^10 * x^3 mod 11 = 4 mod 11

And since x^10 mod 11 = 1 :

1^10 * x^3 mod 11 = 4 mod 11

which leaves us with the much simpler:

x^3 mod 11 = 4 mod 11

We only have to check from x = 0 to 10, so we can just brute force check each one:

If we choose x = 5

5^3 mod 11 = 125 mod 11 = 4 mod 11

So the answer is:

x mod 11 = 5

or

x = 11k + 5 where k is some integer(3 votes)

- in the second illustration down the page between slices 3 & C-2 is '...'.

could someone kindly explain or define what slice '...' is or represents?

thank you in advance(1 vote)- The '...' are ellipsis. They indicate that the pattern continues.

If you saw:

1, 2, 3, 4, ..., 9, 10 the '...' would represent 5, 6, 7, 8

In the article '...' represents the slices between 3 and C-2

e.g. the next slice would be 4, the next last slice would be C-3(2 votes)

- -8 ≡ 7 (mod 5) is true because 7--8 = 15 and it can be divided into 5, but they are not in the same equivalence class: -8 mod 5= 3 and 7 mod 5 = 2. Why is that? I thought they would also have the same equivalence class?(1 vote)