A339870 Composite numbers k of the form 4u+1 for which the odd part of phi(k) divides k-1.

85, 561, 1105, 1261, 1285, 2465, 4369, 6601, 8245, 8481, 9061, 9605, 10585, 16405, 16705, 17733, 18721, 19669, 21845, 23001, 28645, 30889, 38165, 42121, 43165, 46657, 54741, 56797, 57205, 62745, 65365, 74593, 78013, 83665, 88561, 91001, 106141, 117181, 124645, 126701, 134521, 136981, 141661, 162401, 171205, 176437

Offset: 1

Author

Antti Karttunen, Dec 22 2020

Keywords

• nonn

Comments

From Antti Karttunen, Dec 26 2020: (Start)

Equally, squarefree composite numbers k of the form 4u+1 for which A336466(k) divides k-1. This follows because on squarefree n, A336466(n) = A053575(n).

No common terms with A016105, because 4xy + 2(x+y) + 1 does not divide 4xy + 3(x+y) + 2 for any distinct x, y >= 0 (where 4x+3 and 4y+3 are the two prime factors of Blum integers).

This can also seen by another way: If this sequence contained any Blum integers, then, because A016105 is a subsequence of A339817, we would have found a composite number n satisfying Lehmer's totient problem y * phi(n) = n-1, for some integer y > 1. But Lehmer proved that such solutions should have at least 7 distinct prime factors, while Blum integers have only two.

Moreover, it seems that none of the terms of A167181 may occur here, and a few of A137409 (i.e., of A125667). See A339875 for those terms.

(End)

Examples

			85 = 4*21 + 1 = 5*17, thus phi(85) = 4*16 = 64, the odd part of which is A000265(64) = 1, which certainly divides 85-1, therefore 85 is included as a term.
561 = 4*140 + 1 = 3*11*17, thus phi(561) = 2*10*16 = 320, the odd part of which is A000265(320) = 5, which divides 560, therefore 561 is included.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..1316
• D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
• Wikipedia, Lehmer's totient problem

Crossrefs

Cf. A000010, A000265, A016105, A053575, A137409, A167181, A336466.

Subsequence of A005117.

Intersection of A091113 and A339880.

Cf. A339875 (a subsequence).

Cf. also comments in A339817.

Programs

Mathematica

odd[n_] := n/2^IntegerExponent[n, 2]; Select[4*Range[45000] + 1, CompositeQ[#] && Divisible[# - 1, odd[EulerPhi[#]]] &] (* Amiram Eldar, Feb 17 2021 *)

PARI

A000265(n) = (n>>valuation(n, 2));
isA339870(n) = ((n>1)&&!isprime(n)&&(1==(n%4))&&!((n-1)%A000265(eulerphi(n))));