Exercise · ZW-QUADRATIC-RESIDUE-010 · ★★★ Advanced
Let \(p = 13\), \(a = 4\) and \(b = 9\) be quadratic residues modulo 13. Prove that \(ab\) is also one and find a square root of \(ab\) modulo 13.
Choose one option.
A \(ab \equiv 4\), and 4 is a residue with root 2 B \(ab \equiv 10\) and \(6^2 \equiv 10 \pmod{13}\), so 6 is a square root of ab C \(ab \equiv 10\), which does not appear among \(1^2,\dots,6^2\), so it is not a residue D \(ab \equiv 10\), but 10 is not a residue because it is even Show answer B. \(ab \equiv 10\) and \(6^2 \equiv 10 \pmod{13}\), so 6 is a square root of ab← Back to the question
Explanation Since \(4 = 2^2\) and \(9 = 3^2\), \(ab = (2\cdot 3)^2 = 36 \equiv 10 \pmod{13}\) and \(6^2 \equiv 10\), so \(ab\) is a residue with root 6.
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