Exercise · ZW-QUADRATIC-RESIDUE-006 · ★★☆ Intermediate
Compute the nonzero quadratic residues modulo 9 and state how many there are.
Choose one option.
Show answer
- B. {1, 4, 7}, three residues
Explanation
The squares of 1 through 8 modulo 9 are 1, 4, 0, 7, 7, 0, 4, 1, so the nonzero ones are {1, 4, 7}. The option including 8 fails because 8 is not a square modulo 9.
Review the concept: Quadratic residue
A quadratic residue modulo n is an integer a with gcd(a,n)=1 such that the congruence x² ≡ a (mod n) has a solution. If it has no solution, a is a quadratic nonresidue.
\[x^2 \equiv a \pmod{p}\]
More practice problems: quadratic residue
- ZW-QUADRATIC-RESIDUE-001 Which of these integers is a quadratic residue modulo 7?
- ZW-QUADRATIC-RESIDUE-002 State the definition of a quadratic residue modulo n for an integer a with gcd(a,n)=1.
- ZW-QUADRATIC-RESIDUE-003 What is the set of nonzero quadratic residues modulo 5?
- ZW-QUADRATIC-RESIDUE-004 Give the number of nonzero quadratic residues modulo an odd prime p.
- ZW-QUADRATIC-RESIDUE-005 Which of these residues is a quadratic nonresidue modulo 11?
- ZW-QUADRATIC-RESIDUE-007 Decide whether 2 is a quadratic residue modulo 17 by computing the squares of the residues from 1 t…
- ZW-QUADRATIC-RESIDUE-008 Solve x² ≡ 4 (mod 15) and count how many solutions exist modulo 15.
- ZW-QUADRATIC-RESIDUE-009 Determine whether 3 is a quadratic residue modulo 13 by testing the squares of 1 through 6.