# Euclidean algorithm proof

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

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

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

So we form the polynomial:

$\displaystyle 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 $\displaystyle deg(f_1) < deg (f)$. By induction, there exists polynomials q_1 (t) and r(t) such that $\displaystyle f_1 (t) = q_1(t)g(t)+r(t)$ where neither $\displaystyle r(t) \equiv 0$ or $\displaystyle deg(r) < deg(g)$.

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

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

Which is the representation we wanted.