cp's OEIS Frontend

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

%I A039769 #44 Aug 09 2024 01:23:07
%S A039769 9,15,21,25,27,28,33,35,39,45,49,51,52,55,57,63,65,66,69,70,75,76,77,
%T A039769 81,85,87,91,93,95,99,105,111,112,115,117,119,121,123,124,125,129,130,
%U A039769 133,135,141,143,145,147,148,153,154,155,159,161,165,169,171,172,175
%N A039769 Composite integers k such that gcd(phi(k), k - 1) > 1.
%C A039769 Previous name was: phi(a(n)) and (a(n) - 1) have a common factor but are distinct.
%C A039769 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
%C A039769 A071904, the odd composite numbers, is a subset of this sequence. - _Peter Munn_, May 15 2017
%C A039769 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
%H A039769 Robert Israel, <a href="/A039769/b039769.txt">Table of n, a(n) for n = 1..10000</a>
%e A039769 phi(21) = 12 and gcd(12, 20) = 4 > 1, hence 21 is in the sequence.
%e A039769 phi(22) = 10 but gcd(10, 21) = 1, so 22 is not in the sequence.
%p A039769 select(n -> not isprime(n) and igcd(n-1, numtheory:-phi(n))>1, [$4..1000]);  # _Robert Israel_, Apr 07 2015
%t A039769 Select[Range[250], GCD[EulerPhi[#], # - 1] > 1 && EulerPhi[#] != # - 1 &] (* _Geoffrey Critzer_, Apr 04 2015 *)
%o A039769 (PARI) forcomposite(k=1, 1e3, if(gcd(eulerphi(k), k-1) > 1, print1(k, ", "))); \\ _Altug Alkan_, Sep 21 2018
%Y A039769 Cf. A000010, A071904, A181780.
%K A039769 nonn,easy
%O A039769 1,1
%A A039769 _Olivier Gérard_
%E A039769 Name clarified by _Tom Edgar_, Apr 05 2015