Modulo math is arithmetic on a circle. Count 0, 1, 2 and so on up to n - 1, and the next step brings you back to 0. A clock does this with n = 12, and a byte counter does it with n = 256. I'll start with the circle picture, then give the formal definition with two examples. After that we'll look at negative numbers, which different programming languages treat differently, and at where modulo appears in communication systems.

• What does modulo n mean ?
• Formal Definition
• What happens with negative numbers and in code ?
• Where is modulo used in communication engineering ?

What does modulo n mean ?

Ordinary counting runs along a line and never repeats. Many engineering counters must stay inside a fixed range, so they repeat instead. The pictures below show that repetition as steps on a circle with n positions.

Figure 1 shows the general case. The circle is cut into n sectors, labelled 0, 1, 2 and so on up to n - 1. The dots at the lower left stand for the labels that are not written out.

Figure 1. Modulo n as a circle. The n possible results, 0 to n - 1, sit next to each other, and n - 1 is followed by 0.

Figure 2 adds the counting rule. Each green arrow is one step of +1, and every step moves one sector clockwise. The arrow at the top is the one that matters. It takes n - 1 to 0, so the count never reaches n.

Figure 2. Adding 1 moves one sector clockwise. Adding 1 to n - 1 wraps around to 0.

• No result is ever n or larger : the circle has only the sectors 0 to n - 1, so every result of modulo n lies in that range.
• Adding k means k steps : adding k to a position moves k sectors clockwise. Adding n moves a full turn and lands on the same sector.

Figure 3 draws the same circle for n = 8. The labels run from 0 to 7, and eight +1 arrows go once around the circle.

Figure 3. Modulo 8. Counting 0, 1, ..., 7 and then 0 again is what a 3-bit counter does.

• 7 + 1 = 0 in modulo 8 : the arrow from 7 lands on 0, not on 8.
• 5 + 6 = 3 in modulo 8 : six steps from 5 pass 6, 7, 0, 1, 2 and stop at 3. In ordinary numbers, 11 = 1 x 8 + 3.
• Modulo 2^k needs no extra logic in hardware : a k-bit register that overflows drops the carry, and that is the same as counting modulo 2^k.

Figure 4 shows the smallest useful case, n = 2. The circle has only two halves, 0 and 1. The arrow on the right takes 0 to 1, and the arrow on the left takes 1 back to 0.

Figure 4. Modulo 2. Adding 1 always flips the value, which is how a single bit behaves.

• 1 + 1 = 0 in modulo 2 : so addition modulo 2 is the XOR operation. The sum of two bits keeps no carry.
• Even and odd : a mod 2 is 0 for an even number and 1 for an odd number. Modulo 2 only remembers the parity.

Formal Definition

The circle is a good picture, but a calculation needs a formula. The formula comes from integer division. When a is divided by n, the result is a quotient q and a remainder r, and modulo keeps only r.

Figure 5 writes a = qn + r and marks which part modulo keeps. The quotient q counts full turns around the circle, and the remainder r is the sector where the count stops.

Figure 5. The definition of a mod n. The remainder r of a = qn + r is the result, and the quotient q is dropped.

• The remainder must satisfy 0 <= r < n : this condition is not written in Figure 5, but it is part of the definition. Without it, 15 = 1 x 6 + 9 would also fit the form a = qn + r.
• The quotient counts full turns : q is the number of times the count passes 0 on the circle. Modulo math does not need it.
• n must be a positive integer : in this page n is at least 2. Modulo 1 is always 0 and is not useful.

Example 01

Let's apply the definition to one number first. The steps are to find the largest multiple of n that fits into a, and then to keep what is left over.

Let's suppose a = 15, n = 6. We can express this according to the definition as follows.

15 = 2 x 6 + 3 ==> q = 2, r = 3

This is represented as follows in modular form.

15 mod 6 = 3

Example 02

The next example keeps n = 6 fixed and lets a run from 0 upward. The table shows the quotient and the remainder for each value, so you can see the circle of Figure 1 as a repeating pattern.

• r repeats with period 6 : the column r runs 0, 1, 2, 3, 4, 5 and starts again at 0 whenever a reaches a multiple of 6.
• q increases by 1 at each wrap : q changes from 0 to 1 at a = 6, to 2 at a = 12 and to 3 at a = 18.
• a is always 6q + r : for example, 20 = 6 x 3 + 2, so 20 mod 6 = 2.

What happens with negative numbers and in code ?

For a negative number the definition still works, but programming languages do not all follow it. The difference is a common source of bugs when an index or a phase counter goes below zero. So let's check one negative case by hand and then in code.

Take a = -7 and n = 3. The definition asks for 0 <= r < 3, so -7 = (-3) x 3 + 2. The quotient is -3, and -7 mod 3 = 2. On the circle, this is seven steps counter-clockwise from 0: 2, 1, 0, 2, 1, 0, 2. The C and Java operator % gives -1 instead, because it rounds the quotient toward zero, to -2. Then -7 = (-2) x 3 + (-1), and the remainder takes the sign of a.

Each language has its own rule, so check it before you use a negative operand. In Python, -7 % 3 is 2, because the quotient is rounded down. In Matlab and Octave, mod(-7, 3) is 2 and rem(-7, 3) is -1. In C, the safe way to get the mathematical result is ((a % n) + n) % n.

• Mathematical modulo is never negative : for n > 0 the result always lies between 0 and n - 1.
• A remainder operator can be negative : C, C++, Java and the Matlab rem function return a result with the sign of a.
• Both agree for a >= 0 : the difference only appears when a is negative, which is why the bug is easy to miss in testing.

Where is modulo used in communication engineering ?

Modulo is everywhere in a communication system, because counters, indexes and bits all live in a fixed range. Here are the uses you will meet most often. Each one is the circle of Figure 1 with a specific n.

The most common case is n = 2. Channel coding, CRC calculation and scrambling all add bits modulo 2, which is the XOR of Figure 4. The pseudo-random sequences used for scrambling and reference signals are generated in the same way. The second case is a counter that wraps. A 10-bit frame number counts 0 to 1023 and then returns to 0, so the next frame after 1023 is (1023 + 1) mod 1024 = 0. The third case is an index into a circular buffer or a cyclic shift, where position (k + m) mod N replaces a position that would run past the end.

Modulo also has an algebra of its own. Two numbers with the same remainder behave the same way in modulo n arithmetic. The Modular Equivalence page defines this idea and lists the rules for adding and multiplying such numbers.

• Addition modulo 2 is XOR : binary codes, CRCs and scramblers all rely on it.
• Wrap-around counters are modulo counters : to compare two values of such a counter, compute the difference modulo n rather than the plain difference.
• Cyclic shifts use modulo indexing : shifting a length N sequence by m moves element k to position (k + m) mod N.