# Remainders $\quad 1\quad 2\quad$ only

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

-
$n(11)=211$, I think. – Gerry Myerson Jun 26 '13 at 1:21
We have $n(13) = n(17) = 716$, while $\sqrt{P(17)} \approx 714$. -- Thus for $x = 17$ your inequality is pretty sharp. – Stefan Kohl Jun 26 '13 at 9:51
What's going on with 716 reminds me of the "Ruth-Aaron pair", 714 and 715; $714=2x3x7x17$, $715=5x11x13$ (and $2+3+7+17=5+11+13$, although that's not relevant here). Also brings to mind Stormer's Theorem, about consecutive smooth numbers. – Gerry Myerson Jun 26 '13 at 12:07
I mean, we also have $2\times3=P(3)$, $5\times6=P(5)$, $14\times 15=P(7)$, but are there any instances with $k\ge19$? – Yoav Kallus Jun 27 '13 at 3:09
Are all the extra spaces (\quad, \ , &nbsp;) really necessary? – Nate Eldredge Jun 29 '13 at 12:28

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 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;

-
Let $p<q$ be consecutive odd primes. If $$\frac{n(q)}{n(p)}<\sqrt q$$ then--by definition--the jump is low; otherwise the jump is high (the inequality is always sharp). It seemed to me that low/high depends (but not consistently) on the $\mod 4$ class of $q$. When $q=3\mod 4$ then the jump is either extra low or extra high depending on the parity of the number of primes $s < q$ which are congruent to $3\mod 4$. Your, @Stefan, list seems to confirm this conjecture. There should be also other considerations which occasionally mess up this tendency; it still should be the most common tendency. – Włodzimierz Holsztyński Jun 26 '13 at 12:00
Here are the ratios $[n(p)-1][n(p)-2]/P(p)$ (necessarily integers) for $p=3,5,\ldots,97$: 1, 1, 1, 19, 17, 1, 409, 604, 82, 20951, 229931, 411012, 39080794, 4382914408, 6345486566, 45119290746, 581075656330, 8672770990, 869561574799171, 71853663603175593, 25509154378676494, 24040267482771436703, 102403319155457392955, 11302410854347731819765 – Yoav Kallus Jun 27 '13 at 3:29
The numbers $n(p)-2$ are tabulated at oeis.org/A118478 and the ratios are tabulated at oeis.org/A215021 but neither page has anything about rate of growth. – Gerry Myerson Jun 27 '13 at 5:54
@Gerry, our own MO Stefan Kohl got further than OEIS! Good reflex and association, Gerry, great links--thank you. – Włodzimierz Holsztyński Jun 27 '13 at 7:21

Speculatively, as for now, we could assume that the smallest difference between $n(x)$ and $\sqrt{P(x)}$ is for $x=17$ (see Stefan's comment). Thus, a natural improvement to your theorem (conjecture?) could be the following: $$n(x)\geq P(x)^{a}$$ Where $a=\log_p716$ and $p=510510$, so $a\approx 0.50016$

Or simpler: $$n(x)\ > \ \sqrt{P(x)}+1$$

-
your first inequality is an interesting conjecture. The second one I had from the beginning, and just somehow neglected to type it in full (just psychology or funny laziness). Yes, it's a theorem, not just a conjecture. Indeed, actual inequality is $$n(x)\ge\left\lceil\sqrt{P(x)}\right\rceil+1$$ Its proof is very simple. – Włodzimierz Holsztyński Jun 26 '13 at 11:37
Thus, referring to your original question, as we know a case for $x=17$ we can conclude that, in general, the inequality $$n(x)\ge\left\lceil\sqrt{P(x)}\right\rceil+1$$ cannot be improved. – Waldemar Jun 26 '13 at 12:05
Thank you, @Waldemar, that's pleasing. To celebrate it I'll add the proof of my small theorem to my "Question". On the other hand one still can strive at getting sharper results, e.g. for $x > M$ (say, for $x \ge 19 :-) or other forms. – Włodzimierz Holsztyński Jun 27 '13 at 1:56 It could also be of interest to find an upper bound for$n(x)$which would be an improvement over the following one: $$n(x)\leq \frac{P(x)}{2}+1$$ – Waldemar Jul 1 '13 at 8:44 Let me make a tiny-microscopic improvement. Let$n := n(x)\$.   Then

$$P(x)\ |\ (n-1)\cdot(n-2)\ =\ \left(n-\frac 32\right)^2 - \frac 14$$

It follows that:

THEOREM

$$n(x)\quad \ge\quad \left\lceil\sqrt{P(x)+\frac 14}\ +\ \frac 32\right\rceil$$

-