cp's OEIS Frontend

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

%I A276976 #96 Jun 03 2022 12:59:59
%S A276976 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,
%T A276976 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,
%U A276976 1,4,3,10,1,6,1,2,15,4,17,6,1,4,27,2,1
%N A276976 Smallest m such that b^m == b^n (mod n) for every integer b.
%C A276976 It suffices to check all bases 0 < b < n for n > 2.
%C A276976 The congruence n == a(n) (mod A002322(n)) is always true.
%C A276976 a(n) = 1 iff n is a prime or a Carmichael number.
%C A276976 We have a(n) > 0 for n > 1, and a(n) <= n/2.
%C A276976 If n > 2 then a(n) is odd iff n is odd.
%C A276976 Conjecture: a(n) <= n/3 for every n >= 9.
%C A276976 Professor Andrzej Schinzel proved this conjecture (in a letter to the author). - _Thomas Ordowski_, Sep 30 2016
%C A276976 Note: a(n) = n/3 for n = A038754 >= 3.
%C A276976 Numbers n such that a(n) > A270096(n) are A290960.
%C A276976 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
%C A276976 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
%C A276976 a(n) >= A051903(n); numbers n such that a(n) = A051903(n) are 1, primes, Carmichael numbers, and A327295. - _Thomas Ordowski_, Dec 06 2019
%H A276976 Charles R Greathouse IV, <a href="/A276976/b276976.txt">Table of n, a(n) for n = 1..10000</a>
%F A276976 a(p) = 1 for prime p.
%F A276976 a(2*p) = 2 for prime p.
%F A276976 a(3*p) = 3 for odd prime p.
%F A276976 a(p^k) = p^(k-1) for odd prime p and k >= 1.
%F A276976 a(2*p^k) = 2*p^(k-1) for odd prime p and k >= 1.
%F A276976 a(2^k) = 2^(k-2) for k >= 4.
%F A276976 From _Thomas Ordowski_, Jul 09 2017: (Start)
%F A276976 Full description of the function:
%F A276976 a(n) = lambda(n) if lambda(n)|n except n = 1, 8, and 24;
%F A276976 a(n) = lambda(n)+2 if lambda(n)|(n-2) and 8|n;
%F A276976 a(n) = n mod lambda(n) otherwise;
%F A276976 where lambda(n) = A002322(n). (End)
%F A276976 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
%t A276976 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 *)
%t A276976 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 *)
%o A276976 (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
%o A276976 (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
%Y A276976 Cf. A002322, A002997, A038754, A050990, A051903, A124240, A219175, A270096, A290960, A327295.
%K A276976 nonn,nice
%O A276976 1,4
%A A276976 _Thomas Ordowski_, Sep 23 2016
%E A276976 More terms from _Altug Alkan_, Sep 23 2016