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

1, 2, 2, 3, 3, 172, 213, 213, 333, 333, 1228, 1438, 2152, 3832, 3832, 3832, 5792, 22732, 22732, 37342, 37342, 37342, 37342, 37342, 545408, 629247, 629247, 629247, 629247, 629247, 629247, 629247, 629247, 1423713, 8136838, 8136838

Offset: 1

Author

Robert Israel, Jul 11 2019

Keywords

• nonn

Comments

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.

Examples

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

Crossrefs

Cf. A279073.

Programs

Maple

P:= NULL:
v:= 1:
for n from 1 to 35 do
  P:= P ,ithprime(n);
  for k from v do
    if nops({seq(k^2 mod P[i],i=1..n)}) = n then
      v:= k;
      A[n]:= k;
      break
    fi
  od
od:
seq(A[n],n=1..35);

PARI

isok(k, n) = my(v=vector(n, j, lift(Mod(k, j)^2))); #v == #Set(v);
a(n) = {my(k=1); while(!isok(k, n), k++); k;} \\ Michel Marcus, Jul 12 2019