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

  • $\begingroup$ Do you have examples of such $n$ which are not too small? $\endgroup$ – AdLibitum Jul 3 '17 at 9:58
  • $\begingroup$ 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)$ $\endgroup$ – Hagen von Eitzen Jul 3 '17 at 9:59
  • $\begingroup$ @HagenvonEitzen Yep sorry, it is the non mathematical way... $\endgroup$ – Maths4F Jul 3 '17 at 10:01
  • $\begingroup$ @HagenvonEitzen But I have to find all $n$ such that it is the case! $\endgroup$ – 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\}.$$


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.