Chapter

Modular Arithmetic

Remainders, congruences, arithmetic modulo m, power cycles, and modular contradiction.

Back to Course Practice Ladders
Theory Examples Practice Ladders

Theory

1. Remainders

When an integer \(a\) is divided by a positive integer \(m\), we can write

\[ a=mq+r,\qquad 0\le r

The number \(r\) is the remainder. Modular arithmetic is a way to work with remainders without carrying the full number.

2. Congruence

We write

\[ a\equiv b\pmod m \]

if \(a\) and \(b\) have the same remainder when divided by \(m\). Equivalently,

\[ m\mid a-b. \]

For example, \(17\equiv 2\pmod 5\), because \(17-2=15\) is divisible by \(5\).

3. Arithmetic with Congruences

If

\[ a\equiv b\pmod m,\qquad c\equiv d\pmod m, \]

then

\[ a+c\equiv b+d\pmod m, \]

\[ ac\equiv bd\pmod m. \]

This means we can add, subtract, and multiply remainders.

4. Powers and Cycles

Powers often repeat modulo \(m\). For example, modulo \(10\),

\[ 2^1\equiv2,\quad 2^2\equiv4,\quad 2^3\equiv8,\quad 2^4\equiv6,\quad 2^5\equiv2. \]

So the last digit of powers of \(2\) repeats with cycle length \(4\): \(2,4,8,6\).

5. Modular Contradiction

To prove that an equation has no integer solutions, look at both sides modulo a small number. If the possible remainders cannot match, the equation is impossible.

Example: no integer square is congruent to \(2\pmod 4\), because squares are only \(0\) or \(1\pmod 4\).

6. Divisibility Tests as Modular Arithmetic

Digit rules come from modular arithmetic. Since

\[ 10\equiv1\pmod 9, \]

every power of \(10\) is congruent to \(1\pmod 9\). Therefore a number has the same remainder modulo \(9\) as the sum of its digits.

Examples

Example 1. Remainder of a Number

This example connects ordinary division with remainders: write the number as \(mq+r\) with \(0\le r

Problem. Find the remainder when \(137\) is divided by \(5\).
Solution. Since \(137=5\cdot27+2\), the remainder is \(2\).

Example 2. Write a Congruence

This example shows how congruence notation records the remainder after division by the modulus.

Problem. Complete the congruence: \(83\equiv \square \pmod 7\), where the box is one of \(0,1,2,3,4,5,6\).
Solution. \(83=7\cdot11+6\), so \(83\equiv6\pmod7\).

Example 3. Add Remainders

This example shows that congruences let us add remainders first and reduce only at the end.

Problem. If \(a\equiv4\pmod9\) and \(b\equiv7\pmod9\), find \(a+b\pmod9\).
Solution. \(a+b\equiv4+7=11\equiv2\pmod9\).

Example 4. Last Digit of a Power

This example shows how powers repeat in cycles modulo \(10\), which controls the last digit.

Problem. Find the last digit of \(2^{25}\).
Solution. The cycle length is \(4\). Since \(25\equiv1\pmod4\), \(2^{25}\) has the same last digit as \(2^1\), which is \(2\).

Example 5. Power Modulo Seven

This example shows how to use a power cycle modulo \(7\) instead of computing a huge power.

Problem. Find the remainder of \(3^{20}\) when divided by \(7\).
Solution. Modulo \(7\): \(3^1\equiv3\), \(3^2\equiv2\), \(3^3\equiv6\), \(3^4\equiv4\), \(3^5\equiv5\), \(3^6\equiv1\). Since \(20\equiv2\pmod6\), \(3^{20}\equiv3^2\equiv2\pmod7\).

Example 6. Squares Modulo Four

This example shows a standard modular fact: every square has only certain possible residues modulo \(4\).

Problem. Prove that every integer square is congruent to \(0\) or \(1\pmod4\).
Solution. If \(n=2k\), then \(n^2=4k^2\equiv0\pmod4\). If \(n=2k+1\), then \(n^2=4k^2+4k+1\equiv1\pmod4\).

Example 7. No Square of This Form

This example shows how modular arithmetic can prove that an equation has no integer solutions.

Problem. Prove that the equation \(x^2=4y+2\) has no integer solutions.
Solution. The right side satisfies \(4y+2\equiv2\pmod4\). But a square is only \(0\) or \(1\pmod4\). Contradiction.

Example 8. Always Divisible by Five

This example shows how checking residues modulo \(5\) proves a divisibility statement for every integer.

Problem. Prove that \(5\mid n^5-n\) for every integer \(n\).
Solution. It is enough to check \(n\equiv0,1,2,3,4\pmod5\). We get \(0^5-0=0\), \(1^5-1=0\), \(2^5-2=30\), \(3^5-3=240\), \(4^5-4=1020\), all divisible by \(5\). Therefore \(5\mid n^5-n\).

Problems

Problems

No published problems are available yet.

Ladders

No published ladders were found.
Previous Chapter
Next Chapter