Exercise · ZW-COMPLETE-RESIDUE-SYSTEM-009 · ★★★ Advanced
Prove that if \(\gcd(a,7)=1\) and \(\{r_1,\dots,r_7\}\) is complete modulo \(7\), then \(\{ar_1,\dots,ar_7\}\) is also complete. State the key idea.
Choose one option.
A The key idea is that \(a\) is invertible modulo \(7\), so \(ar_i\equiv ar_j\) implies \(r_i\equiv r_j\) B The key idea is that the product of two residues is always a residue C The key idea is that \(a\) must be greater than \(7\) D The key idea is that the sum of the \(r_i\) is a multiple of \(7\) Show answer A. The key idea is that \(a\) is invertible modulo \(7\), so \(ar_i\equiv ar_j\) implies \(r_i\equiv r_j\)← Back to the question
Explanation If \(\gcd(a,7)=1\), \(a\) has an inverse modulo \(7\), which allows cancelling \(a\) in the congruence. Cancellation does not require \(a\) to be large, nor the sum to have special properties.
A complete residue system modulo \(m\) is a set of \(m\) integers that contains exactly one representative from each congruence class modulo \(m\).
\[\{r_1,\dots,r_m\}\ \text{with}\ r_i\not\equiv r_j\ (\bmod\ m)\ \forall i\neq j\]
More practice problems: complete residue system ZW-COMPLETE-RESIDUE-SYSTEM-001 How many elements must a complete residue system modulo 7 have?ZW-COMPLETE-RESIDUE-SYSTEM-002 Which of these sets is a complete residue system modulo 5?ZW-COMPLETE-RESIDUE-SYSTEM-003 How many congruence classes are there modulo 9?ZW-COMPLETE-RESIDUE-SYSTEM-004 If \0,1,2,3\ is complete modulo 4, what is the remainder of 7 divided by 4?ZW-COMPLETE-RESIDUE-SYSTEM-005 Which of these integers belongs to the class of 2 modulo 6?ZW-COMPLETE-RESIDUE-SYSTEM-006 Determine whether \0,1,7,3,4,5,6\ is a complete residue system modulo 7 and explain why.ZW-COMPLETE-RESIDUE-SYSTEM-007 If \1,2,3,4,5,6\ is complete modulo 6, which of these sets is also complete modulo 6?ZW-COMPLETE-RESIDUE-SYSTEM-008 Let m=8 and consider \1,3,5,7\ as a set of residues. How many integers are needed to complete a com…