VOOZH about

URL: https://oeis.org/A276976

⇱ A276976 - OEIS

login
A276976
Smallest m such that b^m == b^n (mod n) for every integer b.
7
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
KEYWORD
nonn,nice
AUTHOR
Thomas Ordowski, Sep 23 2016
EXTENSIONS
More terms from Altug Alkan, Sep 23 2016
STATUS
approved