Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I How to introduce quadratic residues?

  1. Jul 12, 2018 #1
    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.
  2. jcsd
  3. Jul 16, 2018 #2


    User Avatar
    Gold Member

    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 ...
  4. Jul 16, 2018 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    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)##.

    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?