**NOTATION**:   $P(x)$   stands for the product of all primes which do not exceed real   $x$;   e.g.   $P(10)=210$.


**QUESTION**:   Given any real   $x\ge 3$,   compute or estimate the smallest natural number   $n:=n(x)\ge 3$   such the remainder of the division of   $n$   by any odd prime   $p\le x$   is   $1$ or $2$   (it may be any combination of   $1$s   and   $2$s).


In particular, improve upon my simple theorem below, and still better upon its consecutive improvements provided by the MO participants.


**THEOREM**
$$ n(x)\ > \ \left\lceil\sqrt{P(x)}\right\rceil + 1 $$


**EXAMPLEs** (small calculations):


* $n(3) = 4$
* $n(5) = 7$
* $n(7) = 16$


**REMARK (warning)**: First I talk about **all** primes (see **NOTATION**), then about **odd** primes (see **QUESTION**).


  


---




**PROOF of the THEOREM**


Let integer   $n\ge 3$   be such that all mentioned remainders are   $1$   or   $2$.   Let   $A$   be the product of all odd primes   $p\le x$   for which   $n=1\mod p$, and   $B$   be the same for remainder   $2$.   Thus   $A|n-1$   and   $B|n-2$,   and


$$A\cdot B\ =\ \frac{P(x)}2 $$


Furthermore,   $2|n-1$   or   $2|n-2$,   hence   $A'|n-1$   and   $B'|n-2$   for certain natural numbers such that


$$ A'\cdot B'\ =\ P(x) $$


It follows that


$$ n\ \ \ge\ \ \max(A'\ B') + 1$$


while


$$ \max(A'\ B')\ \ \ge\ \ \left\lceil\sqrt{A'\cdot B'}\right\rceil\ \ =\ \ \left\lceil\sqrt{P(x)}\right\rceil $$


This proves the required inequality:


$$ n\ \ \ge\ \ \left\lceil\sqrt{P(x)}\right\rceil + 1 $$



Remainders $\quad 1\quad 2\quad $ only
The values $n(p)$ for primes $13 \leq p < 100$, found by computation: $n(13) = n(17) = 716$,
$n(19) = 62987$,
$n(23) = 367082$, $n(29) = 728366$, $n(31) = 64822396$, $n(37) = 1306238012$,
$n(41) = 11182598506$, $n(43) = 715041747422$, $n(47) = 51913478860882$,
$n(53) = 454746157008782$, $n(59) = 9314160363311806$, $n(61) = n(67) = 261062105979210901$,
$n(71) = 696537082207206753592$, $n(73) = 54097844397380813592487$,
$n(79) = 286495021083846822067822$, $n(83) = 80126789479717708423427656$,
$n(89) = 1560127578864999430859224576$, $n(97) = 161426380685234430031618378951$.


**Edit:** For completeness -- the [GAP](http://www.gap-system.org) code for computing these values
is as follows:



```
n := function ( x )

  local  primes, remainders, solutions;

  primes     := Filtered([3..x],IsPrime);
  remainders := Tuples([1,2],Length(primes));
  solutions  := List(remainders,rem->ChineseRem(primes,rem));
  return Minimum(Difference(solutions,[1,2]));
end;

```

