NumeriveMATH
CurriculumFamily workspaceStudentMy characterAchievementsContact
← Introduction to Number Theory levels

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.

  1. MINI QUEST NT 3.1Cycles of Units DigitsRead the lesson
  2. MINI QUEST NT 3.2Linear CongruencesRead the lesson
  3. MINI QUEST NT 3.3Combining Remainder ConditionsRead the lesson
  4. 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.

3¹,3²,3³,3⁴ ≡ 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 3^10?

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

9

WORKED EXAMPLE 2

What is the units digit of 3^13?

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

3

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
  1. What is the units digit of 3^19?
  2. What is the units digit of 3^22?
  3. What is the units digit of 3^25?
  4. What is the units digit of 3^28?
  5. What is the units digit of 3^31?
  6. What is the units digit of 3^34?
  7. A branching design triples its count in each of 37 steps, starting with one piece. What is the units digit of the final count? New context
  8. A branching design triples its count in each of 40 steps, starting with one piece. What is the units digit of the final count? New context
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 ax≡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.

ax≡b (mod m), gcd(a,m)=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 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 2x ≡ 6 (mod 9).

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

3

WORKED EXAMPLE 2

Find the least nonnegative integer x satisfying 2x ≡ 8 (mod 11).

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

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
  1. Find the least nonnegative integer x satisfying 2x ≡ 12 (mod 15).
  2. Find the least nonnegative integer x satisfying 2x ≡ 14 (mod 17).
  3. Find the least nonnegative integer x satisfying 2x ≡ 16 (mod 19).
  4. Find the least nonnegative integer x satisfying 2x ≡ 18 (mod 21).
  5. Find the least nonnegative integer x satisfying 2x ≡ 20 (mod 23).
  6. Find the least nonnegative integer x satisfying 2x ≡ 22 (mod 25).
  7. A machine moves two positions per step on a 27-position dial. Starting at zero, how many steps first land it at position 24? New context
  8. A machine moves two positions per step on a 29-position dial. Starting at zero, how many steps first land it at position 26? New context
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.

x≡r (mod m), x≡s (mod n)

Choose and carry out a method

List numbers satisfying one condition, or write 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 x ≡ 2 (mod 4) and x ≡ 1 (mod 5).

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

6

WORKED EXAMPLE 2

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

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

7

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
  1. Find the smallest nonnegative x with x ≡ 2 (mod 7) and x ≡ 1 (mod 8).
  2. Find the smallest nonnegative x with x ≡ 2 (mod 8) and x ≡ 1 (mod 9).
  3. Find the smallest nonnegative x with x ≡ 2 (mod 9) and x ≡ 1 (mod 10).
  4. Find the smallest nonnegative x with x ≡ 2 (mod 10) and x ≡ 1 (mod 11).
  5. Find the smallest nonnegative x with x ≡ 2 (mod 11) and x ≡ 1 (mod 12).
  6. Find the smallest nonnegative x with x ≡ 2 (mod 12) and x ≡ 1 (mod 13).
  7. 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? New context
  8. 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? New context
Open stage NT 3.3 in the student workspace →
Browse another level →