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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.$$
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?
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$$
$$(2k+1)\cdot 1 - 2\cdot k = 1$$
$$ (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
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.