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,2

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.

Links

Table of n, a(n) for n=1..60.

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.

Formula

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

Example

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

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

Crossrefs

Cf. A195637.

Sequence in context: A064919 A064923 A064924 * A332462 A358137 A256662

Adjacent sequences: A196327 A196328 A196329 * A196331 A196332 A196333

Keyword

nonn

Author

Michel Lagneau, Oct 01 2011

Status

approved