Quadratic Residue Checker
Check if a number \\( n \\) is a quadratic residue modulo a prime \\( p \\).
Formulas Used
A number \\( n \\) is a quadratic residue modulo a prime \\( p \\) if there exists an integer \\( x \\) such that \\( x^2 \equiv n \pmod{p} \\). We use the Legendre symbol and Euler’s criterion to check this.
- Legendre Symbol:
\\[ \left( \frac{n}{p} \right) = n^{(p-1)/2} \pmod{p} \\]
Where:
- \\( n \\): Number to check
- \\( p \\): Prime modulus
- \\( \left( \frac{n}{p} \right) = 1 \\): \\( n \\) is a quadratic residue
- \\( \left( \frac{n}{p} \right) = -1 \\): \\( n \\) is not a quadratic residue
- \\( \left( \frac{n}{p} \right) = 0 \\): \\( n \equiv 0 \pmod{p} \\)
- Euler’s Criterion:
The value of \\( n^{(p-1)/2} \pmod{p} \\) determines the quadratic residue status.
Example Calculations
Example 1: \\( n = 2 \\), \\( p = 7 \\)
Inputs: Number = 2, Modulus = 7
Calculations:
- Legendre Symbol: \\[ \left( \frac{2}{7} \right) = 2^{(7-1)/2} = 2^3 = 8 \equiv 1 \pmod{7} \\]
- Result: \\( 2 \\) is a quadratic residue modulo \\( 7 \\)
Result: \\( 2 \\) is a quadratic residue modulo \\( 7 \\)
Example 2: \\( n = 3 \\), \\( p = 7 \\)
Inputs: Number = 3, Modulus = 7
Calculations:
- Legendre Symbol: \\[ \left( \frac{3}{7} \right) = 3^{(7-1)/2} = 3^3 = 27 \equiv 6 \equiv -1 \pmod{7} \\]
- Result: \\( 3 \\) is not a quadratic residue modulo \\( 7 \\)
Result: \\( 3 \\) is not a quadratic residue modulo \\( 7 \\)
Example 3: \\( n = 0 \\), \\( p = 5 \\)
Inputs: Number = 0, Modulus = 5
Calculations:
- Legendre Symbol: \\[ \left( \frac{0}{5} \right) = 0 \\] (since \\( 0 \equiv 0 \pmod{5} \\))
- Result: \\( 0 \\) is a quadratic residue modulo \\( 5 \\)
Result: \\( 0 \\) is a quadratic residue modulo \\( 5 \\)
How to Use the Calculator
Follow these steps to check if a number is a quadratic residue modulo a prime:
- Enter Number (\\( n \\)): Input a non-negative integer (e.g., 5).
- Enter Modulus (\\( p \\)): Input a prime number (e.g., 7).
- Calculate: Click “Check Quadratic Residue” to see the result.
- Interpret Result: The result shows whether \\( n \\) is a quadratic residue modulo \\( p \\), with calculations using the Legendre symbol.
- Share or Embed: Use the share buttons to post results on social media, copy the result, or get an embed code.
Note: The modulus \\( p \\) must be prime. Non-prime moduli or invalid inputs will prompt an error. For large numbers, calculations use modular exponentiation for efficiency.