A276976 Smallest m such that b^m == b^n (mod n) for every integer b.

0, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 4, 5, 2, 9, 4, 1, 2, 1, 8, 3, 2, 11, 6, 1, 2, 3, 4, 1, 6, 1, 4, 9, 2, 1, 4, 7, 10, 3, 4, 1, 18, 15, 8, 3, 2, 1, 4, 1, 2, 3, 16, 5, 6, 1, 4, 3, 10, 1, 6, 1, 2, 15, 4, 17, 6, 1, 4, 27, 2, 1

Offset

1,4

Comments

It suffices to check all bases 0 < b < n for n > 2.

The congruence n == a(n) (mod A002322(n)) is always true.

a(n) = 1 iff n is a prime or a Carmichael number.

We have a(n) > 0 for n > 1, and a(n) <= n/2.

If n > 2 then a(n) is odd iff n is odd.

Conjecture: a(n) <= n/3 for every n >= 9.

Professor Andrzej Schinzel proved this conjecture (in a letter to the author). - Thomas Ordowski, Sep 30 2016

Note: a(n) = n/3 for n = A038754 >= 3.

Numbers n such that a(n) > A270096(n) are A290960.

Information from Carl Pomerance: a(n) > A002322(n) if and only if 8|n and n is in A050990; such n = 8, 24, 56, ... - Thomas Ordowski, Jun 21 2017

Number of integers k < n such that b^k == b^n (mod n) for every integer b is f(n) = (n - a(n))/lambda(n). For n > 1, f(n) = floor((n-1)/lambda(n)) if and only if a(n) <= lambda(n), where lambda(n) = A002322(n). - Thomas Ordowski, Jun 21 2017

a(n) >= A051903(n); numbers n such that a(n) = A051903(n) are 1, primes, Carmichael numbers, and A327295. - Thomas Ordowski, Dec 06 2019

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Formula

a(p) = 1 for prime p.

a(2*p) = 2 for prime p.

a(3*p) = 3 for odd prime p.

a(p^k) = p^(k-1) for odd prime p and k >= 1.

a(2*p^k) = 2*p^(k-1) for odd prime p and k >= 1.

a(2^k) = 2^(k-2) for k >= 4.

From Thomas Ordowski, Jul 09 2017: (Start)

Full description of the function:

a(n) = lambda(n) if lambda(n)|n except n = 1, 8, and 24;

a(n) = lambda(n)+2 if lambda(n)|(n-2) and 8|n;

a(n) = n mod lambda(n) otherwise;

where lambda(n) = A002322(n). (End)

For n <> 8 and 24, a(n) = A(n) if A(n) >= A051903(n) or a(n) = A002322(n) + A(n) otherwise, where A(n) = A219175(n). - Thomas Ordowski, Nov 30 2019

Mathematica

With[{nn = 83}, Table[SelectFirst[Range[nn/4 + 10], Function[m, AllTrue[Range[2, n - 1], PowerMod[#, m , n] == PowerMod[#, n , n] &]]] - Boole[n == 1], {n, nn}]] (* Michael De Vlieger, Aug 15 2017 *)
a[1] = 0; a[8] = a[24] = 4; a[n_] := If[(rem = Mod[n, (lam = CarmichaelLambda[n])]) >= Max @@ Last /@ FactorInteger[n], rem, rem + lam]; Array[a, 100] (* Amiram Eldar, Nov 30 2019 *)

Prog

(PARI) a(n)=if(n<3, return(n-1)); forstep(m=1, n, n%2+1, for(b=0, n-1, if(Mod(b, n)^m-Mod(b, n)^n, next(2))); return(m)) \\ Charles R Greathouse IV, Sep 23 2016
(Python) def a(n): return next(m for m in range(0, n+1) if all(pow(b, m, n)==pow(b, n, n) for b in range(1, 2*n+1))) # Nicholas Stefan Georgescu, Jun 03 2022

Crossrefs

Cf. A002322, A002997, A038754, A050990, A051903, A124240, A219175, A270096, A290960, A327295.

Sequence in context: A184342 A030767 A352933 * A135545 A123317 A231557

Adjacent sequences: A276973 A276974 A276975 * A276977 A276978 A276979

Keyword

nonn,nice

Author

Thomas Ordowski, Sep 23 2016

Extensions

More terms from Altug Alkan, Sep 23 2016

Status

approved