Main content

## Computer science

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

# Equivalence relations

## Equivalent Statements

Before proceeding it’s important to remember the following statements are equivalent

- C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (The | symbol means divides, or is a factor of)
- A, equals, B, plus, K, dot, C (where K is some integer)

This lets us move back and forth between

**different forms**of expressing the**same idea**.**For example**the following are equivalent:

- 5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis ( 5, space, vertical bar, space, minus, 10, which is true since 5, times, left parenthesis, minus, 2, right parenthesis, equals, minus, 10 )
- 13, equals, 23, plus, K, dot, 5. We can satisfy this with K, equals, minus, 2: 13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, times, 5

## Congruence Modulo is an Equivalence Relation

Convince yourself that the slices used in the previous example have the following properties:

- Every pair of values in a slice are related to each other
- We will never find a value in more than one slice (slices are mutually disjoint)
- If we combine all the slices together they would form a pie containing all of the values

A pie with slices that have these properties has an

An

**equivalence relation**.An

**equivalence relation**defines how we can**cut up**our pie (how we**partition**our set of values) into slices (**equivalence classes**).In general, equivalence relations must have these properties:

- The pie: A collection of all the
**values we are interested in** - A slice of pie: An
**equivalence class** - How we cut the pie into slices:
**equivalence relation**

Specifically, for our previous example:

- The pie: The collection of
**all integers** - A slice of pie labelled B: Equivalence class where all the values start text, m, o, d, space, end text, C, equals, B
- How we cut the pie into slices: Using the
**congruence modulo C**relation, \equiv, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

This is why we say that

*Congruence modulo C is an equivalence relation*. It partitions the integers into**C different equivalence classes**.## Why do we care that congruence modulo C is an equivalence relation ?

Knowing that congruence modulo C is an equivalence relation lets us know about some properties that it must have.

**Equivalence relations**are relations that have the following properties:- They are
**reflexive**: A is related to A - They are
**symmetric**: if A is related to B, then B is related to A - They are
**transitive**: if A is related to B and B is related to C then A is related to C

Since

**congruence modulo is an equivalence relation for (mod C)**. This means:- if A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis then B, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
- if A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis and B, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis then A, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

## Example

Let's apply these properties to a concrete example using start text, m, o, d, space, end text, 5, colon

- 3, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (
**reflexive property**) - if 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis then 8, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (
**symmetric property**) - if 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis and if 8, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis then 3, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (
**transitive property**)

## Want to join the conversation?

- can you explain more of reflexive properties with simpler examples? thanks.(7 votes)
**Reflexive property**

This is a property, that some**relations**have, that says that an element must be related to itself.**An example relation with the reflexive property**:

We have a relation, R, that is "has the same father as" i.e. if x is related to y then x has the same father as y

we would write this as:

x R y

This relation has the reflexive property, since x must have the same father as x, i.e. it is always true that x is related to x.

Written as:

x R x**An example relation without the reflexive property**:

We have a relation, G, that is "is less than" i.e. if x is related to y then x < y

we would write this as:

x G y

This relation does not have the reflexive property, since x can not be less than x.**Reflexive property for congruence modulo**:

Our relation, ≡ (mod C), is true when both elements have the same value mod C. i.e. if x ≡ y (mod C) then x mod C = y mod C

It is always true that x ≡ x (mod C) since x mod C = x mod C, thus the reflexive property holds for congruence modulo.

e.g.

5 ≡ 5 (mod 2)

7 ≡ 7 (mod 4)

13131313 ≡ 13131313 (mod 1554544774)

Hope this makes sense(25 votes)

- do you learn this in college?(4 votes)
- Yes, generally in a number theory class, although it can show up in some classes on discrete mathematics as well.(14 votes)

- Not sure where to ask this, so here goes:

Please note the equal sign is used instead of congruence, text is used in places instead of symbols.

Introduction to Algorithms (second printing) MIT Press. Page 805 has the following:

Theorem 33.2

If a and b are any integers, not both zero, then gcd(a,b) is the smallest positive element of the set {ax + by : x,y are members of Integers} of linear combination of a and b.

Proof

Let s be the smallest positive such linear combination of a and b, and let s = ax + by for some x and y members of Intergers. Let q = lower_bound(a/s). Equation 33.2 (a mod s = a - lower_bound(a/s) * s) then implies:

a mod s = a - qs

= a – q(ax +by)

= a(1 – qx) + b(-qy)

and thus a mod s is a linear combination of a and b as well. But since a mod s < s we have that a mod s = 0, because s is the smallest positive such linear combination.

…

My problem is with the last sentence, I don't see the justification for a mod s equaling zero. I know what it says but it seems like hand waving to me.

Can anyone tell me why this is true?

Any help would be appreciated!

Mark.(6 votes) - I think this section would be even more awesome if there would be an explanation of why it is so that C divides (A - B). So thats my question :-) How and why C divides (A - B) holds.(5 votes)
- Here are some requested proofs:
**PROOF THAT THE EQUIVALENT STATEMENTS ARE EQUIVALENT**

By definition A≡B (mod C) means C | (A-B)

This is a definition, so no proof required.**Proof that if C | (A-B) then A = B + K * C**

Suppose C|(A-B).

This means A-B = K * C where K is some integer

we rearrange this to obtain

A = B + K * C

Thus, if C | (A-B) then A = B + K * C

As was to be shown.**Proof that if A = B + K * C then A mod C = B mod C**

Definition of mod says:

if A = K * C + R where 0 <= R < C-1

then A mod C = R )

By the quotient remainder theorem:

A = Q * C + R where 0 <= R < C-1

By definition of mod: A mod C = R

Equating the two equations we have:

