A196330 Smallest number k such that the number of distinct residues of x^k (mod k) equals n.

1, 2, 3, 6, 5, 10, 7, 14, 21, 68, 11, 22, 13, 26, 15, 114, 17, 34, 19, 38, 57, 164, 23, 46, 2525, 776, 657, 212, 29, 58, 31, 62, 33, 4112, 35, 102, 37, 74, 111, 380, 41, 82, 43, 86, 105, 356, 47, 94, 301, 388, 51, 404, 53, 106, 6275, 182, 1467, 452, 59, 118

Offset: 1

Author

Michel Lagneau, Oct 01 2011

Keywords

• nonn

Comments

The values of x can be taken to be 1 to n.

Properties of the sequence: if n prime, a(n) = n and a(n+1) = 2n because x^n == 0,1,2,3,...,n-1 (mod n) and x^(2n) == 0, 1^2, 2^2, 3^2,...,(n-1)^2, n (mod 2n) with n+1 distinct residues.

There exists prime numbers, for example n = 7, 19, 37,... with the property: a(n) = n, a(n+1) = 2n, and a(n+2) = 3n.

There exists composite numbers, for example n = 15, 33, 35, 51,... with the property a(n) = n.

Examples

			a(6) = 10 because x^10 == 0, 1, 4, 5, 6, 9  (mod 10) => 6 distinct residues.
		

Links

• I. M. Vinogradov, On a general theorem concerning the distribution of the residues and non-residues of powers, Trans. American Math. Soc., 29 (1927), 209-217.

Crossrefs

Cf. A195637.

Programs

Maple

a:= nops ({seq (k&^n mod n, k=0..n-1)}):for i from 1 to 60 do:id:=0:for j from 1 to 10000 while(id=0) do:if a(j)=i then id:=1:printf ( "%d %d \n",i,j):else fi:od:od:

Mathematica

nn = 10000; t = Table[Length[Union[PowerMod[Range[n], n, n]]], {n, nn}]; lim = Complement[Range[nn], Union[t]][[1]] - 1; Table[Position[t, n, 1, 1][[1, 1]], {n, lim}] (* T. D. Noe, Oct 03 2011 *)

Formula

a(n) such that A195637(a(n)) = n.