A327922 Odd numbers m >= 3 for which phi(2*m)/2 = phi(m)/2 is even, where phi = A000010 (Euler's totient).

5, 13, 15, 17, 21, 25, 29, 33, 35, 37, 39, 41, 45, 51, 53, 55, 57, 61, 63, 65, 69, 73, 75, 77, 85, 87, 89, 91, 93, 95, 97, 99, 101, 105, 109, 111, 113, 115, 117, 119, 123, 125, 129, 133, 135, 137, 141, 143, 145, 147, 149, 153, 155, 157, 159, 161, 165, 169, 171, 173, 175, 177, 181, 183, 185, 187, 189, 193

Offset: 1

Author

Wolfdieter Lang, Nov 12 2019

Keywords

• nonn
• easy

Comments

This sequence is the complement of A197504 with respect to the positive odd numbers. It collects all positive odd numbers m with 4 dividing phi(m).

In the prime number factorization of an odd m >= 3 the largest even factor of phi(a(n)) is 2^{2*r1 + r3}, where r1 and r3 are the nonnegative number of distinct primes 1 (mod 4) and 3 (mod 4), respectively. This means that for m = a(n) one needs 2*r1 + r3 >= 2. See some examples below.

The number of solutions of the congruence x^2 == +1 (mod a(n)) or (inclusive) x^2 == -1 (mod a(n)) is 2^(r1 + r3) + delta_{r3,0}*2^r1, with 2*r1 + r3 >= 2, where r1 and r3 are the number of distinct primes 1 (mod 4) and 3 (mod 4), respectively, in the prime number factorization of a(n), and delta is the Kronecker symbol.

This follows from the result that primes 1 (mod 4) (A002144) have Legendre symbol (-1, p) = +1 and primes 3 (mod 4) (A002145) have (-1, p) = -1. The part (a) of the lifting theorem for powers of primes (Apostol, 5.30, pp. 121-122) is used. Also the theorem that for odd primes p there are exactly (p-1)/2 quadratic residues modulo p (and exactly (p-1)/2 nonresidues modulo p) is needed (see e.g., Silverman, ch. 20, Theorem 1, p. 151).

Examples

			[n, a(n), [r1, r3], number of solutions x (mod a(n)), [solutions]] (with pm for + or -):
  [1, 5, [1, 0], 4, [pm1, pm2]],
  [5, 21 = 3*7, [0, 2], 4, [pm1, pm8]],
  [20, 65 = 5*13, [1, 1], 8, [pm1, pm8, pm14, pm18]],
  [34, 105 = 3*5*7, [1, 2], 8, [pm1, pm29, pm34, pm41]].
		

References

• T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, pp. 121-122.
• J. H. Silverman, A Friendly Introduction to Number Theory, fourth ed., Pearson Education, Inc, 2014, ch. 20, pp. 149-155.

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A197504, A329584 (phi(a(n))/4).

Programs

Mathematica

Select[Range[3, 200, 2], And[EvenQ[#1], #1 == #2] & @@ {EulerPhi[2 #]/2, EulerPhi[#]/2} &] (* Michael De Vlieger, Jun 28 2020 *)

PARI

isok(m) = (m > 3) && (m % 2) && ((eulerphi(m) % 4) == 0); \\ Michel Marcus, Nov 13 2019

Formula

All members of the set {odd m >= 1: 4 | phi(m)} ordered increasingly.