# Thread: Division Algorithm or Euclidean Algorithm

1. ## 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.....

2. ## Re: Division Algorithm or Euclidean Algorithm

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.

3. ## Re: Division Algorithm or Euclidean Algorithm

oh umm can you please give me an example of an division algorithm

4. ## 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.

5. ## 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?

6. ## Re: Division Algorithm or Euclidean Algorithm

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.

7. ## Re: Division Algorithm or Euclidean Algorithm

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.