Euclidean algorithm proof

• November 26th 2009, 04:52 AM
withoutaclue
Euclidean 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
• November 26th 2009, 06:39 AM
Shanks
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.
• November 26th 2009, 08:13 AM
withoutaclue
hmm so i use prove,
but i dont really get the -nb,-(n-1)b bit
do you mind explaining?
• November 26th 2009, 09:34 AM
Shanks
it is the half closed half open interval,e.g. all the integers in $[1,5)$ are 1,2,3,4; the number x is in $[1,5)$ if and only if it is no less than 1, and strictly less than 5.
• November 26th 2009, 02:13 PM
withoutaclue
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
• November 26th 2009, 02:44 PM
emakarov
The intuitive idea is that you take this negative $a$ and start adding $b$ to it ( $b$ must be positive). By adding $b$ as many time as needed (call it $q$ times) you will come to the neighborhood of 0. If you hit 0 directly, then $a+qb=0$. If you don't hit 0 directly, then after some step you'll be at $a+qb < 0$, and the next step at $r=a+(q+1)b > 0$. So, since $a+qb$ is negative, $0\le r < b$.

Induction is just a formal way to explain the phrase "By adding b as many time as needed".
• November 28th 2009, 07:03 PM
Roam
Like you said theorem states that if f(t) & g(t) are polynomials then $\exists q(t), r(t)$ such that f(t)=q(t)g(t)+r(t), where $g(t) \neq 0$. I just wrote it more clearly.

So, I would prove the Euclidean algorithm in a slightly different way. If $f(t) \equiv 0$ or if $deq (f) < deg (g)$, then we have the required representation $f(t)=0 g(t)+f(t)$. Now suppose $deg (f) \geq deg (g)$, say $f(t)=a_nt^n +...+a_1t+a_0$ and $g(t)=b_mt^m+...+b_1t+b_0$ where $a_n, b_m \neq 0$ & $n \geq m$.

So we form the polynomial:

$
f_1 (t) = f(t) - \frac{a_n}{b_m} t^{n-m} g(t)
$

Actually, this is the first step in long division.

Then $deg(f_1) < deg (f)$. By induction, there exists polynomials q_1 (t) and r(t) such that $f_1 (t) = q_1(t)g(t)+r(t)$ where neither $r(t) \equiv 0$ or $deg(r) < deg(g)$.

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

$f(t)=[q_1 (t) + \frac{a_n}{b_m} t^{n-m}]g(t)+r(t)$

Which is the representation we wanted.