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,1

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.

References

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

Links

Table of n, a(n) for n=1..65.

Miles Englezou, MATLAB script

Formula

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

Example

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

Prog

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

Crossrefs

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

Sequence in context: A065475 A062983 A081311 * A053233 A121818 A179005

Adjacent sequences: A366932 A366933 A366934 * A366936 A366937 A366938

Keyword

nonn,easy

Author

Miles Englezou, Oct 29 2023

Status

approved