Let $n>30$. Then prove there exists a natural number $1 $(m,n)$ denotes the greatest common divisor of $m$ and $n$.
Thanks
Let n>30. Then prove there exists a natural number $ 1< m\leq n$ such that $(n,m)=1$ and $m$ is not prime.
-
0Why are you requiring $n\gt30$? – 2012-11-27
-
0this is not true for $n<30$ – 2012-11-27
-
2@elham It is definitely true, as stated, for $n<30$. – 2012-11-27
-
1Perhaps you intended to include the condition $m\lt n$ and forgot? – 2012-11-27
-
1@joriki Ah, that's probably it. – 2012-11-27
-
1Note, as stated, $m=1$ works for all $n$. $1$ is a natural number, $1$ is not prime, and $(1,n)=1$ for all $n$. – 2012-11-27
-
0I took the liberty to make the inequality $1
– 2012-11-27
3 Answers
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
Take $m=p^2$.
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
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$
-
0You don't even need two of them... – 2012-11-27
-
0@ThomasAndrews: true enough. – 2012-11-27