# Numbers only coprime to prime numbers

January 21, 2010 1 Comment

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

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

*then*

**N***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.*

**k**In general, * N* cannot be coprime to any

*such that , as this would imply that it is coprime to*

**p**

**p**^{2}and so imply that

*is prime, which it cannot be! Hence*

**p**^{2}*has as factors all prime numbers up to its square root. (The square root of 18 is about 4.2.)*

**N**Let us enumerate the primes so that p_{n} is the largest prime smaller (or equal) to the square root of * N*:

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

It follows that:

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

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

**and**

*t**. In particular this means that:*

**2t**and so we can deduce the following bound:

Applying that to the inequality above, we have:

Therefore, simplifying, * n* must satisfy:

Since:

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.

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