Numbers only coprime to prime numbers

Here is a little puzzle: Suppose N is a number such that it is only coprime to prime numbers. That is,

\rm{If}\: 1 < k \le N \:\rm{and}\:GCD(k,N)=1\:\rm{then}\:k \rm{ \: is\: prime}

An example of one of these numbers is 18. 18 is coprime to 1, 5, 7, 11, 13, 17.  1 doesn’t count, and the rest are prime.

Can we find an upper bound for N?

The first thing to look at is the behaviour of primes. The condition only says if k it is coprime to N then k is prime, not that all prime numbers are coprime to it. For instance, 18 is not coprime to 2 or 3. It couldn’t be coprime to 2, as then it would be coprime to its square, 4, and by definition it cannot be as 4 is not prime. Similarly with 3.

In general, N cannot be coprime to any p such that p^2 \le N, as this would imply that it is coprime to p2 and so imply that p2 is prime, which it cannot be! Hence N has as factors all prime numbers up to its square root. (The square root of 18 is about 4.2.)

Let us enumerate the primes so that pn is the largest prime smaller (or equal) to the square root of N:

p_1 < p_2 < p_3 < ... < p_n \le \sqrt{N} < p_{n+1}

Therefore, from what was said above all, we must have:

p_1 p_2 p_3 \dots p_n \:|\: N

It follows that:

p_1 p_2 p_3 \dots p_n \le N < p_{n+1}^2

And so we need to find an upper bound on the values of n for which we can have:

p_1 p_2 p_3 \dots p_n < p_{n+1}^2

This is a question about the gaps between primes, and so maybe we should use Bertrand’s Postulate. This states that for any number t, there is a prime between t and 2t. In particular this means that:

p_{n+1} < 2p_n \mbox{ and } p_n < 2p_{n-1}

and so we can deduce the following bound:

p_n p_{n-1} > \left(\frac{p_{n+1}}{2}\right) \left(\frac{p_n}{2}\right) > \left(\frac{p_{n+1}}{2}\right) \left(\frac{p_{n+1}}{4}\right) = \frac{p_{n+1}^2}{8}

Applying that to the inequality above, we have:

p_1 \dots p_{n-2} \left(\frac{p_{n+1}^2}{8}\right) < p_{n+1}^2

Therefore, simplifying, n must satisfy:

p_1 \dots p_{n-2} < 8


p_1 p_2 = 6 \qquad p_1 p_2 p_3 = 30

It follows that n is at most 4. Therefore the square root of N may be no larger than the square of the fifth prime, 11. Thus we have that N < 121

Using a computer program it is now easy to find the full list of possible values of N. They are: 3, 4, 6, 8, 12, 18, 24, 30.


One Response to Numbers only coprime to prime numbers

  1. Jamie says:

    I gave it a go, but you lost me around the “Here is a little puzzle” part.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: