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

Congruence modulo

Congruence Modulo

You may see an expression like:
A, \equiv, B, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
This says that A is congruent to B modulo C.
We 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 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, because 26, start text, space, m, o, d, space, end text, 5, equals, 1.
Above 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 equivalence class.
The way we express this mathematically for mod C is: A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
The above expression is pronounced A is congruent to B modulo C.
Examining the expression closer:
  1. \equiv is the symbol for congruence, which means the values A and B are in the same equivalence class.
  2. left parenthesis, start text, m, o, d, space, end text, C, right parenthesis tells us what operation we applied to A and B.
  3. when we have both of these, we call “\equivcongruence modulo C.
e.g. 26, \equiv, 11, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis
26, start text, space, m, o, d, space, end text, 5, equals, 1 so it is in the equivalence class for 1,
11, start text, space, m, o, d, space, end text, 5, equals, 1 so it is in the equivalence class for 1, as well.
Note, that this is different from A, start text, space, m, o, d, space, end text, C: 26, does not equal, 11, start text, space, m, o, d, space, end text, 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 C.
First, we would label C slices 0, comma, 1, comma, 2, comma, dots, comma, C, minus, 2, comma, C, minus, 1.
Then, for each of the integers, we would put it into a slice that matched the value of the integer start text, m, o, d, space, end text, 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:
dots, comma, minus, 3, C, comma, minus, 2, C, comma, minus, C, comma, 0, comma, C, comma, 2, C, comma, 3, C, comma, dots
If we looked at the bucket labelled 1 we would find:
dots, comma, 1, minus, 3, C, comma, 1, minus, 2, C, comma, 1, minus, C, comma, 1, comma, 1, plus, C, comma, 1, plus, 2, C, comma, 1, plus, 3, C, comma, dots
If we looked at the bucket labelled 2 we would find:
dots, comma, 2, minus, 3, C, comma, 2, minus, 2, C, comma, 2, minus, C, comma, 2, comma, 2, plus, C, comma, 2, plus, 2, C, comma, 2, plus, 3, C, comma, dots
If we looked at the bucket for C, minus, 1 we would find:
dots, comma, minus, 2, C, minus, 1, comma, minus, C, minus, 1, comma, minus, 1, comma, C, minus, 1, comma, 2, C, minus, 1, comma, 3, C, minus, 1, comma, 4, C, minus, 1, dots
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 C.
This means the difference between any two values in a slice is some multiple of C.
This observation can help us understand equivalent statements and equivalence classes next.

Want to join the conversation?

  • leafers sapling style avatar for user melissa.zamojcin
    "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 (:
    (22 votes)
    Default Khan Academy avatar avatar for user
  • piceratops seedling style avatar for user amy charlotte
    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)
    Default Khan Academy avatar avatar for user
  • leaf grey style avatar for user Christopher Smitho (Offline)
    I don't understand the "Insights into Congruence Modulo" diagram. Help?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • leaf red style avatar for user Noble Mushtak
      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)
  • blobby green style avatar for user moin  ali
    what is modulus congruence in simple?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user esmichalak
      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.
      (7 votes)
  • starky ultimate style avatar for user EJ
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
      (5 votes)
  • male robot donald style avatar for user james walmsley
    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).
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user ameramin36
    𝑥^103≡4 𝑚𝑜𝑑 11,solve for x?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • male robot hal style avatar for user Kanga Roo
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • leaf yellow style avatar for user CSA
    -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)
    Default Khan Academy avatar avatar for user
  • duskpin ultimate style avatar for user Vardaan S.
    Would saying that 6 mod 5 = 11 mod 5 be the same thing as saying 6 ≡ 11 (mod 5)?
    (1 vote)
    Default Khan Academy avatar avatar for user