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 $34$ and $102$
The GCD of $34$ and $102$ is found to be:
- $\gcd \set {34, 102} = 34$
GCD of $52$ and $273$
The GCD of $52$ and $273$ is found to be:
- $\gcd \set {52, 273} = 13$
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 $595$ and $721$
The GCD of $595$ and $721$ is found to be:
- $\gcd \set {595, 721} = 7$
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$