Can anyone help me on the following question

show that if a< 0 then a=qb+r 0=<r<b

thankss so much

Printable View

- Nov 26th 2009, 05:52 AMwithoutaclueEuclidean algorithm proof
Can anyone help me on the following question

show that if a< 0 then a=qb+r 0=<r<b

thankss so much - Nov 26th 2009, 07:39 AMShanks
You can prove it by using mathematic induction.

let P(n) be the following proposition:

if the integer a is in [-nb,-(n-1)b), then there exist integer q and r, such that a=qb+r, where 0=< r < b. - Nov 26th 2009, 09:13 AMwithoutaclue
hmm so i use prove,

but i dont really get the -nb,-(n-1)b bit

do you mind explaining? - Nov 26th 2009, 10:34 AMShanks
it is the half closed half open interval,e.g. all the integers in are 1,2,3,4; the number x is in if and only if it is no less than 1, and strictly less than 5.

- Nov 26th 2009, 03:13 PMwithoutaclue
so how does the interval helps to solve the question? im really sorry, but i still i dont know how to use induction to proof

- Nov 26th 2009, 03:44 PMemakarov
The intuitive idea is that you take this negative and start adding to it ( must be positive). By adding as many time as needed (call it times) you will come to the neighborhood of 0. If you hit 0 directly, then . If you don't hit 0 directly, then after some step you'll be at , and the next step at . So, since is negative, .

Induction is just a formal way to explain the phrase "By adding b as many time as needed". - Nov 28th 2009, 08:03 PMRoam
Like you said theorem states that if f(t) & g(t) are polynomials then such that f(t)=q(t)g(t)+r(t), where . I just wrote it more clearly.

So, I would prove the Euclidean algorithm in a slightly different way. If or if , then we have the required representation . Now suppose , say and where & .

So we form the polynomial:

Actually, this is the first step in long division.

Then . By induction, there exists polynomials q_1 (t) and r(t) such that where neither or .

Putting this into the above and solving for f(t):

Which is the representation we wanted.