Results 1 to 7 of 7

Math Help - Division Algorithm or Euclidean Algorithm

  1. #1
    Junior Member
    Joined
    Feb 2013
    From
    New York
    Posts
    28

    Division Algorithm or Euclidean Algorithm

    Hello, i am confused on division algorithm, can anyone give me an understandable example

    so far for euclidean
    i have 1188=385(3)+33
    385=33(3)+22
    33=22(3)+11
    22=11(2)+0
    and the answer is 11, does this apply to division too? cause i am somewhat dividing numbers.....
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Division Algorithm or Euclidean Algorithm

    Quote Originally Posted by zhengcl86 View Post
    and the answer is 11, does this apply to division too?
    I am not sure what exactly you are asking. You found the greatest common divisor of 1188 and 385 using the Euclidean algorithm.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2013
    From
    New York
    Posts
    28

    Re: Division Algorithm or Euclidean Algorithm

    oh umm can you please give me an example of an division algorithm
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Division Algorithm or Euclidean Algorithm

    Wikipedia says that Euclidean division is not so much an algorithm as a theorem that says:

    For all integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|.

    There are various algorithms for finding such q and r: division by repeated subtraction, long division, as well as more sophisticated and faster algorithms. Euclid himself used division by repeated subtraction in the Elements.

    You should check your source or ask your instructor about what is meant by Euclidean division in your course.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Apr 2013
    From
    Green Bay
    Posts
    68
    Thanks
    16

    Re: Division Algorithm or Euclidean Algorithm

    The Euclidean Algorithm is a process used to determine the greatest common divisor of two numbers. It uses several applications of the division algorithm.

    Division Algorithm: For any integer a,b where b =/= 0 there exists unique integers q and r such that a = bq + r and 0 <= r < |b|.

    Each step in your Euclidean Algorithm example represents an application of the division algorithm.

    For example. Let a = 1188 and b = 385. Then choosing q = 3 and r = 33 we see that 1188 = (385)(3) + 33 and 0 <= 33 < 385.
    Make sense now?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Division Algorithm or Euclidean Algorithm

    Quote Originally Posted by mathguy25 View Post
    Division Algorithm: For any integer a,b where b =/= 0 there exists unique integers q and r such that a = bq + r and 0 <= r < |b|.
    Well, this is not an algorithm, it is a proposition.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Apr 2013
    From
    Green Bay
    Posts
    68
    Thanks
    16

    Re: Division Algorithm or Euclidean Algorithm

    Quote Originally Posted by emakarov View Post
    Well, this is not an algorithm, it is a proposition.
    Yes, it's a proposition. However, it is known as the Division Algorithm.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean algorithm
    Posted in the Algebra Forum
    Replies: 7
    Last Post: October 7th 2012, 06:40 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 06:53 AM
  3. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 13th 2010, 07:25 PM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM
  5. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 29th 2009, 11:51 AM

Search Tags


/mathhelpforum @mathhelpforum