A111076 Smallest positive number of maximal order mod n.

1, 1, 2, 3, 2, 5, 3, 3, 2, 3, 2, 5, 2, 3, 2, 3, 3, 5, 2, 3, 2, 7, 5, 5, 2, 7, 2, 3, 2, 7, 3, 3, 2, 3, 2, 5, 2, 3, 2, 3, 6, 5, 3, 3, 2, 5, 5, 5, 3, 3, 5, 7, 2, 5, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 7, 5, 5, 5, 2, 3, 2, 7, 3, 3, 2, 7, 2, 5, 3, 3, 2, 3, 3, 7, 2, 3, 11, 5, 2, 5, 5, 3, 2, 3

Offset: 1

Author

Franklin T. Adams-Watters, Oct 10 2005

Keywords

• easy
• nonn

Examples

			a(6)=5 because order of 1 is 1 and 2 through 4 are not relatively prime to 6, but 5 has order 2, which is the maximum possible.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A002322 (orders); same as A046145 for n with primitive roots; see also A001918 (for primes), A229708.

Programs

Mathematica

Table[Min[
  Select[Range[n],
   CoprimeQ[#, n] &&
     MultiplicativeOrder[#, n] == CarmichaelLambda[n] &]], {n, 1, 100}]
(* Geoffrey Critzer, Jan 04 2015 *)

PARI

a(n)=if(n==1, return(1)); if(n<5,return(n-1)); my(o=lcm(znstar(n)[2]),k=1); while(gcd(k++,n)>1 || znorder(Mod(k,n))Charles R Greathouse IV, Jul 31 2013

Formula

a(n) = A229708(n) if and only if a(n) is prime. - Jonathan Sondow, May 17 2017