Make learning comfortable

Visual experienceAnimationRead-aloud speedChanging style, motion, or reading speed keeps your current question, answers, homework, and saved progress. The school band still chooses your task layout. Saved to your learner profile across devices. All lessons and help stay available.

Introduction to Number Theory / LEVEL 3 · DIFFICULTY 3/5

Congruences

Solve problems using remainders.

3 stages · 24 practice problems · two 6-question assessment forms

Choose an island to read its lesson.

MINI QUEST NT 3.1Cycles of Units DigitsRead the lesson
MINI QUEST NT 3.2Linear CongruencesRead the lesson
MINI QUEST NT 3.3Combining Remainder ConditionsRead the lesson
LEVEL CHECKCastle challenge
6 questions across this level.
Sign in for the level check →

STAGE NT 3.1 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Cycles of Units Digits

Useful preparation: Computing with Remainders

Goal: Understand and apply cycles of units digits.

Before you begin: Computing with Remainders

Understand the idea

Repeated powers often revisit the same remainder. For a fixed last digit, multiplying once more determines the next last digit, so a repeated state creates a cycle.

\displaystyle 3^{1}

\displaystyle 3^{2}

\displaystyle 3^{3}

\displaystyle 3^{4} \equiv 3

,9,7,1 (mod 10)

Choose and carry out a method

List successive powers modulo ten until the cycle closes. Reduce the exponent by the cycle length and match the correct position.

Check the reasoning

A remainder of zero refers to the last position of a cycle that begins at exponent one. Check a small exponent to avoid an index shift.

WORKED EXAMPLE 1

What is the units digit of $\displaystyle 3^{10}$ ?

Powers of 3 have units digits cycling through 3, 9, 7, 1.
$\displaystyle 10 = 4 \cdot 2 + 2$ ; a zero remainder selects the fourth entry, otherwise use the remainder as the entry number.
The units digit is 9; full groups of four powers repeat.

WORKED EXAMPLE 2

What is the units digit of $\displaystyle 3^{13}$ ?

Powers of 3 have units digits cycling through 3, 9, 7, 1.
$\displaystyle 13 = 4 \cdot 3 + 1$ ; a zero remainder selects the fourth entry, otherwise use the remainder as the entry number.
The units digit is 3; full groups of four powers repeat.

Common pitfalls

Possible mix-up: Exponent remainder zero means units digit zero.

It means use the last entry of the power cycle.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Why can a units-digit calculation ignore all higher decimal digits?

Preview the eight practice prompts

Problem 1
What is the units digit of $\displaystyle 3^{19}$ ?
Practise this exact problem →
Problem 2
What is the units digit of $\displaystyle 3^{22}$ ?
Practise this exact problem →
Problem 3
What is the units digit of $\displaystyle 3^{25}$ ?
Practise this exact problem →
Problem 4
What is the units digit of $\displaystyle 3^{28}$ ?
Practise this exact problem →
Problem 5
What is the units digit of $\displaystyle 3^{31}$ ?
Practise this exact problem →
Problem 6
What is the units digit of $\displaystyle 3^{34}$ ?
Practise this exact problem →
Problem 7New context
A branching design triples its count in each of 37 steps, starting with one piece. What is the units digit of the final count?
Practise this exact problem →
Problem 8New context
A branching design triples its count in each of 40 steps, starting with one piece. What is the units digit of the final count?
Practise this exact problem →

Open stage NT 3.1 in the student workspace →

STAGE NT 3.2 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Linear Congruences

Useful preparation: Cycles of Units Digits

Goal: Understand and apply linear congruences.

Before you begin: Cycles of Units Digits

Understand the idea

Solving $\displaystyle ax \equiv b$ modulo m asks which residue classes give the desired remainder. A unique class exists when a and m are coprime, because multiplication by a permutes all residues.

\displaystyle ax \equiv b

(mod m),

\displaystyle \operatorname{gcd}\, \left(a, m\right) = 1

Choose and carry out a method

Find an inverse of a modulo m or test the finite residue list. Multiply the target by the inverse and reduce the result to 0 through $\displaystyle m - 1$ .

Check the reasoning

Substitute into the original congruence. Ordinary fraction division cannot replace a modular inverse.

WORKED EXAMPLE 1

Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 6$ (mod 9).

Solve the congruence using an inverse, or test numbers differing by the modulus.
Since 9 is odd, 2 is invertible modulo 9. Here $\displaystyle 2 \cdot 3 = 6$ has remainder 6.
The unique solution between 0 and 8 is 3.

WORKED EXAMPLE 2

Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 8$ (mod 11).

Solve the congruence using an inverse, or test numbers differing by the modulus.
Since 11 is odd, 2 is invertible modulo 11. Here $\displaystyle 2 \cdot 4 = 8$ has remainder 8.
The unique solution between 0 and 10 is 4.

Common pitfalls

Possible mix-up: Divide both sides as ordinary fractions.

Use an integer inverse modulo m, when one exists.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

What changes when the coefficient and modulus share a common factor?

Preview the eight practice prompts

