# About the property of $m$: if $n < m$ is co-prime to $m$, then $n$ is prime [duplicate]

The number $30$ has a curious property:

All numbers co-prime to it, which are between $1$ and $30$ (non-inclusive) are all prime numbers!

I tried searching(limited search, of course) for numbers $\gt 30$ that have this property, but could not find any.

Are there any such numbers $\gt 30$?

The reason why is that $30=2\cdot 3\cdot 5$, which are consecutive primes, so any number less than $30$ must not be divisible by these $3$ numbers to be coprime. If they are to be coprime but not prime themselves, then they would have to be divisible by another two primes (including multiplicities), and the least such one is $7$. But $2\cdot 3\cdot 5<7^2$.

Such numbers (products of consecutive primes) are called primorials, and they grow too quickly for this to happen again for any number above $30$ (for example, the next number is $210$, but $210=2\cdot 3\cdot 5\cdot 7$ and $121=11^2$ are coprime). You can see the OEIS listing to see the first few primorials, which would be candidates for the property you're searching for, to see just how large they get.

Let $n>30$ be such a number. Observe that $p^2<n$ implies $p|n$. Thus $2|n$, $3|n$, $5|n$ follow directly from $n>25>9>4$. Thus $n$ is a multiple of $30$ and $n>30$, which implies $n\ge 60>49$ and hence $7|n$. Up to now, $n$ is divisible by the four smallest primes.

Lemma. The product of four consecutive primes is greater than the square of the next prime: $$\tag1p_kp_{k+1}p_{k+2}p_{k+3}> p_{p+4}^2.$$

Proof: Using Bertrand's postulate, we have $p_{k+2}>\frac{p_{k+3}}2$, and $p_{k+4}\le 2p_{k+2}$, hence $(1)$ follows from $$p_kp_{k+1}p_{k+2}p_{k+3}>3\cdot 5\cdot \frac{p_{k+3}}{2}p_{k+3}> 4p_{k+3}^2>p_{k+4}^2$$ at least if $p_k\ge 3$. The case $p_k=2$ is verified directly: $2\cdot3\cdot 5\cdot 7>11^2$. $_\square$

Now if $n$ is divisible by four consecutive primes $p_k,\ldots,p_{k+3}$, we conclude from $(1)$ that $n$ is also divisible by the next prime, because otherwise $p_{k+4}^2<n$ is relatively prime to $n$. Hence $n$ is divisible by the four consecutive primes $p_{k+1},\ldots,p_{k+4}$. By induction, we conclude that $n$ is divisible by all primes, but that is of course absurd. Hence there is no such number beyond $30$.

• Correcting some typos in the subscripts in this great answer: $p_{k+4}\leq 2p_{k+3}$ (actually strict, as used one line below) and $p_{p+3}^2$ means $p_{k+3}^2$. May 21, 2013 at 18:17
• @ccorn Yes, there are some trivial strictnesses implied by primality. I just wanted to use the formulation of Bertrand a the linked WP page - where $\le$ is owed to the single case $n=1<p=2\le 2n$. May 21, 2013 at 22:13
• Sorry for mentioning the strictness at all. The first inequality I mentioned mainly not because of the strictness, but because a subscript in there needs a correction. (Actually I tried to edit your post, and a script said, changes must amount to at least 6 characters -- in other words, you have not left enough typos!) May 21, 2013 at 23:07

Let $$\, p_i\,$$ be the $$i$$'th prime. Many proofs (e.g. below) use $$\, p_{n+1}\! < 2 p_n\,$$ (by Bertrand) to prove that $$\,p_{k+1}^2\! < p_1 p_2 \cdots p_k.\:$$ It is worth remarking that this follows from a much weaker hypothesis than that of Bertrand. Rather, we need only $$\ \color{#c00}{p_{k+1}\! < p_k^{3/2}}.\$$ Then the inductive step is

\begin{align} \qquad\ p_k^2 &< p_1 p_2 \cdots p_{k-1} \\ p_{k+1}^2/p_k^2 &< p_k\ \ \ {\rm by}\ \ \ \color{#c00}{p_{k+1} < p_k^{3/2}},\ \ \ \text{by hypothesis}\\[.2em] \Rightarrow \ \ \quad p_{k+1}^2 &<\, p_1 p_2 \cdots p_k\ \ \ \text{by multiplying the above} \end{align}\qquad\qquad

What is the simplest proof of this weaker hypothesis: $$\ p_{k+1}\! < p_k^{3/2}\,$$ for $$\, k > 1$$?

Below is a typical proof of said form, from PlanetMath.

• $\pi(x^3)>\pi(x^2)$ follows already from relatively simple estimates $c_1\frac x{\ln x}<\pi(x)<c_2\frac x{\ln x}$ about the prime counting function as that gives us $\pi(x^3)>\frac{c_1}{3}\frac{x^3}{\ln x}>\frac{c_2}2\frac{x^2}{\ln x}>\pi(x^2)$ as soon as $x>\frac{3c_2}{2c_1}$. May 22, 2013 at 6:23

There are no larger numbers, for which all the coprimes are primes. While 30 itself is the largest such number, there are no multiples of 30 that contain eight primes, however, there are intervals of the form 30n+/-15, which do contain eight primes (such as around 1230).

The largest base that contains 'prime decades' is 18. A prime decade is where all the co-primes exist between two multiples of the base are all prime. For example, in decimal, the co-primes $101, 103, 107, 109$ are all prime. Likewise, there are four primes $8.1, 8.5, 8.7, 8.11$ in base 12, are also prime.

In $base 18$, they are very rare, but do exist. The second smallest starts with $43776$, and runs $7.9.2.1$, $7.9.2.5$, $7.9.2.7$, $7.9.2.11$, $7.9.2.13$, $7.9.2.17$ are all prime. They are supprisingly rare.