# Proof on Integers, sa+tb=n

• Nov 8th 2010, 08:10 PM
DEUCSB
Proof on Integers, sa+tb=n
The problem: Let a,b be coprime positive integers. Prove that for any integer n there exists s,t with s>0 such that sa+ tb=n.

My work so far (do not know if I am on the right path):

If a,b are coprime there exists s,t in the integers that sa+tb=1.
This is by definition that is given in our text.
Since, in addition, a,b are positive integers then there are two possible scenarios for s,t as follows:
1. s>0 and t<0
2.s<0 and t>0

This problem has given me a headache :)
I will greatly appreciate your feedback!

Thanks!
• Nov 9th 2010, 02:40 AM
aman_cc
Hint: Note that you also have some x and y, such that xa + yb = 0
Can you now take it fwd?
• Nov 9th 2010, 06:08 AM
DEUCSB
i think.
I'll try to break the problem up into cases.

One for n being postiive
One for n being zero
One for n being negative

Then for all the cases I will show that there is a set of s and t's such that the coefficient in front of the a term will be positive.
• Nov 9th 2010, 07:18 AM
roninpro
I'd like to point out that your original attempt actually doesn't help. There will be some positive and negative $s$ that satisfy the equation; that is, the equation can be satisfied in both cases.

One route that you could try is geometric: consider $as+bt=n$ as a line on the $st$-plane. Finding integer solutions to the equation means finding integer points that lie on the line. The main question is, where are the integer points on the line? You might like to try a few numerical examples and then make guess in general.
• Nov 9th 2010, 07:33 AM
emakarov
Quote:

I'd like to point out that your original attempt actually doesn't help.
I don't agree. I think that the idea that sa + tb = 1 for some s, t together with the remark that xa + yb = 0 for some x, y allow finishing the proof. I would add that one can choose to have x > 0, y < 0 or x < 0, y > 0. Using xa + yb = 0, one can "pump" the coefficient of a in sa + tb = 1 to make it have the correct sign.

Quote:

If a,b are coprime there exists s,t in the integers that sa+tb=1.
This is by definition that is given in our text.
I doubt that this is the definition of coprime numbers. It is probably a fact that is proved afterwards.