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?
$\begingroup$
$\endgroup$
1
-
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éophileAug 8, 2015 at 2:27
Add a comment
|
8 Answers
$\begingroup$
$\endgroup$
8
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?).
-
$\begingroup$ Let $n = ak$ and $n + 1 = aj$. Then $n - n - 1 = -1 = a(k - j)$. But $a$ doesn't divide $-1$? $\endgroup$ Aug 8, 2015 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$– 727Aug 8, 2015 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$– 727Aug 8, 2015 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$ Aug 8, 2015 at 2:49
-
2$\begingroup$ $d|a, d|b \to d|(a - b)$. Since $a - b = n + 1 - n = 1$, $d|1$. Then $d$ must be $1$? $\endgroup$ Aug 8, 2015 at 3:03
$\begingroup$
$\endgroup$
2
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$.
-
-
$\begingroup$ Yes that was a mistake. I don't know where my head's been today. $\endgroup$– MoyaAug 8, 2015 at 5:06
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
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$$
$\begingroup$
$\endgroup$
1
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. $$
-
$\begingroup$ This is the key property, which by the way is the basis of the extended euclidean algorithm $\endgroup$ Jan 17, 2021 at 18:08
$\begingroup$
$\endgroup$
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$
answered Aug 9, 2015 at 20:49
$\begingroup$
$\endgroup$
Suppose $n$ $\in \mathbb{Z}$ $s.t$ $n = 1$. Obviosuly, $gcd(n,n+1) = gcd(1,n+1) = 1$. Now, suppose $n$ $\in$ $\mathbb{Z}$ $s.t$ $n$ $\gt$ $1$. By the division algorithm, we have $$\ (n+1) = nq + r$$ $$0 \le r \lt n$$In particular $$\ (n+1) = n(1) +1$$ which gives us $$ gcd(n+1,n) = gcd(n,1) =1$$ $\mathbb{Q.E.D}$
$\begingroup$
$\endgroup$
Take $n$ and $n-1$, if they have a common prime $p$ then from $n-(n-1)$ we can write $$n-(n-1)=p\cdot\left(\dfrac{n}{p}-\dfrac{n-1}{p}\right)=p\cdot\dfrac{n-n+1}{p}=p\cdot\dfrac{1}{p}$$ and that implies p divides 1, absurd, because p is prime. $quod$ $erat$ $demonstrandum$
