11
$\begingroup$

Given $\{x \mid x > 1\}$, how do I prove that any given $x$ and $x+1$ are coprime?

$\endgroup$
1
  • 8
    $\begingroup$ $p \mid x,x+1 \Longrightarrow p \mid 1$. $\endgroup$
    – njguliyev
    Nov 2 '13 at 17:35
36
$\begingroup$

If $y$ divides $x$ and $x+1$ then it divides $(x+1)-x=1$. Conclude.

$\endgroup$
4
  • 1
    $\begingroup$ "If y divides x and x+1 then it divides (x+1)−x=1." Why is this true? $\endgroup$
    – Kevin
    Nov 2 '13 at 22:14
  • 8
    $\begingroup$ If $y$ divides $x$ and $x+1$ then there's $a$ and $b$ such that $x=ay$ and $x+1=by$ then $(x+1)-x=(b-a)y$ so... Do you understand? $\endgroup$
    – user63181
    Nov 2 '13 at 22:19
  • 1
    $\begingroup$ Nice! A one-liner kills the question! $\endgroup$
    – amWhy
    Mar 6 '14 at 13:51
  • 1
    $\begingroup$ Nice and concise. $\endgroup$
    – drhab
    Jun 12 '14 at 20:18
15
$\begingroup$

$\gcd(x,x+1)=\gcd(x,x+1-x)=\gcd(x,1)=1$.

Hence $x$ and $x+1$ are coprime.

$\endgroup$
1
  • $\begingroup$ +1 for a general method $\endgroup$ Nov 3 '13 at 7:14
3
$\begingroup$

If $x$ is a multiple of $p$, then the next multiple of $p$ is $x+p$, but that's clearly larger than $x+1$.

$\endgroup$
1
  • $\begingroup$ Or, $ $ mod $\,p\!:\ x\equiv 0\,\Rightarrow\, x+1\equiv 1\not\equiv 0\ $ (else $\,p\mid 1-0)\ \ \ $ $\endgroup$ May 31 '14 at 16:53

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.