7
$\begingroup$

Let $n \in \mathbb Z$ be even. Then $n + 1$ is odd. So, $2$ doesn't divide $n + 1$. Thus there's no even number for which $\gcd(n, n+1)$ is not $1$. I am not sure how to show it for odd numbers. Is there a better way to prove the statement?

$\endgroup$
  • 1
    $\begingroup$ Note that an even number can still have a factor in common with an odd number, e.g., $6$ and $9$. In other words, showing that $2$ doesn't divide $n+1$ isn't a valid argument that $n$ and $n+1$ have no common factors. $\endgroup$ – Théophile Aug 8 '15 at 2:27
18
$\begingroup$

Let $a$ and $b$ be integers.

Any integer that divides both $a$ and $b$ must also divide their difference (can you see why this is?).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Let $n = ak$ and $n + 1 = aj$. Then $n - n - 1 = -1 = a(k - j)$. But $a$ doesn't divide $-1$? $\endgroup$ – user259324 Aug 8 '15 at 2:35
  • $\begingroup$ You're going at it a little backwards. We want find a divisor $d$ of the difference $a-b$ first, and then use the fact I posted to conclude that $d$ must also divide $a$ and $b$. (For your particular problem we can set $a = n+1$ and $b = n$.) $\endgroup$ – 727 Aug 8 '15 at 2:45
  • $\begingroup$ Also just an FYI, the fact I posted is the basis of the Euclidean Algorithm, which is an ancient, simple, and efficient method to compute the GCD of two integers. en.wikipedia.org/wiki/Euclidean_algorithm $\endgroup$ – 727 Aug 8 '15 at 2:48
  • 1
    $\begingroup$ $1 = aj$ for some $j$. So $a$ can't be anything other than $1$ which divides both $n, n + 1$. Like that? $\endgroup$ – user259324 Aug 8 '15 at 2:49
  • 1
    $\begingroup$ $d|a, d|b \to d|(a - b)$. Since $a - b = n + 1 - n = 1$, $d|1$. Then $d$ must be $1$? $\endgroup$ – user259324 Aug 8 '15 at 3:03
6
$\begingroup$

Suppose $\gcd(n,n+1)=d>1$ for some $n\in\mathbb{N}$. Then by Bezout's identity, there are $a,b\in\mathbb{Z}$ such that $$an+b(n+1)=d\Rightarrow (a+b)n+b=d$$.....

Edit: This is far too complicated for no reason. The real solution is the one given: $d|n$ and $d|n+1$ implies $d|(n+1)-n\Rightarrow d|1$ so $d=\pm 1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $d$ is congruent to $0$ mod what? $\endgroup$ – miniparser Aug 8 '15 at 4:57
  • $\begingroup$ Yes that was a mistake. I don't know where my head's been today. $\endgroup$ – Moya Aug 8 '15 at 5:06
2
$\begingroup$

I would personally just say the following. Say $n$ has a divisor $q$, for which $\frac{n}{q} = p, p \in \mathbb{Z}$. Then if we divide $n+1$ by $q$ we obtain $\frac{n+1}{q} = p + \frac{1}{q}$, thus for all $q \ne 1$ (since the $\gcd(1,q)=1$), $n+1$ will not be divisible by $q$.

Therefore $\gcd(n, n+1) =1$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Suppose $gcd(n,n+1)=d >0$ $$\to \left.\begin{matrix} d|n\\ d|n+1 \end{matrix}\right\}\Rightarrow d|(n+1)-(n)\Rightarrow d|1\\\frac{1}{d} \in \mathbb{Z}\Rightarrow d=\pm1 \overset{d>0}{\rightarrow} d=1$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

multiples of $n+1$:$\space n+1,2n+2,3n+3,...,(n-1)(n+1)=(n-1)n+(n-1),n(n+1),n(n+2),...$

least common multiple with $n$ must be $n(n+1)$ otherwise $n$ cannot divide it.

$lcm(n,n+1)=n(n+1)$; $\space gcd(a,b)={{ab}\over{lcm(a,b)}},\space a,b\in \mathbb{Z}; \space\space\space gcd(n,n+1)={{n(n+1)}\over{n(n+1)}}=1$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Related to 727 answer.

Theorem: For any integers $x,a,b$, $(a,b) = (a,b+ax)$.

(See the proof in theorem 1.9 in Niven's "An introduction to the theory of numbers".)

Then, for the particular case that $a=n$ and $b=n+1$, choose $x=-1$ to get:

$$ (n,n+1)=(n,1)=1. $$

| cite | improve this answer | |
$\endgroup$

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.