Number theory path · N08

Before this lesson: Modular arithmetic and congruences, Greatest common divisor and Bézout

Your goal: Use representatives without confusing them with the residue classes.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Complete and reduced residue systems: the key idea

A complete residue system modulo n contains exactly one representative from each of the n residue classes. The representatives need not be 0,…,n−1: any n consecutive integers work. A reduced residue system represents only classes coprime to n. If gcd(a,n)=1, multiplication by a permutes all residue classes and also the reduced classes. Prove distinctness by cancellation modulo n; cancellation uses coprimality. Without it, distinct inputs can collapse to the same class.

A worked example

Show that 0,3,6,9,12 is a complete residue system modulo 5.

Their remainders are 0,3,1,4,2, each class exactly once. Alternatively gcd(3,5)=1, so multiplication by 3 permutes the standard system.

Your turn: change one thing

Find the reduced residues modulo 8 in the range 0,…,7.

Try this on paper before opening the explanation.

Compare your reasoning

They are 1,3,5,7: exactly the numbers coprime to 8. Multiplication by 3 maps them to remainders 3,1,7,5.

Pause and check

A trap to avoid: Assuming multiplication permutes all classes when the multiplier is not coprime.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove multiplication by a permutes residues modulo n when gcd(a,n)=1.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

If ax≡ay mod n, then n divides a(x−y). Coprimality allows cancellation, so n divides x−y. Distinct residue classes therefore map to distinct classes. An injective map from a finite set of n classes to itself is surjective, hence a permutation.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. A complete residue system modulo n has how many classes?

Foundation

  1. φ(n) always
  2. 2n
  3. n
  4. n−1
Hint

It represents every remainder once.

Answer and reasoning

n. There are n classes, represented by 0 through n−1.

2. A reduced residue system includes which classes?

Foundation

  1. Only prime representatives
  2. Only zero
  3. Those coprime to n
  4. Only even classes
Hint

Invertibility is the defining condition.

Answer and reasoning

Those coprime to n. A class is reduced when its representatives have gcd 1 with n.

3. Which is a reduced residue system modulo 8?

Core

  1. 0,2,4,6
  2. 1,2,3,4
  3. 2,3,5,7
  4. 1,3,5,7
Hint

Exclude common factors with 8.

Answer and reasoning

1,3,5,7. Exactly the odd classes are coprime to 8.

4. The remainder of 3·4 modulo 5 is what?

Core

  1. 4
  2. 2
  3. 1
  4. 3
Hint

Reduce 12 modulo 5.

Answer and reasoning

2. 12=2·5+2.

5. Multiplication by a permutes classes mod n when what holds?

Stretch

  1. a is even
  2. n divides a
  3. gcd(a,n)=1
  4. a=n
Hint

Cancellation must be valid.

Answer and reasoning

gcd(a,n)=1. Coprimality gives an inverse class and prevents collisions.

6. Why does multiplication by 2 fail to permute residues modulo 6?

Stretch

  1. 0 and 3 both map to 0
  2. 6 is too small
  3. 2 is prime
  4. All classes remain distinct
Hint

Look for a collision.

Answer and reasoning

0 and 3 both map to 0. 2·0≡2·3≡0 mod 6, so the map is not injective.

7. Two integers are in the same residue class mod n when their difference is what?

Foundation

  1. Equal to n only
  2. Less than n always
  3. A multiple of n
  4. Prime
Hint

Use the definition of congruence.

Answer and reasoning

A multiple of n. n divides their difference.

8. Which list is a complete residue system modulo 4?

Core

  1. 0,2,4,6
  2. 1,1,2,3
  3. −1,0,1,2
  4. 0,1,2,4
Hint

Reduce each entry modulo 4.

Answer and reasoning

−1,0,1,2. The remainders are 3,0,1,2, all four classes once.

9. Why do n consecutive integers represent all classes mod n?

Stretch

  1. They are all prime
  2. Their sum is zero
  3. No nonzero difference between them is divisible by n
  4. They are all coprime to n
Hint

Their pairwise differences have absolute value below n.

Answer and reasoning

No nonzero difference between them is divisible by n. The n classes are distinct, so they exhaust the n possible residues.

Choose your next step

Continue to Number theory theorems: Fermat, Euler, Wilson and CRT. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.