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

Author

Olivier Gérard

Keywords

• nonn
• easy

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A000010, A071904, A181780.

Programs

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 *)

PARI

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

Extensions

Name clarified by Tom Edgar, Apr 05 2015