A309090 - OEIS

%I #13 Jul 12 2019 02:38:55

%S 1,2,2,3,3,172,213,213,333,333,1228,1438,2152,3832,3832,3832,5792,

%T 22732,22732,37342,37342,37342,37342,37342,545408,629247,629247,

%U 629247,629247,629247,629247,629247,629247,1423713,8136838,8136838

%N a(n) is the least x such that x^2 mod prime(i), i=1..n, are all distinct.

%C There are more than n squares mod prime(n+1); therefore given a(n)=k we can choose a square r mod prime(n+1) that is not a(n)^2 mod prime(i) for i <= n, and using Chinese Remainder Theorem find x such that x == a(n) (mod prime(i)) for i <= n and x^2 == r (mod prime(n+1)), and then a(n+1) <= x.  In particular a(n) exists for all n.

%e a(5) = 3 because 3^2 mod 2 = 1, 3^2 mod 3 = 0, 3^2 mod 5 = 4, 3^2 mod 7 = 2 and 3^2 mod 11 = 9 are all distinct, while this is not the case for 1^2 or 2^2 (e.g. 2^2 mod 5 = 2^2 mod 7 = 4).

%p P:= NULL:

%p v:= 1:

%p for n from 1 to 35 do

%p   P:= P ,ithprime(n);

%p   for k from v do

%p     if nops({seq(k^2 mod P[i],i=1..n)}) = n then

%p       v:= k;

%p       A[n]:= k;

%p       break

%p     fi

%p   od

%p od:

%p seq(A[n],n=1..35);

%o (PARI) isok(k, n) = my(v=vector(n, j, lift(Mod(k, j)^2))); #v == #Set(v);

%o a(n) = {my(k=1); while(!isok(k, n), k++); k;} \\ _Michel Marcus_, Jul 12 2019

%Y Cf. A279073.

%K nonn

%O 1,2

%A _Robert Israel_, Jul 11 2019