Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n>30$. Then prove there exists a natural number $1<m\leq n$ such that $(n,m)=1$ and $m$ is not prime.

$(m,n)$ denotes the greatest common divisor of $m$ and $n$. Thanks

share|cite|improve this question
Why are you requiring $n\gt30$? – joriki Nov 27 '12 at 14:13
@elham It is definitely true, as stated, for $n<30$. – Thomas Andrews Nov 27 '12 at 14:15
Perhaps you intended to include the condition $m\lt n$ and forgot? – joriki Nov 27 '12 at 14:17
@joriki Ah, that's probably it. – Thomas Andrews Nov 27 '12 at 14:20
Note, as stated, $m=1$ works for all $n$. $1$ is a natural number, $1$ is not prime, and $(1,n)=1$ for all $n$. – Thomas Andrews Nov 27 '12 at 14:22

Since $30=2\cdot3\cdot5$ and $2^2,3^2,5^2<30$ it's enough to consider the case $30\mid n$ (if not take $m=2^2$ or $m=3^2$ or $m=5^2$). Assume that to be the case.

Let $p$ be the smallest prime with $p\nmid n$. Then $(n,p^2)=1$ and $p^2<n$.
This is because $31$ is the largest primorial prime less than the next prime(of the primes in the primorial) squared (see this and for a proof Hagen von Eitzen's answer).
Take $m=p^2$.

share|cite|improve this answer

Let $p_k$ be the largest prime for which $n$ is divisible by $p_k\#=2\cdot 3\cdot 5\cdot\ldots\cdot p_{k-1}\cdot p_k$. Clearly $(n,m)=1$ if we let $m=p_{k+1}^2$. We need to show that $m<n$. By the Bertrand postulate, $\frac12p_k<p_{k-1}<p_k<p_{k+1}<2p_k$. But this follows from $m<4p_k^2$ and

  • $n\ge p_k\#\ge 30p_{k-1}p_k> 15p_k^2$ if $p_k\ge 11$
  • $n\ge p_k\# = 210>11^2=m$ if $p_k=7$
  • $30|n$ and $n>30$, hence $n\ge 60$, and $m=49$ if $p_k=5$
  • $m\le 25<n$ if $p_k\le 3$
share|cite|improve this answer

Hint: do you know a proof that there are an infinite number of primes? If you find two of them not factors of $n, \dots$

share|cite|improve this answer
You don't even need two of them... – Thomas Andrews Nov 27 '12 at 14:12
@ThomasAndrews: true enough. – Ross Millikan Nov 27 '12 at 14:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.