Greatest Common Divisior by Geometry
Greatest Common Divisor by geometry
The G.C.D. of a pair of integers can be found by an interesting geometric method. (G.C.D. of a set of integers is the largest integer which can divide all the numbers without remainder). In order to do this, we only need a piece of paper, a scale and a pencil.
Suppose the two integers whose G.C.D. is to be found are a and b. First draw a rectangle on the paper of length a and breadth b. (If a and b are large take the length and breadth as <math>\frac{a}{2}</math> and <math>\frac{b}{2}</math> or in some suitable proportion).
From this rectangle mark off the largest possible square. If a is greater than b, this will be a square of side b. After marking off the square, the portion which remains is a rectangle with sides b and a – b. Again mark off the largest possible square from this rectangle. Continue this process till you obtain a square instead of a rectangle. The measure of the side of this square is equal to the G.C.D. of the original pair of numbers.
This method is based on the fact that if a and b are both divisible by a number, then a – b will also be divisible by the same number. The same principle is applied recursively to obtain the G.C.D.
