A039769 Composite integers k such that gcd(phi(k), k - 1) > 1.

9, 15, 21, 25, 27, 28, 33, 35, 39, 45, 49, 51, 52, 55, 57, 63, 65, 66, 69, 70, 75, 76, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124, 125, 129, 130, 133, 135, 141, 143, 145, 147, 148, 153, 154, 155, 159, 161, 165, 169, 171, 172, 175

Offset

1,1

Comments

Previous name was: phi(a(n)) and (a(n) - 1) have a common factor but are distinct.

Equivalently, numbers n that are Fermat pseudoprimes to some base b, 1 < b < n. A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n). Cf. A181780. - Geoffrey Critzer, Apr 04 2015

A071904, the odd composite numbers, is a subset of this sequence. - Peter Munn, May 15 2017

Lehmer's totient problem can be stated as finding a number in this sequence such that gcd(a(n) - 1, phi(a(n)) = phi(n). By the original definition of this sequence, such a number (if it exists) would not be in this sequence. - Alonso del Arte, Sep 07 2018, clarified Sep 14 2018

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Example

phi(21) = 12 and gcd(12, 20) = 4 > 1, hence 21 is in the sequence.
phi(22) = 10 but gcd(10, 21) = 1, so 22 is not in the sequence.

Maple

select(n -> not isprime(n) and igcd(n-1, numtheory:-phi(n))>1, [$4..1000]);  #Robert Israel, Apr 07 2015

Mathematica

Select[Range[250], GCD[EulerPhi[#], # - 1] > 1 && EulerPhi[#] != # - 1 &] (* Geoffrey Critzer, Apr 04 2015 *)

Prog

(PARI) forcomposite(k=1, 1e3, if(gcd(eulerphi(k), k-1) > 1, print1(k, ", "))); \\ Altug Alkan, Sep 21 2018

Crossrefs

Cf. A000010, A071904, A181780.

Sequence in context: A255763 A079364 A160666 * A270574 A071904 A326586

Adjacent sequences: A039766 A039767 A039768 * A039770 A039771 A039772

Keyword

nonn,easy

Author

Olivier Gérard

Extensions

Name clarified by Tom Edgar, Apr 05 2015

Status

approved