If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Equivalence relations

Equivalent Statements

Before proceeding it’s important to remember the following statements are equivalent
  • AB (mod C)
  • A mod C=B mod C
  • C | (AB) (The | symbol means divides, or is a factor of)
  • A=B+KC (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:
  • 1323 (mod 5)
  • 13 mod 5=23 mod 5
  • 5 | (1323) ( 5 | 10, which is true since 5×(2)=10 )
  • 13=23+K5. We can satisfy this with K=2: 13=23+(2)×5

Congruence Modulo is an Equivalence Relation

pie

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 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 mod C=B
  • How we cut the pie into slices: Using the congruence modulo C relation, (mod C)
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:
  • AA (mod C)
  • if AB (mod C) then BA (mod C)
  • if AB (mod C) and BD (mod C) then AD (mod C)

Example

mod5
Let's apply these properties to a concrete example using mod 5:
  • 33 (mod 5) (reflexive property)
  • if 38 (mod 5) then 83 (mod 5) (symmetric property)
  • if 38 (mod 5) and if 818 (mod 5) then 318 (mod 5) (transitive property)

Want to join the conversation?

  • blobby green style avatar for user Juneelyn Bacaltos
    can you explain more of reflexive properties with simpler examples? thanks.
    (5 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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
      (28 votes)
  • leafers ultimate style avatar for user 18agneyap
    do you learn this in college?
    (4 votes)
    Default Khan Academy avatar avatar for user
  • orange juice squid orange style avatar for user Mark Henwood
    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)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user 42436
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • leafers ultimate style avatar for user Shreyas Pai
    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) ?
    (5 votes)
    Default Khan Academy avatar avatar for user
  • leaf blue style avatar for user Pete C.
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • old spice man green style avatar for user Daniel Friess
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • male robot hal style avatar for user Andrew R. Howe
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • duskpin ultimate style avatar for user BugattiVeyron5
    23 ( mod 5 ) does not equal 13!!
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user owen.agnel
    I'm. Just. Trying. To. Understand. RSA. Encryption!
    But maybe I should stick to algebra I :)
    (3 votes)
    Default Khan Academy avatar avatar for user