8
$\begingroup$

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

$\endgroup$
20
  • 2
    $\begingroup$ $n(11)=211$, I think. $\endgroup$ Jun 26, 2013 at 1:21
  • 2
    $\begingroup$ We have $n(13) = n(17) = 716$, while $\sqrt{P(17)} \approx 714$. -- Thus for $x = 17$ your inequality is pretty sharp. $\endgroup$
    – Stefan Kohl
    Jun 26, 2013 at 9:51
  • 3
    $\begingroup$ 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. $\endgroup$ Jun 26, 2013 at 12:07
  • 1
    $\begingroup$ 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$? $\endgroup$ Jun 27, 2013 at 3:09
  • 3
    $\begingroup$ Are all the extra spaces (\quad, \ ,  ) really necessary? $\endgroup$ Jun 29, 2013 at 12:28

3 Answers 3

6
$\begingroup$

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;
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jun 26, 2013 at 12:00
  • 1
    $\begingroup$ 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 $\endgroup$ Jun 27, 2013 at 3:29
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 27, 2013 at 5:54
  • $\begingroup$ @Gerry, our own MO Stefan Kohl got further than OEIS! Good reflex and association, Gerry, great links--thank you. $\endgroup$ Jun 27, 2013 at 7:21
4
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 26, 2013 at 11:37
  • $\begingroup$ 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. $\endgroup$
    – Waldemar
    Jun 26, 2013 at 12:05
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2013 at 1:56
  • $\begingroup$ 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$$ $\endgroup$
    – Waldemar
    Jul 1, 2013 at 8:44
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.