3
$\begingroup$

Let $n>30$. Then prove there exists a natural number $1

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

  • 0
    Why are you requiring $n\gt30$?2012-11-27
  • 0
    this is not true for $n<30$2012-11-27
  • 2
    @elham It is definitely true, as stated, for $n<30$.2012-11-27
  • 1
    Perhaps you intended to include the condition $m\lt n$ and forgot?2012-11-27
  • 1
    @joriki Ah, that's probably it.2012-11-27
  • 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$.2012-11-27
  • 0
    I took the liberty to make the inequality $12012-11-27

3 Answers 3

4

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 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$.

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

  • $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
1

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$

  • 0
    You don't even need two of them...2012-11-27
  • 0
    @ThomasAndrews: true enough.2012-11-27