# Division Algorithm or Euclidean Algorithm

• Apr 2nd 2013, 03:57 PM
zhengcl86
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.....
• Apr 3rd 2013, 02:47 AM
emakarov
Re: Division Algorithm or Euclidean Algorithm
Quote:

Originally Posted by zhengcl86
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.
• Apr 3rd 2013, 06:04 PM
zhengcl86
Re: Division Algorithm or Euclidean Algorithm
oh umm can you please give me an example of an division algorithm
• Apr 4th 2013, 02:15 AM
emakarov
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.

• Apr 10th 2013, 12:26 PM
mathguy25
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?
• Apr 10th 2013, 12:38 PM
emakarov
Re: Division Algorithm or Euclidean Algorithm
Quote:

Originally Posted by mathguy25
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.
• Apr 10th 2013, 01:10 PM
mathguy25
Re: Division Algorithm or Euclidean Algorithm
Quote:

Originally Posted by emakarov
Well, this is not an algorithm, it is a proposition.

Yes, it's a proposition. However, it is known as the Division Algorithm.