Quadratic residues are so much fun!
MATL, 14 bytes

:UG\u&amp;-G\8#uX&lt;


Try it online! Or verify the first 30 values.

Explanation

:      % Implicit input. Range
U      % Square, element-wise
G      % Push input again
\      % Modulo, element-wise
u      % Unique elements
&amp;-     % Table of pair-wise differences
G      % Push input
\      % Modulo, element-wise
8#u    % Number of occurrences of each element
X&lt;     % Minimum. Implicit display