A366935 Moduli k for which the number of quadratic residues mod k coprime to k is equal to phi(k)/2^(phi(k)/lambda(k)), where lambda is Carmichael's function.

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 61, 62, 64, 66, 67, 68, 69, 70, 71, 73, 74, 75

Offset: 1

Author

Miles Englezou, Oct 29 2023

Keywords

• nonn
• easy

Comments

Numbers k such that A046073(k) = A000010(k)/2^A034380(k).

An empirical observation, calculated 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.

Examples

			k = 3 is a term: |Q_3| = phi(3)/2^1 = 1, so r = 1 = phi(3)/lambda(3).
		

References

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

Links

• Miles Englezou, MATLAB script

Crossrefs

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

Programs

PARI

isok(n) = my(z=znstar(n).cyc); #z == eulerphi(n)/lcm(z) \\ Andrew Howroyd, Oct 29 2023

Formula

{ k : |Q_k| = phi(k)/2^(phi(k)/lambda(k)) }, where lambda is Carmichael's function (A002322).