How to introduce quadratic residues?

  • #1
201
2
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.
 

Answers and Replies

  • #2
Ssnow
Gold Member
532
156
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
 
  • #3
Stephen Tashi
Science Advisor
7,569
1,465
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?
 

Related Threads on How to introduce quadratic residues?

Replies
5
Views
510
  • Last Post
Replies
3
Views
946
Replies
10
Views
4K
Replies
2
Views
443
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
1
Views
1K
Top