**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 $$

`\quad`

,`\`

,` `

) really necessary? $\endgroup$ – Nate Eldredge Jun 29 '13 at 12:28