A = B + K * C = Q * C + R

We rearrange this to obtain

B = (Q-K) * C + R

By definition of mod: B mod C = R

A mod C = R = B mod C

Thus, if A = B + K * C then A mod C = B mod C

As was to be shown**Proof that if A mod C = B mod C then C|A-B**

Since A mod C = B mod C we can write

(using the quotient remainder theorem):

A = P * C + R

B = Q * C + R

where 0 <= R < C-1

A-B = (P * C + R) - (Q * C + R)

A-B = (P-Q) * C

clearly C | (P-Q) * C thus C | A-B

Thus if A mod C = B mod C then C|A-B

As was to be shown

By combining these proofs you can start at any of the equivalance statements and obtain the others**PROOF THAT CONGRUENCE MODULO IS AN EQUIVALENCE RELATION****Proof congruence modulo is reflexive**

We must show that A≡A (mod C)

The statement is equivalent to C|(A-A)

or C|0.

0 = C * 0 thus C|0 is true

Thus congruence modulo is reflexive**Proof congruence modulo is symmetric**

We must show that if A≡B (mod C) then B≡A (mod C)

The statement is equivalent to:

if C|(A-B) then C|(B-A)

Suppose C|(A-B) then (A-B) = C * K where K is an integer

Multiply both sides by -1

B-A = C * -K, thus C|(B-A)

Thus congruence modulo is symmetric**Proof congruence modulo is transitive**

We must show that:

if A≡B (mod C) and B≡D(mod C) then A≡D(mod C)

The statement is equivalent to:

if C|(A-B) and C|(B-D) then C|(A-D)

A-B = C * K where K is an integer

B-D = C * M where M is an integer

add the two equations

A-B + B-D = C * K + C * M

A-D = C * (K+M) thus C|(A-D)

Thus congruence modulo is transitive

We have shown that congruence modulo is reflexive, symmetric and transitive, thus congruence modulo, by definition, is an equivalence relation.

Hope this makes sense(7 votes)

- I am stuck at this article of this subject. Could someone suggest that what could be learned first to have a better fundamental understanding of the subject? I think I need to break it down and learn it piece by piece.(2 votes)
- A lot of this stuff is:

-Set Theory

-Relations

A book I could suggest, which does a good job of covering this material is "Discrete Math with Applications" by Susanna Epp.

You may find that this particular lesson is on the abstract side, and the material that comes further on is more practical. It may be worthwhile to try the material later on and come back to this material to see if it makes more sense after gaining some experience with the more practical side of things.(9 votes)

- Maybe someone can help me with a problem I'm working on. The 17 year cicadas are coming out in VA this year. Two years ago, the 13 year cicadas came out. From this we know that the solutions to 13a+2011=y and 17b+2013=y represent years when both will come out. Setting them equal, subtracting, etc, leaves us with

13a≡2(mod17) where a is the number of cycles of the 13 year cicadas until the two line up. Now here's my question:

Is there a way other than brute force of solving a problem like this?

I noticed this also comes up in RSA when finding a value for one's private key.(4 votes)- To solve an equation like: 13a≡2(mod17) we need to use modular inverses.

The modular inverse of 13, which we will label as 13^-1, would be a number that we could multiply by 13 such that 13 * 13^-1 mod 17 = 1.

We can find a modular inverse of 13 by brute force or by using the Extended Euclidian Algorithm.

This program shows the extended euclidean algorithm. It shows that the modular inverse of 13 (mod 17) is 4. We can test it, 13 * 4 mod 17 = 52 mod 17 = 1

https://www.khanacademy.org/cs/modulo-inverse-using-the-extended-euclidean-algorithm/1604704343

Now that we have the modular inverse of 13 (mod 17) we can solve the equation.

13a≡2(mod 17)

Now we multiply both sides by the modular inverse of 13 (mod 17)

13 * 13^-1 * a ≡ 2 * 13^-1 (mod 17)

On the left we have 13 * 13^-1 mod 17 =1. On the right we replace 13^-1 by its value of 4.

1 * a ≡ 2 * 4 (mod 17)

a ≡ 8 (mod 17)

or

a= 8+17 k where k is some integer

Hope this makes sense(4 votes)

- So overall, whenever we see A≡B (mod C) can we think that A (mod C) = B (mod C) ? If we are asked to find out whether X≡Y (mod Z), do we just think in our minds if X (mod Z) = Y (mod Z) ?(4 votes)
- Are you sure in the first paragraph, "Equivalent Statements", the line that claims "A = B + K * C (where K is some integer)" doesn't mean "A ≡ B + KC"? BECAUSE: A might not equal (B+KC) Because although they are in the same equivalence class, they might be two different integers. Im pretty crazy about being exact with my math, and nothing to blame, but I just wanted to know if it should be CONGRUENT rather than EQUIVALENT.(2 votes)
- Certainly we can say that "A ≡ B + K * C" (mod C) , but we can make the even stronger statement that "A= B + K * C" is equivalent to the other statements.

(This comes from the quotient remainder theorem).

Note, not just any K will do. There is a unique K that exists for each A,B and C to make this true.

Perhaps it may be helpful to think of it this way.

"A ≡ B (mod C)" says that A and B are in the same equivalence class (mod C)

"A=B+KC" can be interpreted as saying that any two values within the equivalence class are a multiple of C apart (this is true)

Hope this makes sense(5 votes)

- 23 ( mod 5 ) does not equal 13!!(3 votes)
- Anything mod 5 cannot equal 13. After all, 13 cannot be the remainder of anything/5(2 votes)

- I'm. Just. Trying. To. Understand. RSA. Encryption!

But maybe I should stick to algebra I :)(3 votes)