login
A368042
Moduli k for which the number of quadratic residues mod k coprime to k is phi(k)/2^r for positive r = (phi(k)/lambda(k)) - x, x > 0, where lambda is Carmichael's function. Complement of A366935.
0
2, 24, 40, 48, 56, 60, 63, 65, 72, 80, 84, 85, 88, 91, 96, 104, 105, 112, 117, 120, 126, 130, 132, 133, 136, 140, 144, 145, 152, 156, 160, 165, 168, 170, 171, 176, 180, 182, 184, 185, 189, 192, 195, 200, 204, 205, 208, 210, 216, 217
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)
KEYWORD
nonn,easy
AUTHOR
Miles Englezou, Dec 09 2023
STATUS
approved