Problem 1
Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 12$ (mod 15).
Practise this exact problem →
Problem 2
Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 14$ (mod 17).
Practise this exact problem →
Problem 3
Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 16$ (mod 19).
Practise this exact problem →
Problem 4
Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 18$ (mod 21).
Practise this exact problem →
Problem 5
Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 20$ (mod 23).
Practise this exact problem →
Problem 6
Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 22$ (mod 25).
Practise this exact problem →
Problem 7New context
A machine moves two positions per step on a 27-position dial. Starting at zero, how many steps first land it at position 24?
Practise this exact problem →
Problem 8New context
A machine moves two positions per step on a 29-position dial. Starting at zero, how many steps first land it at position 26?
Practise this exact problem →

Open stage NT 3.2 in the student workspace →

STAGE NT 3.3 · 8 PRACTICE PROBLEMS · 2 NEW-CONTEXT APPLICATIONS

Combining Remainder Conditions

Useful preparation: Linear Congruences

Goal: Understand and apply combining remainder conditions.

Before you begin: Linear Congruences

Understand the idea

Two congruences describe overlapping arithmetic progressions. For coprime moduli, exactly one residue class modulo their product meets both conditions.

\displaystyle x \equiv r

(mod m),

\displaystyle x \equiv s

(mod n)

Choose and carry out a method

List numbers satisfying one condition, or write $\displaystyle x = r$ +km and use the other to determine k. Reduce to the least nonnegative solution.

Check the reasoning

Check both remainders. Adding the product of the moduli produces more solutions but not the least one.

WORKED EXAMPLE 1

Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 4) and $\displaystyle x \equiv 1$ (mod 5).

Numbers satisfying the first condition form an arithmetic progression.
Test 2, 6, 10, … in the second condition. The first match is 6.
The moduli are consecutive and coprime, so the pattern repeats every 20 indices.

WORKED EXAMPLE 2

Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 5) and $\displaystyle x \equiv 1$ (mod 6).

Numbers satisfying the first condition form an arithmetic progression.
Test 2, 7, 12, … in the second condition. The first match is 7.
The moduli are consecutive and coprime, so the pattern repeats every 30 indices.

Common pitfalls

Possible mix-up: Add the two remainders to obtain x.

Both conditions must hold simultaneously; addition alone does not enforce them.

Possible mix-up: A correct numerical answer alone explains the method.

State the governing relationship and check the conditions described above.

Explain it to yourself

Why does adding mn preserve both remainder conditions?

Preview the eight practice prompts

Problem 1
Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 7) and $\displaystyle x \equiv 1$ (mod 8).
Practise this exact problem →
Problem 2
Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 8) and $\displaystyle x \equiv 1$ (mod 9).
Practise this exact problem →
Problem 3
Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 9) and $\displaystyle x \equiv 1$ (mod 10).
Practise this exact problem →
Problem 4
Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 10) and $\displaystyle x \equiv 1$ (mod 11).
Practise this exact problem →
Problem 5
Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 11) and $\displaystyle x \equiv 1$ (mod 12).
Practise this exact problem →
Problem 6
Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 12) and $\displaystyle x \equiv 1$ (mod 13).
Practise this exact problem →
Problem 7New context
A repeating marker leaves remainder 2 when its index is divided by 13, and remainder 1 when divided by 14. What is the first nonnegative index satisfying both rules?
Practise this exact problem →
Problem 8New context
A repeating marker leaves remainder 2 when its index is divided by 14, and remainder 1 when divided by 15. What is the first nonnegative index satisfying both rules?
Practise this exact problem →

Open stage NT 3.3 in the student workspace →

Browse another level →

Congruences

Cycles of Units Digits

Understand the idea

Choose and carry out a method

Check the reasoning

What is the units digit of 310\displaystyle 3^{10}310?

What is the units digit of 313\displaystyle 3^{13}313?

Common pitfalls

Explain it to yourself

Linear Congruences

Understand the idea

Choose and carry out a method

Check the reasoning

Find the least nonnegative integer x satisfying 2 x≡6\displaystyle 2\, x \equiv 62x≡6 (mod 9).

Find the least nonnegative integer x satisfying 2 x≡8\displaystyle 2\, x \equiv 82x≡8 (mod 11).

Common pitfalls

Explain it to yourself

Combining Remainder Conditions

Understand the idea

Choose and carry out a method

Check the reasoning

Find the smallest nonnegative x with x≡2\displaystyle x \equiv 2x≡2 (mod 4) and x≡1\displaystyle x \equiv 1x≡1 (mod 5).

Find the smallest nonnegative x with x≡2\displaystyle x \equiv 2x≡2 (mod 5) and x≡1\displaystyle x \equiv 1x≡1 (mod 6).

Common pitfalls

Explain it to yourself

What is the units digit of $\displaystyle 3^{10}$ ?

What is the units digit of $\displaystyle 3^{13}$ ?

Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 6$ (mod 9).

Find the least nonnegative integer x satisfying $\displaystyle 2\, x \equiv 8$ (mod 11).

Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 4) and $\displaystyle x \equiv 1$ (mod 5).

Find the smallest nonnegative x with $\displaystyle x \equiv 2$ (mod 5) and $\displaystyle x \equiv 1$ (mod 6).