Practice question · Multiple choice
Congruence mod n is an equivalence relation, so it partitions the integers into n residue classes. Why does that structure make it legitimate to add and multiply classes rather than individual numbers?
Hints
- Compute 3 + 5 mod 7, then 10 + 12 mod 7. Both pairs are in the same classes. Same answer?
- Ask what could go wrong if different representatives gave different results.
Show the answer
D. Because the result does not depend on which representative you pick.
Why
The question is whether the answer depends on which representative you picked, and it does not: 3 + 5 ≡ 1 and 10 + 12 ≡ 1 mod 7. That is what turns the residue classes into an arithmetic system in their own right. Not every operation survives, reducing the exponent mod n is not well defined, since 2¹ = 2 and 2⁸ ≡ 4 mod 7.
Practise Modular Arithmetic
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Modular Arithmetic
- Select every operation you may perform on congruences modulo n with no extra conditions.
- A congruence may be divided through by a factor only when that factor is coprime to the modulus.
- Find the last digit of 7 raised to the power 4. (The last digit of a number is that number mod 10.)
- Congruence mod 4 splits the integers into four residue classes. Sort each number into its class.
- The ISBN check digit is chosen so a weighted sum of the digits is divisible by 11. Why does that catch a…