Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer

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

share|cite|improve this answer
    
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?

share|cite|improve this answer
6  
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$?

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
1  
Try to use MathJax. – SchrodingersCat Feb 17 at 14:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.