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

<br /><hr />

**PROOF of the THEOREM**

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

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

Furthermore, &nbsp; $2|n-1$ &nbsp; or &nbsp; $2|n-2$, &nbsp; hence &nbsp; $A'|n-1$ &nbsp; and &nbsp; $B'|n-2$ &nbsp; 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 $$