# Euclidean Algorithm

In mathematics, the Euclidean algorithm or Euclid's algorithm, is an efficient method for computing the gcd of two numbers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in 300 BC.

Let's start by going through an example and then we will cover the rules of the
algorithm. Let's try to find the gcd of `210`

and `45`

. We start by dividing
`210`

by `45`

: `210 / 45 = 4 R30`

. This gives us a remainder of `30`

so we will
divide `45`

by `30`

: `45 / 30 = 1 R15`

. This gives us a remainder of `15`

so we
will divide `30`

by `15`

: `30 / 15 = 2`

. Since we have no remainder left so the
gcd of `210`

and `45`

is `15`

.

Let's now work through the formal description of the Euclidean algorithm:

- Input
- Two positive integers, a and b
- Output
- The gcd of a and b
- Internal computation
- steps:
- If a<b, exchange a and b.
- Divide a by b and get the remainder, r. If r=0, report b as the GCD.
- Replace a with b and replace b with r in step 2 and repeat step 2.

Now let's look at a pseudocode example of this algorithm:

a = input1 b = input2 if a < b a = input2 b = input1 while b != 0: r = a % b a = b b = r print "gcd is:" print a