Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given two number A and B, how to find all the numbers in a large range say 'k' which can be formed by adding or subtracting A and B together any number of times.

Example: Suppose the numbers are 3 (A) and 8 (B). We wish to find all numbers up to 4 (k) which can be formed.

In this example all numbers can be formed.

1 = 3+3+3-8

2 = 8-3-3

3 = 3

4 = 8+8-3-3-3-3

I think all the numbers which are divisible by the GCD of A and B can be formed. But I am unable to prove it. I tried it on many inputs and found it working, still couldn't figure out a proof. I don't know whether I am right or wrong. Help me!

share|improve this question
3  
You are correct that all numbers divisible by the GCD can be formed. Look up "extended Euclidean algorithm". –  Rotwang Apr 6 '12 at 11:50
    
@Rotwang Thank You sir! :) –  Login Test Apr 6 '12 at 12:02
    
(+1) for a well-posed question. –  The Chaz 2.0 Apr 6 '12 at 14:19

1 Answer 1

up vote 7 down vote accepted

Congratulations on discovering an important problem, and forming the right conjecture!

Instead of talking about addition and subtraction, equivalently we can ask the following question. We are given two integers $a$ and $b$, not both $0$. Which positive integers can be expressed in the form $ax+by$, where $x$ and $y$ are integers (not necessarily positive)? Call a positive integer which is so expressible good.

It is clear that there are some positive integers expressible in the form $ax+by$, so there are good positive integers. Let $d$ be the smallest good positive integer. We will show that $d$ is the greatest common divisor of $a$ and $b$.

The main step in doing this is to show that $d$ divides $a$ and $d$ divides $b$. We show that $d$ divides $a$. The proof that $d$ divides $b$ is essentially the same.

Since $d$ is good, it follows that $d=au+bv$ for some integers $u$ and $v$.

We try to divide $a$ by $d$. We get $$a=qd+r,$$ where $q$ is the quotient, and where the "remainder" $r$ satisfies $0\le r<d$. But $d=au+bv$, and therefore $$a=q(au+bv)+r$$ or equivalently $$r=a(1-qu) +b(-v).$$ So $r$ is expressible in the form $ax+by$, with $x=1-qu$ and $y=-v$. But since by hypothesis $d$ was the smallest good positive integer, and $r<d$, the number $r$ cannot be positive. We are forced to conclude that $r=0$. So $a=qd$, meaning that $d$ divides $a$, and we are finished with this part of the argument.

Moreover, $d$ is the largest positive integer that divides both $a$ and $b$. For if $z$ divides $a$ and $b$, then since $d=au+bv$ we have that $z$ divides $d$, and therefore $z \le d$.

Now that we know that the greatest common divisor $d$ of $a$ and $b$ is expressible in the form $ax+by$, it is easy to see that any positive multiple $kd$ of $d$ is also expressible in the form $ax+by$.

Remark: There is a substantial theoretical bonus here. We have proved that for any positive integers $a$ and $b$, there exists a positive integer $d$ such that $d$ divides $a$ and $b$, and such that any $z$ that divides $a$ and $b$ must divide $d$. This is certainly true of the smallish integers that we are familiar with, but it is not obvious that the result holds for all positive integers. Now we know that it does.

Remark: There are other approaches to a proof that are in a practical sense more informative. Let $a$ and $b$ be very large integers whose greatest common divisor is $1$, such as $2^{50}$ and $3^{37}$. By the above argument, there are integers $x$ and $y$ such that $ax+by=1$. There are practical situations when we want to find such numbers $x$ and $y$ explicitly. That can be done very efficiently by using the Extended Euclidean Algorithm. The ideas that lead to this algorithm give an alternate proof of the result your post asks about.

The ideas that led to the proof can be substantially generalized. For example, suppose that $A(t)$ and $B(t)$ are polynomials (say with real coefficients) such that there is no polynomial of degree $>1$ that divides both $A(t)$ and $B(t)$. Then there are polynomials $X(t)$ and $Y(t)$ such that $A(t)X(t)+B(t)Y(t)$ is identically equal to $1$. The proof of this important fact is in basic structure very similar to the proof we gave above.

share|improve this answer
    
This answer is useful... and I sure wish I had seen such an accessible discussion years ago! –  The Chaz 2.0 Apr 6 '12 at 14:20
    
Thank You sir! Very-very clear and methodical... I must say its Awesome!! –  Login Test Apr 6 '12 at 15:25
    
You may enjoy going through a book on Elementary Number Theory. (Elementary does not mean easy, it is in this case a technical term.) –  André Nicolas Apr 6 '12 at 15:29
    
@AndréNicolas Thank you again. Nice contents! I'll go through it. :) –  Login Test Apr 7 '12 at 7:34

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.