Congruences, Cycles, and Remainders

A remainder is a compact description of an integer. Instead of computing a huge number, keep track of how it behaves when divided by a carefully chosen modulus.

What you will learn

• Calculate congruences
• Reduce powers
• Eliminate impossible cases

Keep paper and a pencil nearby. Try each problem before opening a hint, and mark sections reviewed as you work through them.

Congruence preserves the relevant difference

Two integers are congruent modulo $m$ when their difference is divisible by the positive integer $m$. They therefore have the same remainder upon division by $m$. Replacing a number by a congruent smaller number preserves the remainder of any sum, difference, or product. This is why you can reduce intermediate calculations without waiting until the end.

For a final remainder, use the representative from zero through $m-1$. Negative representatives are often useful during calculation, but the answer should obey the question's convention. For example, a residue described as one less than a multiple of $m$ has ordinary remainder $m-1$, not a negative remainder.

Powers can repeat in a short cycle

Begin a power problem by computing a few successive residues. If the same residue returns and multiplication by the base repeats the same process, the sequence cycles. Reduce the exponent by the cycle length, taking care with an exponent that is a multiple of that length. It corresponds to the last position in the cycle when you listed powers starting at one.

Division is more delicate than addition or multiplication. You may cancel a factor modulo $m$ when that factor is relatively prime to $m$. Otherwise cancellation can lose information. To solve a small congruence, testing the residue classes or finding a multiplicative inverse is safer than dividing as though the congruence were an ordinary equation.

Combine remainders with a structured search

A condition such as remainder two modulo five describes the integers $5k+2$. Substitute this form into a second remainder condition to narrow the possible values of $k$. This replaces a search through all integers with a search through one residue class. If the moduli share factors, the two conditions may be incompatible.

Square residues are especially effective for ruling out integer solutions. List the possible residues of an input, square them, and observe which output residues never occur. A contradiction modulo a small number proves impossibility for all integers at once; it is much stronger than checking a few ordinary values and seeing no solution.

See the reasoning unfold

Pause after each step and predict what comes next.

Common mistakes to catch

• Dividing a congruence by a factor that is not invertible.
• Using the wrong entry when an exponent is a multiple of a cycle length.
• Reporting a negative representative as an ordinary nonnegative remainder.

Try with support

Guided practice

Choose a strategy, take a first step, and use the hints when you need direction.

Put it into practice

Independent practice

Work on your own first. If you reveal a solution, work through it and mark it reviewed.

Bring it together

• Reduce sums and products at each step.
• Power cycles require an observed and justified repeating rule.
• Combine residue classes to narrow an integer search.