Computing in Z/nZ
Residue classes modulo n, addition and multiplication, invertible elements and zero divisors, the inverse by the extended Euclidean algorithm, and solving ax ≡ b modulo n.
- 26 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Z/nZ: what is it?
Show the answer
The set of remainders of division by n, from 0 to n − 1, where you add and multiply keeping only the remainder.
In Z/12Z, 9 + 5 is 2: 14 has remainder 2. All classical cryptography computes in such a set, with n = 26 for the alphabet.
Which of these elements of Z/10Z has no inverse?
5379
Show the answer
5GCD(5, 10) = 5, so 5 is not invertible, even though it is prime: 5 × 2 = 10 ≡ 0. What matters is the GCD with n, not whether the element is prime. The invertibles of Z/10Z are 1, 3, 7 and 9.
In Z/nZ, an element a is invertible if and only if ….
Show the answer
In Z/nZ, an element a is invertible if and only if GCD(a, n) = 1.
If the GCD is some d > 1, every product a × x is a multiple of d, so it can never equal 1 modulo an n that is a multiple of d.
Congruence modulo n: what is it?
Show the answer
The relation between two integers that have the same remainder when divided by n, that is, whose difference is a multiple of n.
38 ≡ 12 (mod 26)because 38 − 12 = 26. Two congruent numbers are the same class of Z/nZ: either can replace the other in a computation.