Quadratic Residues
Squares modulo a prime.
Key idea
Squares modulo a prime.
In depth
a is a quadratic residue mod p if x² ≡ a (mod p) has a solution. Exactly half of the non-zero residues are quadratic residues. Euler’s criterion: a is a QR iff a^((p−1)/2) ≡ 1.
Worked example
Mod 7, the squares are 1, 2, 4, so QRs are {1, 2, 4}.
Real-world uses
- Solving square-root problems in modular arithmetic for codes and elliptic curve cryptography
Common mistake
Forgetting that 0 is a special case.
How to learn this
- Read the key idea and say it in your own words.
- Work through the worked example, then try a similar problem.
- Use the interactive lesson’s visual and mini-quiz to check the pattern.
Frequently asked questions
What is Quadratic Residues?
Squares modulo a prime. It is a topic at the expert level in Discrete Math & Number Theory.
Where is Quadratic Residues used in real life?
Real-world examples: Solving square-root problems in modular arithmetic for codes and elliptic curve cryptography.
What should I learn before Quadratic Residues?
Make sure you are comfortable with Wilson’s Theorem, the previous topic in Discrete Math & Number Theory.
What is a common mistake with Quadratic Residues?
Forgetting that 0 is a special case.
How can I practise Quadratic Residues?
Open the interactive lesson, play with the visual, then answer the three-question mini-quiz. Getting two right marks the topic complete.
What comes after Quadratic Residues?
Move on to Legendre Symbol and Reciprocity next.
Related expert topics in Discrete Math & Number Theory
- Strong Induction – Assume all earlier cases to prove the next.
- Well-Ordering Principle – Every nonempty set of positive integers has a least element.
- Partial Orders – Reflexive, antisymmetric, transitive relations.
- Cardinality of Sets – Comparing sizes of infinite sets.
- Countable and Uncountable Sets – ℕ and ℚ are countable; ℝ is not.
- Cantor’s Diagonal Argument – Proof that real numbers are uncountable.