# Relatively prime numbers are prime

The problem is to find all numbers $n$ such that all numbers $k>1$ smaller than $n$ and coprime with $n$ are prime.

• Do you have examples of such $n$ which are not too small? – AdLibitum Jul 3 '17 at 9:58
• The two formulations differ in meaning though: The only number $1<k<n$ coprime to $n=6$ is $k=5$, but $\phi(6)-1=4\ne 3=\pi(6)$ – Hagen von Eitzen Jul 3 '17 at 9:59
• @HagenvonEitzen Yep sorry, it is the non mathematical way... – Maths4F Jul 3 '17 at 10:01
• @HagenvonEitzen But I have to find all $n$ such that it is the case! – Maths4F Jul 3 '17 at 10:01

Let $n$ have the property and let $p$ be the smallest prime not dividing $n$. Then $n<p^2$ as otherwise $\gcd(p^2,n)=1$ destroys the property. On the other hand, this implies that $n$ is a multiple of the product of all primes $<p$.
For $p\ge13$, by Bertrand's postulate, the prime preceding $p$ is $>\frac p2$ and the one preceding that is $>\frac p4$ (and $>5$). Hence $p^2>2\cdot 3\cdot5\cdot \frac p4\cdot\frac p2=\frac{15}{4}p^2$, contradiction.
But also for $p=11$, we find $11^2=121>2\cdot3\cdot 5\cdot 7=210$, contradiction.
For $p=7$, we only get $n<49$ and $2\cdot3\cdot 5=30\mid n$,. Instead of a contradiction, this implies $n=30$. We verify that this does indeed have the property.
For $p=5$, we get $6\mid n<25$, so $n\in\{6,12,18,24\}$. For $p=3$, we get $2\mid n<9$, so $n\in\{2,4,6,8\}$. For $p=2$, we get $n<4$.
In summary: The $n$ with this property are precisely $$n\in\{1,2,3,4,6,8,12,18,24,30\}.$$