Find GCD of a and b: Express as Integer Combination

[achacttn]

RESOLVED

Homework Statement

Let a = 123, b = 321. Compute d = gcd(a,b) and express d as an integer combination of ra + sb.

Homework Equations

This is a question (3.1, page 70 of Michael Artin's Algebra). For those who do not have the book, this problem is relevant to the section on subgroups of the additive groups of integers.

The Attempt at a Solution

I quickly found d using the Euclidean algorithm (d=3). However, I'm unsure how to approach the 2nd part. So far, it just seems like brute-forcing integer multiples of a and b on a calculator and hoping the difference comes out as |3|.

Any help or point in the right direction would be much appreciated.

 

[Benn]

Here's an exposition of a neat way to do it: http://www.millersville.edu/~bikenaga/number-theory/exteuc/exteuc.html

He gives a proof of the method, and then gives an example of it in action.

 

[achacttn]

Thanks !