# Difference between revisions of "Euclidean algorithm"

(→See Also: link) |
I like pie (talk | contribs) m |
||

Line 2: | Line 2: | ||

==Main idea and Informal Description== | ==Main idea and Informal Description== | ||

− | |||

The basic idea is to repeatedly use the fact that <math>\gcd({a,b}) \equiv \gcd({a,a - b})</math> | The basic idea is to repeatedly use the fact that <math>\gcd({a,b}) \equiv \gcd({a,a - b})</math> | ||

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>{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>{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>{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer<math>m</math>, so, if <math>{d}</math> divides both <math>{a}</math> and <math>b</math>, it must divide both <math>{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>{a}</math> as well. Thus, the greatest common divisors of <math>{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> | 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>{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>{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>{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer<math>m</math>, so, if <math>{d}</math> divides both <math>{a}</math> and <math>b</math>, it must divide both <math>{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>{a}</math> as well. Thus, the greatest common divisors of <math>{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> | ||

− | |||

== General Form == | == General Form == | ||

− | |||

Start with any two elements <math>a</math> and <math>b</math> of a [[Euclidean Domain]] | Start with any two elements <math>a</math> and <math>b</math> of a [[Euclidean Domain]] | ||

Line 21: | Line 18: | ||

<math>r_{n-1} (\bmod r_n) \equiv 0</math><br> | <math>r_{n-1} (\bmod r_n) \equiv 0</math><br> | ||

Then <math>\gcd({a,b}) = r_n</math><br> | Then <math>\gcd({a,b}) = r_n</math><br> | ||

− | |||

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

Line 32: | Line 28: | ||

<math>r_{n-1} = r_n \cdot q_{n+2} +0</math><br> | <math>r_{n-1} = r_n \cdot q_{n+2} +0</math><br> | ||

and so <math>\gcd({a,b}) = r_n</math><br> | and so <math>\gcd({a,b}) = r_n</math><br> | ||

− | |||

== Simple Example == | == Simple Example == | ||

− | |||

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

Line 43: | Line 37: | ||

== 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 some elements from the same [[Euclidean Domain]] as <math>a</math> and <math>b</math> that can be determined using the algorithm. We can work backwards from whichever step is the most convenient. | 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 elements from the same [[Euclidean Domain]] as <math>a</math> and <math>b</math> that can be determined using the algorithm. We can work backwards from whichever step is the most convenient. | ||

## Revision as of 17:28, 25 April 2008

The **Euclidean algorithm** (also known as the **Euclidean division algorithm** or **Euclid's algorithm**) is an algorithm that finds the greatest common divisor (GCD) of two elements of a Euclidean domain, the most common of which is the nonnegative integers , without factoring them.

## Contents

## Main idea and Informal Description

The basic idea is to repeatedly use the fact that

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

## General Form

Start with any two elements and of a Euclidean Domain

- If , then .
- Otherwise take the remainder when is divided by , and find .
- Repeat this until the remainder is 0.

Then

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

for

and so

## Simple Example

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

## 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 elements from the same Euclidean Domain as and that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.

In the previous example, we can work backwards from equation :