# Show that any two consecutive odd integers are relatively prime

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?

-

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.

-

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.$$

-
Now generalize to integers $2k+1$ and $2k+1+2^m$ that differ by any power of two. – Jeppe Stig Nielsen Feb 17 at 20:03

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?

-
However, once you've run the Euclidean algorithm, you can work it backwards to get the required linear combination without needing to spot any pattern. You've already worked out (not that it took much effort to work them out, but in general the divisions might have been harder), $2k+3 = (2k+1) + 2$ and $2k + 1 = (k)(2) + 1$. So $1 = (2k+1) - (k)(2) = (2k+1) - k((2k+3) - (2k+1)) = (1+k)(2k+1) - k(2k+3)$. The Euclidean algorithm can always be worked back like this, provided you record the quotient and remainder at each step. – Steve Jessop Feb 17 at 0:11

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$?

-

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.

-

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.

-
Try to use MathJax. – SchrodingersCat Feb 17 at 14:58