# How to introduce quadratic residues?

• I
• matqkks
In summary, the most motivating way to introduce quadratic residues is to provide concrete examples and applications, such as their use in factorization of large numbers and in cryptography. They are also important in the computation of Legendre symbols and in solving polynomial equations. The topic can be further explored through resources such as John Cook's blog on quadratic congruences. Additionally, the solutions to quadratic equations in mod N arithmetic may have implications for solving general polynomial equations in mod N arithmetic.

#### matqkks

What is the most motivating way to introduce quadratic residues? I would like some concrete examples which have an impact. This is for first year undergraduates doing an elementary number theory course. They have done Diophantine equations, solved linear congruences, primitive roots.

Quadratic residues are used in the factorization of large numbers, so they have applications in cryptography ( pseudo random number generators, in encryption algorithms (for example https://en.wikipedia.org/wiki/Goldwasser–Micali_cryptosystem), ...)
In mathematics they are used for the computation of Legendre symbols and for the proof when a number is expressible as sum of two squares ...
Ssnow

matqkks said:
They have done Diophantine equations, solved linear congruences

If the class has studied linear congruences then purely mathematical curiosity leads to asking about polynomial congruences. The simplest example would be ##x^2 = A (mod\ M)## I haven't studied this topic. A blog by John Cook https://www.johndcook.com/blog/quadratic_congruences/ deals with it.

I wonder if any application of quadratic residues to a practical topic comes by way of needing to solve ##x^2 = A (mod \ M)##.

primitive roots.

The solutions to the quadratic equation ##x^2 = -1## play a crucial role in the theory of solving general polynomial equations over the real numbers. I wonder if the solutions to ##x^2 = A (mod\ N)## play a crucial role in the theory of solving general polynomial equations over the integers in mod N arithmetic. Can anybody comment on that?

## 1. What are quadratic residues?

Quadratic residues are integers that have a square root modulo some prime number or power of a prime number. In other words, they are integers that when squared and divided by a given prime number or power of a prime number, produce a remainder that is a perfect square.

## 2. Why are quadratic residues important?

Quadratic residues have important applications in number theory, cryptography, and algebraic geometry. They also play a crucial role in the study of modular arithmetic and can help in solving mathematical problems related to prime numbers.

## 3. How can I determine if an integer is a quadratic residue?

To determine if an integer is a quadratic residue modulo a prime number or power of a prime number, you can use the Legendre symbol or the Jacobi symbol. These symbols are mathematical functions that can evaluate whether an integer is a quadratic residue or not. Alternatively, you can use computational methods such as the Tonelli-Shanks algorithm to find the square root of a quadratic residue.

## 4. What is the difference between quadratic residues and non-residues?

Quadratic residues and non-residues are complementary sets of integers. Quadratic residues are integers that have a square root modulo a prime number or power of a prime number, while non-residues do not have a square root modulo that number. In other words, non-residues produce a remainder that is not a perfect square when squared and divided by a given prime number or power of a prime number.

## 5. Can quadratic residues be negative?

Yes, quadratic residues can be negative. When considering residues modulo a prime number, the set of quadratic residues includes both positive and negative integers. In contrast, when considering residues modulo a power of a prime number, the set of quadratic residues only includes non-negative integers.