# Euclidean Algorithm/Examples

## Contents

- 1 Examples of Use of Euclidean Algorithm
- 1.1 GCD of $341$ and $527$
- 1.2 GCD of $2190$ and $465$
- 1.3 GCD of $9 n + 8$ and $6 n + 5$
- 1.4 Solution of $31 x \equiv 1 \pmod {56}$
- 1.5 GCD of $108$ and $243$
- 1.6 GCD of $132$ and $473$
- 1.7 GCD of $129$ and $301$
- 1.8 GCD of $156$ and $1740$
- 1.9 GCD of $299$ and $481$
- 1.10 GCD of $361$ and $1178$
- 1.11 GCD of $527$ and $765$
- 1.12 GCD of $2145$ and $1274$
- 1.13 GCD of $12321$ and $8658$

## 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$

#### Integer Combination

$31$ can be expressed as an integer combination of $341$ and $527$:

- $31 = 2 \times 527 - 3 \times 341$

### 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 $108$ and $243$

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

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

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

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

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

### 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 $156$ and $1740$

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

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

### 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 $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 $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$