Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
$n(11)=211$, I think. –  Gerry Myerson Jun 26 '13 at 1:21
2  
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
3  
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
1  
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
2  
Are all the extra spaces (\quad, \ ,  ) really necessary? –  Nate Eldredge Jun 29 '13 at 12:28

3 Answers 3

up vote 6 down vote accepted

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;
share|improve this answer
    
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
1  
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
2  
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$$

share|improve this answer
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 $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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