# Abtract Algebra Sanity Check

1. Oct 27, 2004

### dogma

Hello out there!

I'm working a problem where I need to find the greatest common divisor and the least common multiple for integer pairs. I then need to express the gcd as a linear combination. I could use a sanity check to make sure I'm on the right track.

I need to find the gcd and lcm of the integer pair: 175 and 35

By visual inspection, I "see" the answers, but working it outâ€¦

The gcd: $$(175,35) = \prod_i p_i^{min(\alpha_i,\beta_i)}$$

$$175 = 5^1\cdot35 = 5^1\cdot5^1\cdot7^1 = 5^2\cdot7^1$$

$$35 = 5^1\cdot7^1$$

$$(175,35) = 5^1\cdot7^1 = 35$$

The lcm: $$[175,35] = \prod_i p_i^{max(\alpha_i,\beta_i)}$$

$$[175,35] = 5^2\cdot7^1 = 175$$

So now I need to express the gcd as a linear combination. Is this correct:

$$ax + by = d$$ where $$d = (a,b)$$

$$175x + 35y = 35$$

$$x = 0$$ and $$y = 1$$

$$\therefore 175\cdot(0) + 35\cdot(1) = 35$$

Hopefully I'm on the right track, although I can see there being multiple solutions for the linear combination.

2. Oct 27, 2004

### NateTG

That all looks correct.

You might consider using Euclid's algoritm for finding the GCD - it dovetails nicely with the linear combination thing.

3. Oct 27, 2004

### dogma

It looks like the Euclidean Algorith would result in a one liner:

$$175 = 5\cdot35 + 0$$

How would you "pull" the linear combination out of that? I must be missing something simple.

Thanks again.

4. Oct 27, 2004

### NateTG

Well, the example you gave is a special case b/c the gcf is one of the factors. If you had somehting like:
$$<15,35>=5$$

Then you'd be able to use the Euclidean algoritm to find the LCF directly.
$$35-2(15)=5$$

or
$$<20,35>=5$$
$$(35-20)=15$$
$$20 - (35 - 20) = 5$$
$$2 \times 20 - 1 \times 35 = 5$$

I guess, that mostly, I like Euclid's algorithm because it's less computationally complex - it takes roughly $$\log(n)$$ time while factoring can take $$n^{\frac{1}{4}}$$ or so time. I suppose it doesn't much matter unless you're dealing with big numbers.

5. Oct 27, 2004

### dogma

Thanks!

After reading your replies and vary info on the web (and in texts), it's very clear now.

Thanks much!

6. Oct 27, 2004

### shmoe

Hi, I thought I'd point out that you can find the lcm without factoring also. You have the relation gcd(a,b)*lcm(a,b)=a*b, for any positive integers a, b. So you can use the euclidean algorithm to find the gcd, then the lcm follows with little effort.

Also, when the euclidean algorithm spat out 175=(5)35+0, you knew the gcd was 35, since it divides both numbers. The obvious linear combination is the one you ended with, taking the coefficient of 35 to be 1. If you wanted more, you could rearrange the equation to get:

175=(4)35+35

or

(1)175-(4)35=35

Get as many different ones as you like by adding any integer multiple of (1)175-(5)35 to the left hand side.

Last edited: Oct 27, 2004