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

What is modular arithmetic?

An Introduction to Modular Math

When we divide two integers we will have an equation that looks like the following:
start fraction, A, divided by, B, end fraction, equals, Q, start text, space, r, e, m, a, i, n, d, e, r, space, end text, R
A is the dividend
B is the divisor
Q is the quotient
R is the remainder
Sometimes, we are only interested in what the remainder is when we divide A by B.
For 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, start text, space, m, o, d, space, end text, B, equals, R
We would say this as A modulo B is equal to R. Where B is referred to as the 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, start text, space, m, o, d, space, end text, B we can follow these steps:
  1. Construct this clock for size B
  2. Start at 0 and move around the clock A steps
  3. Wherever we land is our solution.
(If the number is positive we step clockwise, if it's negative we step counter-clockwise.)

Examples

8, start text, space, m, o, d, space, end text, 4, equals, question mark

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 ended up at 0 so 8, start text, space, m, o, d, space, end text, 4, equals, 0.

7, start text, space, m, o, d, space, end text, 2, equals, question mark

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 ended up at 1 so 7, start text, space, m, o, d, space, end text, 2, equals, 1.

minus, 5, start text, space, m, o, d, space, end text, 3, equals, question mark

With a modulus of 3 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.
We ended up at 1 so minus, 5, start text, space, m, o, d, space, end text, 3, equals, 1.

Conclusion

If we have A, start text, space, m, o, d, space, end text, B and we increase A by a multiple of B, we will end up in the same spot, i.e.
A, start text, space, m, o, d, space, end text, B, equals, left parenthesis, A, plus, K, dot, B, right parenthesis, start text, space, m, o, d, space, end text, B for any integer 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.
-5 % 3 = -2.

Congruence Modulo

You may see an expression like:
A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
This says that A is congruent to B modulo C. It is similar to the expressions we used here, but not quite the same.
In the next article we will explain what it means and how it is related to the expressions above.

Want to join the conversation?

  • old spice man green style avatar for user Shane Kays
    Who invented Modular Arithmetic?
    (22 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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.
      (83 votes)
  • blobby green style avatar for user diana
    -17 mod 7

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

    -7 *2 +-3=-17

    why does the site say 4? :(
    (8 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user vijayhm
    What happens if the modulus is negative?
    (13 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user MohsenQaddoura
    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.
    (15 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • starky tree style avatar for user Kiara O'Connell
    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??
    (2 votes)
    Default Khan Academy avatar avatar for user
    • piceratops seed style avatar for user Alex Carrasquillo
      Think about how you divide with positive numbers first. Say you divide 13 by 4. How do we approach this? We find a multiple of 4 that is closest to 13. In this case, 12. The remainder is 1.

      Now let's do the same for the negative case. The problem was -5 mod 3.
      We need to find a multiple of 3 that is as close to -5 as possible, yet still smaller. In this case, that would be -2. 3 * -2 gives you -6, which is 1 smaller than -5. So, our remainder is 1 since -6 + 1 gives you -5.
      (30 votes)
  • aqualine ultimate style avatar for user The Great Narwhal
    Can someone explain the concept of calculating mod with out the circles?
    How would you do 13 mod 10?
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user shaillie.tiwari532st
    how is 3mod10 = 3?? it should be 0..isnt it??
    (5 votes)
    Default Khan Academy avatar avatar for user
  • old spice man green style avatar for user yamauchi.hitoshi
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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)
  • blobby green style avatar for user dbrodersen
    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)
    Default Khan Academy avatar avatar for user
  • aqualine ultimate style avatar for user Denis
    How do divide 4/4 in mod 5 or 3/4. Ex: 4 - 1 = 3
    (2 votes)
    Default Khan Academy avatar avatar for user