Euclidean Algorithm/Examples

From ProofWiki
Jump to navigation Jump to search

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$