# Euclidean Algorithm Steps

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

The steps in the Euclidean algorithm, which calculates the greatest common divisor of two positive integers. The red bars indicate the fraction of the remainder to the divisor.

Contributed by: Michael Trott (March 2011)

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

, — pair of integers whose greatest common divisor is to be calculated.

Algorithms are becoming more and more important. Nearly everyone encounters the PAGERANK algorithm (from Mr. Page) every day. One of the first (and still one of the most beautiful and useful) algorithms is the 2300-year-old Euclidean algorithm that calculates the greatest common divisor of two positive integers. Don Knuth once said that computer science will become a science when it has made 1000 algorithms. This Demonstration shows how it all got started. Can you find the pair of numbers that generate the longest output? (Hint: rabbits.)

## Permanent Citation

"Euclidean Algorithm Steps"

http://demonstrations.wolfram.com/EuclideanAlgorithmSteps/

Wolfram Demonstrations Project

Published: March 7 2011