Show that any two consecutive odd integers are relatively prime

Question

I've selected two integers $m=2k+1$ and $n=2k+3$ and I've tried to make a linear combination of the two such that it equals 1, but I'm sort of stuck and am not sure if this is a dead end or not. Any pointers or alternative ideas?

Answer 1

If $d|2k+1$ and $d|2k+3$, then $d|2k+3-(2k+1)=2$. Thus $d=1$ or $d=2$. But $d\neq 2$, since $d$ is a divisor of an odd number. Then $d=1$. That is, the only common divisor of $2k+1$ and $2k+3$ is 1.

Answer 2

If you know about the Euclidean algorithm, you can see that $\gcd(2k+3, 2k+1) = \gcd(2k+1, 2) = \gcd(2, 1) = 1$.

As for making a linear combination: try small values of $k$ instead of diving right into the general case: For example with $k = 1, 2, 3$:

$2 \times 5 - 3 \times 3 = 1$

$3 \times 7 - 4 \times 5 = 1$

$4 \times 9 - 5 \times 7 = 1$

Can you extend this?

Answer 3

If you really want to express $1$ as a linear combination of $2k+1$ and $2k+3$, note that $$(2k+3)(k+1)-(2k+1)(k+2)=1.$$

Answer 4

If you want to write $1$ as a linear combination of $2k+1$ and $2k+3$, note

$$(2k+3) - (2k+1) = 2$$

and

$$(2k+1)\cdot 1 - 2\cdot k = 1$$

so

$$ (2k+1) \cdot 1 - (2k+3)\cdot k + (2k+1)\cdot k = 1$$

There's no magic here... if you can express $s$ as a linear combination of $x$ and $y$, and if you can express $t$ as a linear combination of $x$ and $y$, then you can express $s+t$, $-2s + 3t$, etc. as a linear combination of $x$ and $y$. So once you get $2$ and an odd number, you're done.

Answer 5

I believe the top answer is the most "straightforward" approach, but here is that same idea from a slightly different perspective:

If you were to think of the consecutive odds as sharing a factor $a > 1$, then what could it be? Certainly $a \neq 2$ since we are dealing with odds. So we'd need $a \geq 3$, which is absurd:

How could numbers $2$ apart share a factor $\geq 3$?

Answer 6

A=2n+1=c*a , where c is a common divisor

B=2n-1=c*b

A-B=c(a-b)=2

A>B hence a>b hence a-b>0.

If a-b=1 then c=2, and then A and B (since A=ca, B=cb) are not odd, which is a contradiction. Hence a-b is not 1.

If a-b=2 then c=1.

If a-b>2 then c*(a-b)>2 which is a contradiction.

Hence c=1 is the only option for a common divisor c.