10
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
  • 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
  • 7
    $\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
14
$\begingroup$

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for a general method $\endgroup$ – Ramchandra Apte 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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Or, $ $ mod $\,p\!:\ x\equiv 0\,\Rightarrow\, x+1\equiv 1\not\equiv 0\ $ (else $\,p\mid 1-0)\ \ \ $ $\endgroup$ – Gone 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.