How to introduce quadratic residues?

[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.

 

[Ssnow]

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

 

[Stephen Tashi]

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?