How can I use the congruence property to determine GCD?

Question

As per my text, the congruence property is: If a > 0, b, and b' are integers such that $$b \equiv b' (mod\ a)$$ then $$(a,b) = (a,b')$$

I'm trying to use that to determine (7,150) and (28,-288).

Any tips/hints would be appreciated!

Answer 1

For the first one, we have that

$$150\equiv 3\,(\text{ mod } 7)$$

and since both $3$ and $7$ are prime,

$$\gcd(7,150)=1$$

As a more general note, suppose you have two integers $a$ and $b$ and you want to determine $\gcd(a,b)$. Take the one with the smaller absolute value (WLOG, $a$) and take $b\,(\text{mod }a)$ Keep doing this until you reach sufficiently small numbers, in which case you can find the GCD.

Also, read this Wikipedia article on Euclid's algorithm.

Answer 2

If you divide $150$ by $7$ you get $21$ as quotient and $3$ as remainder. That is, $150=21\cdot 7+3.$ This means $$150=3 (mod 7).$$ So, you have, applying the congruence property, $(7,150)=(7,3)=1.$

Can you do the same in the other case?