Is This the Correct Approach to Finding GCD and LCM for Integer Pairs?

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

Thanks in advance for your help, comments, tips, clues, commentaries...

 

[NateTG]

That all looks correct.

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

 

[dogma]

Thanks for the reply.

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.

 

[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 algorithm to find the LCF directly.
$$35-2(15)=5$$

or
$$<20,35>=5$$
$$(35-20)=15$$
$$20 - (35 - 20) = 5$$
readily leads to the the linear combination
$$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.

 

[dogma]

Thanks!

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

Thanks much!

 

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