1b. Apply the Euclidean Algorithm to 90 and 37.
90 |
= |
37 · 2 + 16 |
37 |
= |
16 · 2 + 5 |
| 16 | = | 5 · 3 + 1 |
| 5 | = | 1 · 5 + 0 |
The last non-zero remainder was 1, so gcd(90, 37) = 1.
Note that when the gcd(a, b) = 1, we say that a and b are
"relatively prime", in other words, they have no prime factors in common.