OFFSET
1,1
COMMENTS
An empirical observation, verified for 2 <= k <= 10^5: The number of quadratic residues mod k coprime to k is |Q_k| = phi(k)/2^r, r = A046072(k) <= phi(k)/lambda(k). Up to 10^5, the equality holds for 37758 moduli, and the inequality holds for 62241.
REFERENCES
D. Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993, page 95.
EXAMPLE
k = 2 is a term: |Q_2| = phi(2)/2^0 = 1, and r = 0 < phi(2)/lambda(2) = 1.
PROG
(PARI) isok(n) = my(z=znstar(n).cyc); #z < eulerphi(n)/lcm(z)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Miles Englezou, Dec 09 2023
STATUS
approved