A342256 Numbers k such that gcd(k, Phi_k(a)) > 1 for some a, where Phi_k is the k-th cyclotomic polynomial.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 31, 32, 34, 37, 38, 39, 41, 42, 43, 46, 47, 49, 50, 52, 53, 54, 55, 57, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 78, 79, 81, 82, 83, 86, 89, 93, 94, 97, 98, 100, 101

Offset: 1

Author

Jianing Song, Mar 07 2021

Keywords

• nonn
• easy

Comments

Indices of columns of A342255 with some elements greater than 1.

For k > 1, let p be the largest prime factor of k, then k is a term if and only if k = p^e*d with d | (p-1). See A342255 for more information.

Also numbers k such that A342257(k) > 1.

Examples

			6 is a term since gcd(6, Phi_6(2)) = gcd(6, 3) = 3 > 1.
55 is a term since 55 = 11*5, 5 | (11-1). Indeed, gcd(55, Phi_55(3)) = gcd(55, 8138648440293876241) = 11 > 1.
12 is not a term since 12 = 3*4 but 4 does not divide 3-1. Indeed, gcd(12, Phi_12(a)) = gcd(12, a^4-a^2+1) = 1 for all a.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A342255, A342257. Complement of A253235.

Programs

PARI

isA342256(k) = if(k>1, my(L=factor(k), d=omega(k), p=L[d,1]); (p-1)%(k/p^L[d,2])==0, 0)

Formula

Equals Union_{p prime} (Union_{d|(p-1)} {d*p, d*p^2, ..., d*p^e, ...}).