login
a(n) = smallest integer m>0 such that the positive integers not exceeding m and coprime to n generate the multiplicative group U(Z/nZ).
6

%I #18 Apr 20 2017 15:15:41

%S 1,1,2,3,2,5,3,5,2,3,2,7,2,3,7,5,3,5,2,11,5,7,5,13,2,5,2,5,2,11,3,5,5,

%T 3,3,7,2,3,7,11,3,11,3,7,7,5,5,13,3,3,5,5,2,5,3,11,5,3,2,13,2,3,5,5,3,

%U 7,2,5,5,19,7,13,5,5

%N a(n) = smallest integer m>0 such that the positive integers not exceeding m and coprime to n generate the multiplicative group U(Z/nZ).

%C Denoted G(n) in Burthe (1997).

%C If A046145(n)>0, then a(n) <= A046145(n).

%C For all n>=3, a(n) is prime.

%H Burthe, R. J., Jr. <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa80/aa8042.pdf">Upper bounds for least witnesses and generating sets</a>. Acta Arith. 80:4 (1997), 311-326.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n">Multiplicative group of integers modulo n</a>.

%o (PARI) { A285512(n) = my(S,s,t); S=Set([Mod(1,n)]); t=1; while( #S!=eulerphi(n), until(n%t,t=nextprime(t+1)); until(#S==s, s=#S; S=setunion(S,Set(S*t))); ); t; }

%Y Cf. A002997, A046145, A285513, A285514.

%K nonn

%O 1,3

%A _Max Alekseyev_ and _Thomas Ordowski_, Apr 20 2017