Modular Arithmetic

Modular arithmetic keeps track of remainders rather than complete integer values. It is useful when positions repeat: days of the week, numbered slots, repeating patterns and the final digits of powers.

The arithmetic does not claim that different integers are equal. It records that they occupy the same position in a repeating cycle.

On this page

Separate a remainder from a congruence statement

For an integer $a$ and positive integer $m$ , $a\bmod m$ denotes its least non-negative remainder. For example,

17\bmod7=3,\qquad-4\bmod7=3.

The relation $17\equiv-4\pmod7$ says that the difference $17-(-4)=21$ is divisible by 7. Both integers lie in the same residue class. They are not equal as integers.

For the main examples, $m\ge2$ . Modulo 1 there is only one residue class, because every integer has remainder zero. MathWorld’s congruence reference develops the relation and its arithmetic properties.

Understand the entire residue class

The class represented by 3 modulo 7 contains

\ldots,-11,-4,3,10,17,24,\ldots.

Every member has the form $3+7k$ for an integer $k$ . The representative 3 is a convenient label for the whole class, not its only member.

The seven classes represented by $0,1,2,3,4,5,6$ partition the integers: every integer belongs to exactly one class. Adding seven moves to a different integer in the same class.

Successive multiples of 3 modulo 7

The spacing of the nodes is schematic. It shows operation order, not distance between numerical values.

Diagram explanation and exact data

The total after j steps is 3j. Reducing each total modulo 7 produces every residue once before returning to zero after seven steps.

Successive multiples of 3 modulo 7: exact reference data
Step	Total	Residue modulo 7
0	0	0
1	3	3
2	6	6
3	9	2
4	12	5
5	15	1
6	18	4
7	21	0

Add, subtract and multiply after reducing

Modulo 7, both 18 and 25 have remainder 4. Their sum can therefore be reduced using small numbers:

18+25\equiv4+4\equiv1\pmod7.

Their product gives a different result:

18\times25\equiv4\times4\equiv16\equiv2\pmod7.

These rules work because adding or multiplying representatives changes the original result only by a multiple of the modulus. If $a=a’+km$ and $b=b’+\ell m$ , then

ab-a’b’=m(a’\ell+b’k+k\ell m).

The difference is divisible by $m$ . Repeated reduction is therefore exact, not an approximation.

Model a cycle with a stated starting position

Number weekdays Monday 0 through Sunday 6. Thursday is 3. Seventeen days after a Thursday has residue

(3+17)\bmod7=6,

so it is Sunday. Stating the numbering avoids an off-by-one error. “Seventeen days after” does not count the starting Thursday as day one.

Likewise, on a 12-hour clock, $11+5\equiv4\pmod{12}$ . The residue determines the clock face position but does not distinguish morning from afternoon or record how many full cycles passed. Remainder information deliberately discards that information.

Reduce large powers without expanding them

To calculate $3^{100}\bmod7$ , find a short power that returns to 1:

3^2\equiv2,\quad3^3\equiv6,\quad3^6\equiv1\pmod7.

Since $100=6\times16+4$ ,

3^{100}=(3^6)^{16}3^4\equiv1^{16}\times4\equiv4\pmod7.

No enormous decimal integer was needed. For the final digit of $7^{2026}$ , work modulo 10. The residues of successive positive powers repeat $7,9,3,1$ ; exponent 2026 has remainder 2 modulo the period 4, so the final digit is 9.

The modulus and the exponent’s period are different objects. You cannot generally reduce an exponent modulo the original modulus. Although $3\equiv8\pmod5$ , the powers $2^3$ and $2^8$ have different residues modulo 5.

Do not cancel a factor automatically

Ordinary integer equality allows cancellation of any non-zero multiplicative factor. Congruences need a stronger condition. For example,

2\times1\equiv2\times4\pmod6,

because the two products differ by 6. But $1\not\equiv4\pmod6$ . Cancelling 2 while keeping modulus 6 loses information.

Cancellation modulo $m$ is valid when the cancelled factor is coprime to $m$ . Otherwise the modulus must be adjusted, or all possible solutions retained. Congruence in Number Theory explains this through modular inverses and greatest common factors.

Use residues to rule out impossible cases

Every integer is even or odd. If $n=2k$ , then $n^2=4k^2$ has remainder zero modulo 4. If $n=2k+1$ , then

n^2=4k^2+4k+1

has remainder one. Thus an integer square cannot have remainder 2 or 3 modulo 4.

This is a general proof from the two possible parity cases, not merely a list of observed squares. Such a restriction can eliminate an impossible equation before a lengthy search. It is still a necessary condition: having remainder zero or one does not by itself prove that an integer is a square.

Practice questions

Find the least non-negative remainder of $-17$ modulo 5.
Find $8\times9\bmod7$ without multiplying the original numbers first.
Find $2^{10}\bmod3$ and explain the reduction.

Check your answers

It is 3 because $-17=5(-4)+3$ .
Reduce to $1\times2$ , giving remainder 2.
Since $2\equiv-1\pmod3$ , $2^{10}\equiv(-1)^{10}=1\pmod3$ .