login
This site is supported by donations to The OEIS 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. 5
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 8, 32, 56, 64, 96, 128, 144, 155, 170, 176, 192, 196, 204, 215, 221, 224, 238, 248, 255, 256, 272, 288, 320, 322, 336, 341, 352, 368, 372, 374, 384, 432, 448, 465, 476, ... - Altug Alkan, Sep 23 2016

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

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)

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

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, A124240, A219175, A270096.

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 October 22 14:44 EDT 2019. Contains 328318 sequences. (Running on oeis4.)