Results 1 to 7 of 7

Math Help - 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 [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.
    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,517
    Thanks
    771
    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".
    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 \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:

     <br />
f_1 (t) = f(t) - \frac{a_n}{b_m} t^{n-m} g(t)<br />

    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.
    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: October 11th 2010, 04:16 AM
  2. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  3. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 24th 2010, 09:54 PM
  4. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 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