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