Results 1 to 7 of 7

Thread: Euclidean algorithm proof

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    5
    hmm so i use prove,
    but i dont really get the -nb,-(n-1)b bit
    do you mind explaining?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    5
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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".
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2008
    Posts
    191
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Oct 11th 2010, 04:16 AM
  2. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 5th 2010, 06:45 PM
  3. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 24th 2010, 09:54 PM
  4. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 10th 2006, 05:46 AM
  5. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 7th 2006, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum