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.

Solution 1:

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.