A209211 -id:A209211 - cp's OEIS frontend

A049559 a(n) = gcd(n - 1, phi(n)).

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 2, 1, 36, 1, 2, 1, 40, 1, 42, 1, 4, 1, 46, 1, 6, 1, 2, 3, 52, 1, 2, 1, 4, 1, 58, 1, 60, 1, 2, 1, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 2, 3, 4, 1, 78, 1, 2, 1, 82, 1, 4, 1, 2, 1, 88, 1, 18, 1, 4

Offset: 1

Labos Elemer, Dec 28 2000

nonn

For prime n, a(n) = n - 1. Question: do nonprimes exist with this property?
Answer: No. If n is composite then a(n) < n - 1. - Charles R Greathouse IV, Dec 09 2013
Lehmer's totient problem (1932): are there composite numbers n such that a(n) = phi(n)? - Thomas Ordowski, Nov 08 2015
a(n) = 1 for n in A209211. - Robert Israel, Nov 09 2015

			a(9) = 2 because phi(9) = 6 and gcd(8, 6) = 2.
a(10) = 1 because phi(10) = 4 and gcd(9, 4) = 1.

Richard K. Guy, Unsolved Problems in Number Theory, B37.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Lehmer's Totient Problem

Cf. A000010, A002322, A039766, A063994, A160595, A209211, A219428, A264012, A264024, A280262, A283656, A283872, A284089, A284440, A318827, A318829, A318830, A330747 (ordinal transform), A340195.

Cf. also A009195, A058515, A058663, A187730, A258409, A339964, A340071, A340081, A340087 for more or less analogous sequences.

[Gcd(n-1, EulerPhi(n)): n in [1..80]]; // Vincenzo Librandi, Oct 13 2018

seq(igcd(n-1, numtheory:-phi(n)), n=1..100); # Robert Israel, Nov 09 2015

Table[GCD[n - 1, EulerPhi[n]], {n, 93}] (* Michael De Vlieger, Nov 09 2015 *)

a(n)=gcd(eulerphi(n),n-1) \\ Charles R Greathouse IV, Dec 09 2013

from sympy import totient, gcd
print([gcd(totient(n), n - 1) for n in range(1, 101)]) # Indranil Ghosh, Mar 27 2017

a(p^m) = a(p) = p - 1 for prime p and m > 0. - Thomas Ordowski, Dec 10 2013
From Antti Karttunen, Sep 09 2018: (Start)
a(n) = A000010(n) / A160595(n) = A063994(n) / A318829(n).
a(n) = n - A318827(n) = A000010(n) - A318830(n).
(End)
a(n) = gcd(A000010(n), A219428(n)) = gcd(A000010(n), A318830(n)). - Antti Karttunen, Jan 05 2021

A063994 a(n) = Product_{primes p dividing n } gcd(p-1, n-1).

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, 4, 3, 52, 1, 4, 1, 4, 1, 58, 1, 60, 1, 4, 1, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 4, 3, 4, 1, 78, 1, 2, 1, 82, 1, 16, 1, 4, 1, 88, 1, 36, 1

Offset: 1

N. J. A. Sloane, Sep 18 2001

a(n) = number of bases b modulo n for which b^{n-1} == 1 (mod n).
a(A209211(n)) = 1. - Reinhard Zumkeller, Mar 02 2013
A049559(n) divides a(n) divides A000010(n). - Thomas Ordowski, Dec 14 2013
Note that a(n) = phi(n) iff n = 1 or n is prime or n is Carmichael number A002997. - Thomas Ordowski, Dec 17 2013

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722.
R. Baillie and S. S. Wagstaff, Lucas pseudoprimes, Mathematics of Computation, 35 (1980), 1391-1417.
P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Mathematics of Computation, 46 (1986), 259-279.
Keith Gibson, NMBRTHRY posting, Sep 07, 2001.
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.
Carl Pomerance, NMBRTHRY posting, Jul 26, 2001.

Cf. A002997, A027748.

a063994 n = product $ map (gcd (n - 1) . subtract 1) $ a027748_row n
-- Reinhard Zumkeller, Mar 02 2013

f[n_] := Times @@ GCD[n - 1, First /@ FactorInteger@ n - 1]; f[1] = 1; Array[f, 92] (* Robert G. Wilson v, Aug 08 2011 *)

for (n=1, 1000, f=factor(n)~; a=1; for (i=1, length(f), a*=gcd(f[1, i] - 1, n - 1)); write("b063994.txt", n, " ", a) ) \\ Harry J. Smith, Sep 05 2009

