login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

CROSSREFS

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

Sequence in context: A060805 A184342 A030767 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 00:28 EDT 2021. Contains 346265 sequences. (Running on oeis4.)