User:Charles Howard R. Gaa/sandbox

This is the user sandbox of Charles Howard R. Gaa. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

Euclidean Algorithm is a process proposed by the Greek mathematician Euclid for calculating the greatest common divisor (GCD) of two numbers in his Elements (c. 300 BC). The method is computationally efficient and is still used by computers with modest modifications. The algorithm entails dividing and calculating remainders in steps.

Example

To get the GCD of 56 and 12, divide 56 by 12 and note the quotient is 4 and the remainder is 8. This is calculated as 56 = 4 x 12 + 8. Take the divisor (12), divide it by the remainder (8), and write 12 = 1 x 8 + 4 as the result. Continue by taking the previous divisor (8), dividing it by the previous remainder (4), and writing the result as 8 = 2 x 4 + 0. The operation is now complete because the residual is now zero, and the last nonzero remainder, in this case 4, is the GCD.

The Euclidean Algorithm today

Euclid's algorithm has the advantage of being straightforward to follow and producing a solution rapidly, even for big numbers. Prime factorization, particularly of large numbers, is extremely difficult; in fact, certain types of encryption are predicated on it. With the technology that we have now, such as calculators, cellphones, laptops, and computers, we can solve mathematical problems easily.