Euclidean Algorithm + Math Image
| Euclidean Algorithm |
Author
Phoebe Jiang
Field
Number Theory
Link
Euclidean Algorithm
NeedGradPlusDesc
Yes
Title
Euclidean Algorithm
UsedImage
EA1.jpg
Description
This image shows Euclid's method to find t … This image shows Euclid's method to find the greatest common divisor (gcd) of two integers. The '''greatest common divisor''' of two numbers a and b is the largest integer that divides the numbers without a remainder.
:Here I use 52 and 36 as an example to show you how Euclid found the gcd, so you have a sense of the Euclidean algorithm in advance. As you have probably noticed already, Euclid uses lines, defined as multiples of a common unit length, to represent numbers. First, use the smaller integer of the two, 36, to divide the bigger one, 52. Use the remainder of this division, 16, to divide 36 and you get the remainder 4. Now divide the last divisor, 16, by 4 and you find that they divide exactly. Therefore, 4 is the greatest common divisor. For every two integers, you will get the gcd by repeating the same process until there is no remainder.
:You may have many questions so far: "What is going on here?" "Are you sure that 4 is the gcd of 52 and 36?" Don't worry. We will talk about them precisely later. This brief explanation is just to preheat your enthusiasm for Euclidean Algorithm! It is amazing to see that he explains and proves his algorithm relying on visual graphs, which is different from how we treat number theory now. erent from how we treat number theory now.
Math Image
Euclidean Algorithm +
Categories Algebra +, Elementary School +, High School +, Higher Education +, Math Images +, Middle School +, Number Theory +, Phoebe Jiang +, Pre-Kindergarten +
|
