A366935 -id:A366935 - cp's OEIS frontend

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.

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

Miles Englezou, Dec 09 2023

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.

			k = 2 is a term: |Q_2| = phi(2)/2^0 = 1, and r = 0 < phi(2)/lambda(2) = 1.

D. Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993, page 95.

Cf. A366935, A000010, A002322, A046073, A034380, A033948, A046072.

isok(n) = my(z=znstar(n).cyc); #z < eulerphi(n)/lcm(z)

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

PARI