# Euclidean Algorithm/Examples

## Examples of Use of Euclidean Algorithm

### GCD of $341$ and $527$

The GCD of $341$ and $527$ is found to be:

$\gcd \set {341, 527} = 31$

### GCD of $2190$ and $465$

The GCD of $2190$ and $465$ is found to be:

$\gcd \set {2190, 465} = 15$

Hence $15$ can be expressed as an integer combination of $2190$ and $465$:

$15 = 33 \times 465 - 7 \times 2190$

### GCD of $9 n + 8$ and $6 n + 5$

The GCD of $9 n + 8$ and $6 n + 5$ is found to be:

$\gcd \set {9 n + 8, 6 n + 5} = 1$

Hence:

$2 \paren {9 n + 8} - 3 \paren {6 n + 5} = 1$

### Solution of $31 x \equiv 1 \pmod {56}$

Let $x \in \Z$ be an integer such that:

$31 x \equiv 1 \pmod {56}$

Then by using the Euclidean Algorithm:

$x = -9$

is one such $x$.

### GCD of $24$ and $138$

The GCD of $24$ and $138$ is found to be:

$\gcd \set {24, 138} = 6$

### GCD of $56$ and $72$

The GCD of $56$ and $72$ is found to be:

$\gcd \set {56, 72} = 8$

### GCD of $108$ and $243$

The GCD of $108$ and $243$ is:

$\gcd \set {108, 243} = 27$

### GCD of $119$ and $272$

The GCD of $119$ and $272$ is found to be:

$\gcd \set {119, 272} = 17$

### GCD of $129$ and $301$

The GCD of $129$ and $301$ is found to be:

$\gcd \set {129, 301} = 43$

Hence $43$ can be expressed as an integer combination of $129$ and $301$:

$43 = 1 \times 301 - 2 \times 129$

### GCD of $132$ and $473$

The GCD of $132$ and $473$ is:

$\gcd \set {132, 473} = 11$

### GCD of $143$ and $227$

The GCD of $143$ and $227$ is:

$\gcd \set {143, 227} = 1$

### GCD of $156$ and $1740$

The GCD of $156$ and $1740$ is:

$\gcd \set {156, 1740} = 12$

### GCD of $272$ and $1479$

The GCD of $272$ and $1479$ is:

$\gcd \set {272, 1479} = 17$

### GCD of $299$ and $481$

The GCD of $299$ and $481$ is found to be:

$\gcd \set {299, 481} = 13$

Hence $13$ can be expressed as an integer combination of $299$ and $481$:

$13 = 5 \times 481 - 8 \times 299$

### GCD of $306$ and $657$

The GCD of $306$ and $657$ is:

$\gcd \set {306, 657} = 9$

### GCD of $361$ and $1178$

The GCD of $361$ and $1178$ is:

$\gcd \set {361, 1178} = 19$

### GCD of $527$ and $765$

The GCD of $527$ and $765$ is:

$\gcd \set {527, 765} = 17$

### GCD of $1769$ and $2378$

The GCD of $1769$ and $2378$ is found to be:

$\gcd \set {1769, 2378} = 29$

### GCD of $2145$ and $1274$

The GCD of $2145$ and $1274$ is:

$\gcd \set {2145, 1274} = 13$

Hence $13$ can be expressed as an integer combination of $2190$ and $465$:

$13 = 32 \times 1274 - 19 \times 2145$

### GCD of $12321$ and $8658$

The GCD of $12321$ and $8658$ is:

$\gcd \set {12321, 8658} = 333$

### GCD of $12378$ and $3054$

The GCD of $12378$ and $3054$ is:

$\gcd \set {12378, 3054} = 6$