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

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.

Re: Division Algorithm or Euclidean Algorithm

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

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.

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?

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.

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.