Chapter

Congruences and Remainders

Residue classes, linear congruences, compatible remainders, and olympiad-style remainder arguments.

Back to Course Practice Ladders
Theory Examples Practice Ladders

Theory

1. Residue Classes

Modulo \(m\), every integer belongs to exactly one of the classes

\[ 0,1,2,\ldots,m-1. \]

For example, modulo \(5\), the integers split into five residue classes. The number \(23\) belongs to class \(3\), because \(23\equiv3\pmod5\).

2. Congruence as a Tool

The statement

\[ a\equiv b\pmod m \]

means that \(a-b\) is divisible by \(m\). This turns questions about large numbers into questions about small remainders.

3. Solving Linear Congruences

A congruence such as

\[ ax\equiv b\pmod m \]

is called a linear congruence. If \(\gcd(a,m)=1\), then \(a\) has an inverse modulo \(m\), and the congruence has exactly one solution modulo \(m\).

Example:

\[ 3x\equiv5\pmod7. \]

Since \(3\cdot5\equiv1\pmod7\), multiply both sides by \(5\):

\[ x\equiv25\equiv4\pmod7. \]

4. When Division Is Dangerous

In ordinary equations, we often divide both sides. In congruences, division is allowed only when the divisor is invertible modulo \(m\). For example,

\[ 2x\equiv2\pmod6 \]

cannot simply be divided by \(2\) to get \(x\equiv1\pmod6\). In fact, the solutions are

\[ x\equiv1,4\pmod6. \]

5. Compatible Remainders

Sometimes a number must satisfy several remainder conditions:

\[ n\equiv a\pmod m,\qquad n\equiv b\pmod k. \]

When \(m\) and \(k\) are small, we can list one residue class and test it in the other condition. This prepares for the Chinese Remainder Theorem later.

6. Remainder Arguments in Olympiad Problems

Remainders are useful for proving that something is impossible, finding the form of a number, or reducing many cases to a few. A good habit is to ask:

  • Which modulus makes the expression simple?
  • Which remainders are possible?
  • Can a common divisor, square, or power force a contradiction?

Examples

Example 1. Residue Class

This example shows how a standard residue identifies the residue class of an integer modulo a fixed number.

Problem. Find the residue class of \(94\) modulo \(9\).
Solution. Since \(94=9\cdot10+4\), we have \(94\equiv4\pmod9\).

Example 2. Negative Residue

This example reminds students that negative numbers also have standard residues between 0 and m-1.

Problem. Write \(-17\) as a standard residue modulo \(6\).
Solution. \(-17+18=1\), so \(-17\equiv1\pmod6\).

Example 3. Equivalent Congruences

This example connects congruence notation with the divisibility condition behind it.

Problem. Explain why \(a\equiv b\pmod m\) is equivalent to \(m\mid a-b\).
Solution. If \(a=mq+r\) and \(b=mk+r\), then \(a-b=m(q-k)\), so \(m\mid a-b\). Conversely, if \(m\mid a-b\), then \(a\) and \(b\) differ by a multiple of \(m\), so they have the same remainder modulo \(m\).

Example 4. Solve a Simple Congruence

This example shows how to solve a linear congruence by using an inverse modulo m.

Problem. Solve \(4x\equiv3\pmod7\).
Solution. Since \(4\cdot2=8\equiv1\pmod7\), multiply both sides by \(2\). Then \(x\equiv6\pmod7\).

Example 5. Two Solutions

This example shows how to solve a linear congruence by using an inverse modulo m.

Problem. Solve \(2x\equiv4\pmod6\).
Solution. Testing residues modulo \(6\), \(x=2\) and \(x=5\) work. Thus \(x\equiv2,5\pmod6\). Equivalently, after dividing by \(2\), we get \(x\equiv2\pmod3\), which gives residues \(2\) and \(5\) modulo \(6\).

Example 6. Compatible Remainders I

This example develops the habit of listing one residue class and checking the second condition.

Problem. Find the smallest positive integer \(n\) such that \(n\equiv2\pmod3\) and \(n\equiv1\pmod5\).
Solution. The numbers \(1\pmod5\) are \(1,6,11,16,\ldots\). Checking modulo \(3\), we get \(1,0,2,1,\ldots\). The first suitable number is \(11\).

Example 7. Polynomial Residue

This example shows how reducing the variable first makes polynomial remainders manageable.

Problem. If \(n\equiv5\pmod8\), find \(n^2+3n+1\pmod8\).
Solution. \(n^2+3n+1\equiv5^2+3\cdot5+1=25+15+1=41\equiv1\pmod8\).

Example 8. Congruent Squares

This example shows how a congruence identity can be proved by multiplying congruent quantities.

Problem. Prove that if \(a\equiv b\pmod m\), then \(a^2\equiv b^2\pmod m\).
Solution. Since \(a\equiv b\pmod m\), multiplying both sides by the congruent quantities gives \(a\cdot a\equiv b\cdot b\pmod m\). Hence \(a^2\equiv b^2\pmod m\).

Problems

Problems

No published problems are available yet.

Ladders

No published ladders were found.
Previous Chapter
Next Chapter