Quadratic non-residues
Number Theory
Level
5
Find the smallest \(n\) such that for some prime \(p\), at least \(20\) of the numbers \(1,2,...,n\) are quadratic non-residues modulo \(p\).
Details and assumptions
\(k\) is a quadratic residue modulo \(p\) if there exists an integer \(j\) such that \( j^2 \equiv k \pmod{p} \).
There is no condition on the relative sizes of \(n\) and \(p\). As an explicit example, if \(p=3\), then \(n=59 \) would satisfy the conditions of the question.
by
Calvin Lin