a(n)=my(f=factor(n)[,1]);prod(i=1,#f,gcd(f[i]-1,n-1)) \\ Charles R Greathouse IV, Dec 10 2013

def a(n):
    if n == 1: return 1
    return len([1 for witness in range(1,n) if pow(witness, n - 1, n) == 1])
[a(n) for n in range(1, 100)]

a(p^m) = p-1 and a(2p^m) = 1 for prime p and integer m > 0. - Thomas Ordowski, Dec 15 2013

a(n) = Sum_{k=1..n}(floor((k^(n-1)-1)/n)-floor((k^(n-1)-2)/n)). - Anthony Browne, May 11 2016

More terms from Robert G. Wilson v, Sep 21 2001

A247074 a(n) = phi(n)/(Product_{primes p dividing n } gcd(p - 1, n - 1)).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 3, 4, 1, 4, 1, 6, 2, 8, 1, 6, 1, 8, 3, 10, 1, 8, 5, 12, 9, 4, 1, 8, 1, 16, 5, 16, 6, 12, 1, 18, 6, 16, 1, 12, 1, 20, 3, 22, 1, 16, 7, 20, 8, 8, 1, 18, 10, 24, 9, 28, 1, 16, 1, 30, 9, 32, 3, 4, 1, 32, 11, 8, 1, 24, 1, 36, 10, 12, 15, 24, 1, 32, 27, 40, 1, 24, 4, 42, 14, 40, 1, 24, 2, 44, 15, 46

Offset: 1

Eric Chen, Nov 16 2014

a(n) = A000010(n)/A063994(n). - Eric Chen, Nov 29 2014
Does every natural number appear in this sequence? If so, do they appear infinitely many times? - Eric Chen, Nov 26 2014
A063994(n) must be a factor of EulerPhi(n). - Eric Chen, Nov 26 2014
Number n is (Fermat) pseudoprimes (or prime) to one in a(n) of its coprime bases. That is, b^(n-1) = 1 (mod n) for one in a(n) of numbers b coprime to n. - Eric Chen, Nov 26 2014
a(n) = 1 if and only if n is 1, prime (A000040), or Carmichael number (A002997). - Eric Chen, Nov 26 2014
a(A191311(n)) = 2. - Eric Chen, Nov 26 2014
a(p^n) = p^(n-1), where p is a prime. - Eric Chen, Nov 26 2014
a(A209211(n)) = EulerPhi(A209211(n)), because A063994(A209211(n)) = 1. - Eric Chen, Nov 26 2014

			EulerPhi(15) = 8, and that 15 is a Fermat pseudoprime in base 1, 4, 11, and 14, the total is 4 bases, so a(15) = 8/4 = 2.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Gérard P. Michon, Pseudoprimes

Cf. A063994, A182816, A002997, A191311, A064234, A000010, A063994, A003557, A209211.

a063994[n_] := Times @@ GCD[n - 1, First /@ FactorInteger@ n - 1]; a063994[1] = 1; a247074[n_] := EulerPhi[n]/a063994[n]; Array[a247074, 150]

a(n)=my(f=factor(n));eulerphi(f)/prod(i=1,#f~,gcd(f[i,1]-1,n-1)) \\ Charles R Greathouse IV, Nov 17 2014

A003557(n) <= a(n) <= n, and a(n) is a multiple of A003557(n). - Charles R Greathouse IV, Nov 17 2014

A318827 a(n) = n - gcd(n - 1, phi(n)).

Original entry on oeis.org

0, 1, 1, 3, 1, 5, 1, 7, 7, 9, 1, 11, 1, 13, 13, 15, 1, 17, 1, 19, 17, 21, 1, 23, 21, 25, 25, 25, 1, 29, 1, 31, 29, 33, 33, 35, 1, 37, 37, 39, 1, 41, 1, 43, 41, 45, 1, 47, 43, 49, 49, 49, 1, 53, 53, 55, 53, 57, 1, 59, 1, 61, 61, 63, 49, 61, 1, 67, 65, 67, 1, 71, 1, 73, 73, 73, 73, 77, 1, 79, 79, 81, 1, 83, 81, 85, 85, 87, 1, 89, 73

Offset: 1

Antti Karttunen, Sep 09 2018

nonn

a(n) = n-1 for n in A209211.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A051953, A049559, A209211, A318828, A318829, A318830.

Array[# - GCD[# - 1, EulerPhi[#]] &, 100] (* Alonso del Arte, Sep 09 2018 *)

PARI
```
A318827(n) = (n-gcd(eulerphi(n), n-1));
```

a(n) = n - A049559(n) = n - gcd(n - 1, phi(n)).
a(n) = A051953(n) + A318830(n).
a(p) = 1 for p prime.

A330747 Number of values of k, 1 <= k <= n, with A049559(k) = A049559(n), where A049559(n) = gcd(n - 1, phi(n)).

Original entry on oeis.org

1, 2, 1, 3, 1, 4, 1, 5, 2, 6, 1, 7, 1, 8, 3, 9, 1, 10, 1, 11, 2, 12, 1, 13, 3, 14, 4, 1, 1, 15, 1, 16, 4, 17, 5, 18, 1, 19, 6, 20, 1, 21, 1, 22, 5, 23, 1, 24, 2, 25, 7, 2, 1, 26, 8, 27, 6, 28, 1, 29, 1, 30, 9, 31, 2, 1, 1, 32, 7, 3, 1, 33, 1, 34, 10, 4, 8, 35, 1, 36, 11, 37, 1, 38, 9, 39, 12, 40, 1, 41, 2, 42, 10, 43, 13

Offset: 1

Antti Karttunen, Dec 30 2019

nonn

Ordinal transform of A049559.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A049559, A209211.

Cf. also A081373, A303756, A330756.

b[_] = 0;
a[n_] := With[{t = GCD[n-1, EulerPhi[n]]}, b[t] = b[t]+1];
Array[a, 105] (* Jean-François Alcover, Dec 27 2021 *)

up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
A049559(n) = gcd(n-1, eulerphi(n));
v330747 = ordinal_transform(vector(up_to, n, A049559(n)));
A330747(n) = v330747[n];

A111305 Composite numbers k such that a^(k-1) == 1 (mod k) only when a == 1 (mod k).

Original entry on oeis.org

4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 72, 74, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 114, 116, 118, 120, 122, 126, 128, 132, 134, 136, 138, 140, 142, 144

Offset: 1

Karsten Meyer, Nov 02 2005

nonn

These unCarmichael numbers fail the Fermat primality test as often as possible.
All such numbers are even: for odd n, (-1)^(n-1) = 1.
The even numbers not in this sequence are 2 and A039772.
If c is a Carmichael number, then 2c is in the sequence. Also, the sequence is A209211 without the first two terms. - Emmanuel Vantieghem, Jul 03 2013

			10 is a term because 3^9 == 3 (mod 10), 7^9 == 7 (mod 10), 9^9 == 9 (mod 10).

Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.

Cf. A002997, A039772, A209211, A227180.

Select[Range[4, 144],Count[Table[PowerMod[b, # - 1, #], {b, 1, # - 1}], 1] == 1 &] (* Geoffrey Critzer, Apr 11 2015 *)

is(n)=for(a=2,n-1, if(Mod(a,n)^(n-1)==1, return(0))); !isprime(n) \\ Charles R Greathouse IV, Dec 22 2016

Edited by Don Reble, May 16 2006

A227180 Composite numbers n such that b^(n-1) == 1 (mod n) implies b == -1 or +1 (mod n).

Original entry on oeis.org

4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 27, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 72, 74, 78, 80, 81, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 114, 116, 118, 120, 122, 126, 128, 132, 134, 136, 138, 140, 142, 144, 146, 150, 152, 156, 158, 160, 162, 164, 166, 168, 170

Offset: 1

Emmanuel Vantieghem, Jul 03 2013

nonn

The sequence is the union of A111305 with {3^k | k > 1}.

The composite numbers not in this sequence are the Fermat pseudoprimes A181780.

Cf. A111305, A181780, A209211.

FQ[k_]:= Block[{},GCD[EulerPhi[k],k-1]==1||IntegerQ[Log[3,k]]];Select[Range[4,170],FQ]

is(n)=for(b=2, n-2, if(Mod(b, n)^(n-1)==1, return(0))); !isprime(n) \\ Charles R Greathouse IV, Dec 22 2016

A280196 Numbers n such that a^(n-1) == 1 (mod n^2) has no solutions with 1 < a < n^2-1.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 27, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 72, 74, 78, 80, 81, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 114, 116, 118, 120, 122, 126, 128, 132, 134, 136, 138

Offset: 1

Robert Israel and Thomas Ordowski, Dec 28 2016

nonn

1 and numbers n such that A185103(n) = n^2 + (-1)^n.
Complement of A280199.
Union of A000244 and A209211.

			a(4) = 4 is in the sequence because a^3 == 1 (mod 4^2) has no solutions except a == 1 (mod 4^2).
a(7) = 9 is in the sequence because a^8 == 1 (mod 9^2) has no solutions except a == 1 (mod 9^2) and a == 80 (mod 9^2), and 80 = 9^2-1.

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

Cf. A000244, A185103, A209211, A280199.

Aeven:= select(t -> igcd(t-1, numtheory:-phi(t^2))=1, {seq(i,i=2..1000,2}}):
Aodd:= {seq(3^i,i=0..floor(log[3](1000)))}:
sort(convert(Aeven union Aodd, list));

Aeven = Select[Range[2, 1000, 2], GCD[#-1,EulerPhi[#^2]] == 1&];
Aodd = 3^Range[0, Floor[Log[3, 1000]]];
Union[Aeven, Aodd] (* Jean-François Alcover, Apr 27 2019, from Maple *)

A330756 Number of values of k, 1 <= k <= n, with A063994(k) = A063994(n), where A063994(n) = Product_{primes p dividing n} gcd(p-1, n-1).

Original entry on oeis.org

1, 2, 1, 3, 1, 4, 1, 5, 2, 6, 1, 7, 1, 8, 2, 9, 1, 10, 1, 11, 3, 12, 1, 13, 4, 14, 3, 1, 1, 15, 1, 16, 5, 17, 6, 18, 1, 19, 7, 20, 1, 21, 1, 22, 1, 23, 1, 24, 2, 25, 8, 2, 1, 26, 9, 27, 10, 28, 1, 29, 1, 30, 11, 31, 2, 1, 1, 32, 12, 3, 1, 33, 1, 34, 13, 4, 14, 35, 1, 36, 4, 37, 1, 38, 3, 39, 15, 40, 1, 41, 2, 42, 16

Offset: 1

Antti Karttunen, Dec 30 2019

nonn

Ordinal transform of A063994.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A063994, A209211.

Cf. also A081373, A303756, A330747.

A063994[n_] := If[n==1, 1, Times @@ GCD[n-1, First /@ FactorInteger[n]-1]];
Module[{b}, b[_] = 0;
a[n_] := With[{t = A063994[n]}, b[t] = b[t]+1]];
Array[a, 105] (* Jean-François Alcover, Jan 12 2022 *)

up_to = 65537;
A063994(n) = { my(f=factor(n)[, 1]); prod(i=1, #f, gcd(f[i]-1, n-1)); }; \\ From A063994
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
v330756 = ordinal_transform(vector(up_to, n, A063994(n)));
A330756(n) = v330756[n];

A039767 Numbers k such that gcd(phi(k), k-1) = number of distinct prime factors of (k-1).

Original entry on oeis.org

4, 6, 8, 10, 12, 14, 15, 18, 20, 24, 26, 27, 30, 32, 35, 38, 39, 42, 44, 48, 50, 51, 54, 55, 60, 62, 63, 68, 72, 74, 75, 80, 81, 82, 84, 87, 90, 95, 98, 99, 102, 104, 108, 110, 114, 119, 122, 123, 126, 128, 132, 135, 138, 140, 143, 147, 150, 152, 158, 159, 164, 168

Offset: 1

Olivier Gérard

If k = p+1 where p is an odd prime, then k is a term. - Amiram Eldar, Sep 16 2024

			phi(15) = 8, gcd(8, 14) = 2, 14 = 2*7, 2 prime factors.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A001221, A049559, A209211.

q[k_] := GCD[EulerPhi[k], k-1] == PrimeNu[k-1]; Select[Range[200], q] (* Amiram Eldar, Sep 16 2024 *)

is(k) = k > 1 && gcd(eulerphi(k), k-1) == omega(k-1); \\ Amiram Eldar, Sep 16 2024

cp's OEIS Frontend

A049559 a(n) = gcd(n - 1, phi(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A063994 a(n) = Product_{primes p dividing n } gcd(p-1, n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

Extensions

A247074 a(n) = phi(n)/(Product_{primes p dividing n } gcd(p - 1, n - 1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A318827 a(n) = n - gcd(n - 1, phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A330747 Number of values of k, 1 <= k <= n, with A049559(k) = A049559(n), where A049559(n) = gcd(n - 1, phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A111305 Composite numbers k such that a^(k-1) == 1 (mod k) only when a == 1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A227180 Composite numbers n such that b^(n-1) == 1 (mod n) implies b == -1 or +1 (mod n).

Views

Author