# Homework Help: Abstract algebra/elementary number theory: Express d as integer combination ra + sb

1. Aug 11, 2012

### achacttn

RESOLVED

1. The problem statement, all variables and given/known data

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

2. Relevant 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.

3. 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.

Last edited: Aug 11, 2012
2. Aug 11, 2012

### Benn

Re: Abstract algebra/elementary number theory: Express d as integer combination ra +

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

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

Last edited by a moderator: May 6, 2017
3. Aug 11, 2012

### achacttn

Re: Abstract algebra/elementary number theory: Express d as integer combination ra +

Thanks !