# Difference between revisions of "Euclidean algorithm"

(reorganized) |
(restored a part of the older version, kept the new organization intact) |
||

Line 1: | Line 1: | ||

The '''Euclidean algorithm''' allows us to find the [[greatest common divisor]] of any two [[nonnegative]] [[integer]]s. | The '''Euclidean algorithm''' allows us to find the [[greatest common divisor]] of any two [[nonnegative]] [[integer]]s. | ||

+ | ==Main idea and informal description== | ||

+ | |||

+ | If we have two non-negative integers <math>a,b</math> with <math>a\ge b</math> and <math>b=0</math>, then the greatest common divisor is <math>\displaystyle{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>\displaystyle{a}</math> and <math>b</math> is the same as the set of common divisors of <math>b</math> and <math>r</math> where <math>r</math> is the [[remainder]] of division of <math>\displaystyle{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer<math>m</math>, so, if <math>\displaystyle{d}</math> divides both <math>\displaystyle{a}</math> and <math>b</math>, it must divide both <math>\displaystyle{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>\displaystyle{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>\displaystyle{a}</math> as well. Thus, the greatest common divisors of <math>\displaystyle{a}</math> and <math>b</math> and of <math>b</math> and <math>r</math> coincide: <math>GCD(a,b)=GCD(b,r)</math>. But the pair <math>(b,r)</math> consists of smaller numbers than the pair <math>(a,b)</math>! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes <math>0</math> | ||

+ | |||

== Steps == | == Steps == | ||

Line 14: | Line 18: | ||

To see how it works, just take an example. Say <math>\displaystyle a=112,b=42</math>. We have <math>112\equiv 28\pmod {42}</math>, so <math>\displaystyle{\gcd(112,42)}=\displaystyle\gcd(42,28)</math>. Similarly, <math>42\equiv 14\pmod {42}</math>, so <math>\displaystyle\gcd(42,28)=\displaystyle\gcd(28,14)</math>. Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\displaystyle \gcd(28,14)}={\displaystyle \gcd(14,0)} = 14</math>. Thus <math>\displaystyle\gcd(112,42)=14</math>. | To see how it works, just take an example. Say <math>\displaystyle a=112,b=42</math>. We have <math>112\equiv 28\pmod {42}</math>, so <math>\displaystyle{\gcd(112,42)}=\displaystyle\gcd(42,28)</math>. Similarly, <math>42\equiv 14\pmod {42}</math>, so <math>\displaystyle\gcd(42,28)=\displaystyle\gcd(28,14)</math>. Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\displaystyle \gcd(28,14)}={\displaystyle \gcd(14,0)} = 14</math>. Thus <math>\displaystyle\gcd(112,42)=14</math>. | ||

− | Usually the Euclidean algorithm is written down just as a chain of divisions: | + | Usually the Euclidean algorithm is written down just as a chain of divisions with remainder: |

* <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math> | * <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math> | ||

Line 22: | Line 26: | ||

== Linear Representation == | == Linear Representation == | ||

− | An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write <math>\gcd(a,b)=ax+by</math>, where <math>x,y</math> are constants | + | An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write <math>\gcd(a,b)=ax+by</math>, where <math>x,y</math> are some integer constants that can be determined using the algorithm. |

In the example, we can rewrite equation <math>(2)</math> from above as | In the example, we can rewrite equation <math>(2)</math> from above as |

## Revision as of 12:35, 20 June 2006

The **Euclidean algorithm** allows us to find the greatest common divisor of any two nonnegative integers.

## Contents

## Main idea and informal description

If we have two non-negative integers with and , then the greatest common divisor is . If , then the set of common divisors of and is the same as the set of common divisors of and where is the remainder of division of by . Indeed, we have with some integer, so, if divides both and , it must divide both and and, thereby, their difference . Similarly, if divides both and , it should divide as well. Thus, the greatest common divisors of and and of and coincide: . But the pair consists of smaller numbers than the pair ! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes

## Steps

Start with two nonnegative integers, and .

- If , then .
- Otherwise take the remainder when is divided by (), and find .

Repeat this until .

## Simple Example

To see how it works, just take an example. Say . We have , so . Similarly, , so . Then , so . Thus .

Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:

## Linear Representation

An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write , where are some integer constants that can be determined using the algorithm.

In the example, we can rewrite equation from above as