4
$\begingroup$

Show that only finitely many positive integers $n$ have the property that for all $m$ for which $1<m<n$ and $\text{gcd}(m,n) = 1$, $m$ is prime.

I am able to show that a positive integer with the specified property is prime, but I do not know how to prove that there are "finitely many" of them.

EDIT: Adding a proof of the mentioned claim that "a positive integer with the specified property is prime."

If $m$ is prime $m$ has no factors but $1$ and $m$. So gcd$(m,n)$ can only equal 1 or $m$. If gcd$(m,n) = m$ then $m|n$. So $n \ge m$. If $n < m$ then gcd$(m,n)=1$. Conversely, if gcd$(m,n)=1$ for all $n < m$, then no number less than $m$ divides $m$ (other than $1$). Since no number larger than $m$ divides $m$, $m$ has no divisors except itself and $1$. So $m$ is prime.

$\endgroup$
  • $\begingroup$ Please include the details of what you've done. You might be closer than you think! $\endgroup$ – Shaun Mar 3 '18 at 23:19
  • 2
    $\begingroup$ Such an $n$ is rarely prime. The only primes with this property are $2$ and $3$, all larger ones - like $6$ - are composite. $\endgroup$ – Daniel Fischer Mar 3 '18 at 23:21
  • 1
    $\begingroup$ @Shaun I added a proof of a claim I mentioned. $\endgroup$ – Dominated Convergence Theorem Mar 3 '18 at 23:29
  • 4
    $\begingroup$ You misunderstood. It's $n$ that is fixed. $6$ has the property, because the only $1 < m < 6$ which is coprime to $6$ is $m = 5$, which is prime. $n = 7$ doesn't have the property, because the $1 < m < 7$ coprime to $7$ are $2,3,4,5,6$, of which $4$ and $6$ aren't prime. $\endgroup$ – Daniel Fischer Mar 3 '18 at 23:38
  • 2
    $\begingroup$ Adding on to @DanielFischer's clarifying comment: Consider $n = 8$. The numbers in question (bigger than one, less than $n$, coprime with $n$) are: $3$, $5$, and $7$, which are all prime. And so $n = 8$ serves as another among the finitely many positive integers with the desired property. $\endgroup$ – Benjamin Dickman Mar 3 '18 at 23:43
8
$\begingroup$

I know that your proof is incorrect, since we have counterexamples, but I will leave that to others to debate. We will concentrate on the other question, which is better.


First, let us give a name to the property of a natural number $n$ : "For all $1 <m < n$ such that $\gcd(m,n) = 1$, $m$ is prime". For fun, I say $n$ satisfies the orange juice property if it satisfies this condition.

For example, $30$ has the orange juice property, since the numbers smaller than $30$ which are relatively prime to $30$, are just the primes below $30$ other than $2,3,5$ i.e. $7,11,13,17,19,23,29$. You can check that every other $1<m<n$ actually shares a common factor with $n$.

Why is this happening? Essentially, this is because $7^2 > 30$.


In more detail, let $p_1(n)$ be the smallest prime which doesn't divide $n$. Then, we know that $p_1^2(n)$ is a composite number, which is coprime to $n$.

I claim that for large enough $n$, we have $p_1^2(n) < n$. Note that if this statement is true, then for large enough $n$, $p_1^2(n)$ is a composite number which is coprime to $n$, so $n$ does not have the orange juice property.


Why is the claim true? It follows from the fact that $n$ is at least greater than or equal to the product of all the primes before $p_1$, since that is the definition of $p_1$, and in some sense, consecutive primes are not too far apart. We'll prove it below, though.

Let us use Bertrand's postulate (it's called a postulate but it is a true statement), which says that for any $k>3$ there is a prime in the range $k < p < 2k - 2$. Its proof is elementary in the least (Erdos provided a proof at the age of $19$) but I shall not mention it here.

We'll go right into the proof, then.


Claim : Let $p_i$ denote the $i$th smallest prime. Then, for large enough $i$ (actually, I think $i \geq 5$), we have $p_i^2 < \prod_{j=1}^{i-1} p_j$.

Proof : Let us do this by induction, starting from a base case derived by experiment. $p_5 = 11$, and $p_5^2 = 121 < 2\cdot 3 \cdot 5 \cdot 7 = 210$.

Now, assume the statement true for $n$. So it is true that $p_n^2 < \prod_{i=1}^{n-1} p_i$. We want to show, that $p_{n+1}^2 < \prod_{i=1}^{n} p_i$.

Use Bertrand's postulate to see that $p_{n+1} < 2p_n$, since there is some prime between $p_n$ and $2p_n$, but $p_{n+1}$ has to be less than or equal to that prime. Now, it follows that $p_{n+1}^2 \leq 4p_n^2$, and therefore: $$ p_{n+1}^2 < 4p_n^2 < 4\prod_{i=1}^{n-1} p_i < \prod_{i=1}^{n} p_{i} $$

completing the proof.


Let $\{p_1,...,p_k\}$ be the set of primes dividing $n$ (only the set : we don't count multiplicities. For example, the set for a power of $2$ is just the set $\{2\}$).

Then, $p_1(n)$ is the smallest prime not dividing $n$, so $p_1(n)$ is the $k$th smallest prime for some $k \geq 1$.

Suppose $n$ had the orange juice property. Then, we must have $n \geq \prod_{i=1}^{k-1} p_i$, but then $p_k^2 > n$, since it is coprime to $n$. But, this forces: $$ \prod_{i=1}^{k-1} p_i \leq n < p_k^2 $$

It follows, from the claim that $k \leq 4$. So, $n < 7^2 = 49$ is forced from the above statement.

Hence, there are only finitely many numbers satisfying the orange juice property. They are all less than $49$.


Now, here's a modification : let $n$ have the mango juice property, if for all $m$ such that $1 < m < n$ and $m$ is coprime to $n$, $m$ is either a prime, or a semiprime i.e. a product of primes. Then, I think that using similar bounds and not much stronger inequalities, we can also prove that numbers having the mango juice property must be upper bounded.

In similar vein, the creation of other fruit juice properties, allowing $m$ to be say composed of $3$ primes, or of squares of primes etc. can be dealt with in this way, I would think. It seems fun to experiment with these.

$\endgroup$
  • $\begingroup$ Does $30 < n < 49$ satisfy this property? For all odd numbers in this range, $(4,n) = 1$ is a counter example. For all even numbers, 32, 34, 36, 38, 40, 42, 44, 46, 48, the counter examples are either 25 or 9. $\endgroup$ – sku Mar 4 '18 at 22:30
  • $\begingroup$ @sku Yes, you are right. Note that every number between $30$ and $49$ either has $p_1(n) = 2,3$ or $5$, and each of these has square less than $25$, so they sort themselves out that way. $\endgroup$ – астон вілла олоф мэллбэрг Mar 5 '18 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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