Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Why are you requiring $n\gt30$? –  joriki Nov 27 '12 at 14:13
2  
@elham It is definitely true, as stated, for $n<30$. –  Thomas Andrews Nov 27 '12 at 14:15
1  
Perhaps you intended to include the condition $m\lt n$ and forgot? –  joriki Nov 27 '12 at 14:17
1  
@joriki Ah, that's probably it. –  Thomas Andrews Nov 27 '12 at 14:20
1  
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
show 2 more comments

3 Answers 3

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|improve this answer
add comment

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.