Computing gcd(a,b)

Useful Properties

Use divisibility to simplify the numbers before applying the Euclidean algorithm whenever possible.

Example

Let $\gcd(2n+3,\,5n-4)=d$.

Since $d\mid(2n+3)$, multiply by $5$ to obtain $d\mid(10n+15)$.

Since $d\mid(5n-4)$, multiply by $2$ to obtain $d\mid(10n-8)$.

Subtracting gives $d\mid23$, so the only possibilities are $d=1$ or $d=23$.

Finally, verify that each possible value is attainable by finding an appropriate value of $n$.

Examples: $n=1:\ \gcd(5,1)=1,\qquad n=10:\ \gcd(23,46)=23.$