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

Author

Thomas Ordowski, Sep 23 2016

Keywords

• nonn
• nice

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

Crossrefs

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

Programs

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

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

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

Extensions

More terms from Altug Alkan, Sep 23 2016