Math Is Fun Forum

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Euclidean Algorithm and GCD

In what cases does repeated use of the Euclidean Algorithm not give the greatest common divisor as the last non-zero remainder?

Thanks.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Euclidean Algorithm and GCD

Well, first of all the Euclidean Algorithm is to continue iterating until you get a zero remainder, so it makes no sense to apply it more than once.  I know you were referring to the actual iterations themselves, but it is important to get the vocabulary right.

The answer to your question however, is none, at least with integers.  You always get the gcd as a result as long as you have a and b not equal to 0 or 1.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

That's what I thought, but my book says:

"Repeated use of the Euclidean Algorithm provides the greatest common divisor as the last non-zero remainder (in almost all cases, but why is this statement not quite true?)"

All I can think of is if one of the numbers is a factor of the other.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Euclidean Algorithm and GCD

That is correct.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

Thank you. I have some other questions related to the Euclidean Algorithm, GCD and LCM.

1. Find the greatest common divisor h of 630 and 765 using the Euclidean Algorithm.
2. Find the integers s and t such that 630 = hs and 765 = ht, and prove that s and t are coprime. Prove that [s,t] = st and hence find the least common multiple of 630 and 765.

Ok the first part is easy:

765 = 1 x 630 +135,
630 = 4 x 135 + 90,
135 = 1 x 90 + 45,
90 = 2 x 45 + 0.

The last non-zero remainder is 45
⇒ h = 45
⇒ s = 14, t = 17

To prove that they are coprime... is it enough to say that 17 is prime anyway, so the two numbers can't possibly share a factor? Or use the Euclidean Algorithm to show that the gcd is 1?

It's the last two parts I'm having trouble with. To prove that [s,t] = st:

A common multiple is st. I need to show that this is the least common multiple, so I need to show that there are no other common multiples that divide st. If st/n, where n is an integer, is a common multiple of s and t, then both s/n and t/n must be integers for st/n to be an integer. But since (s,t) = 1, n must be 1 (otherwise s/n and t/n could not both be integers) and hence [s,t] = st/1 = st. Is this right?

I can't really see how to hence find [630,765]? This is the same as asking for [hs,ht]... but I can't see where to go.

Thanks.

Last edited by Daniel123 (2008-08-21 10:45:08)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Euclidean Algorithm and GCD

You're right that in this case, the numbers are small enough that you can easily see that one of them is prime anyway. But it's probably best to use a general method that would apply to any problem. You could certainly prove it using Euclid's algorithm again, but there's a quicker way.

You worked out s and t such that 630 = hs and 735 = ht, where h = (630,735).
Do a similar thing with 14 and 17, saying for example that 14 = gu and 17 = gv, where g = (14,17).

Then 630 = h(gu) and 735 = h(gv). Clearly, 630 and 735 have a common factor of hg.
But since their HCF is h, that means g must be 1.

That's maybe more long-winded than you need it to be, I'm not sure how rigorously the question wants it shown. It could be enough to just say that you've already used Euclid's algorithm to find all the common factors of 630 and 735, and so there can't be any left over.

Your proof that [s,t] = st looks fine. The one thing I'm not sure about is whether you're allowed to divide by things. You might not have discovered rationals yet.
So, instead of saying that st/n is an integer, say something like that a k exists such that nk = st.

Now that you know h and [s,t], the last part is relatively straightforward.
Not sure if you've learnt this rule yet, but if not then it'd be a good one to convince yourself about:

[hs,ht] = h[s,t]
If you use that, you just need to plug stuff to find the answer.

That exercise is probably setting you up to prove that (s,t) x [s,t] = st, which is another fairly important rule.

---

Why did the vector cross the road?
It wanted to be normal.

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

Thanks for that mathsyperson.

I hadn't learnt the rule you mentioned, but I can see why.

And you're exactly right, the next question asks me to prove just that

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Euclidean Algorithm and GCD

See this! http://www.mathisfunforum.com/viewtopic.php?id=8048

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

See this! http://www.mathisfunforum.com/viewtopic.php?id=8048

Jane, what is a'?

Let a = hs and b = ht, where h = (a,b), and let s = gv and t = gu, where g = (s,t).

Writing a and b in terms of g gives a = hgv, b = hgu. hg is clearly a common divisor of a and b ⇒ g = 1 as h = (a,b). As g = 1, s and t are coprime.

If s and t are coprime, it can be shown that [s,t] = st using my method from earlier (mathsy, I can't seem to explain properly using nk=st?)

As s and t are coprime, [hs,ht]=hst or [a,b] = hst (how would I explain this one?).

Therefore (a,b) x [a,b] = h x hst = hs x ht = a x b.

Thanks

Last edited by Daniel123 (2008-08-22 00:28:30)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Euclidean Algorithm and GCD

If s and t are coprime, it can be shown that [s,t] = st using my method from earlier (mathsy, I can't seem to explain properly using nk=st?)

Yeah, I couldn't think of how to do it either (which is why I didn't ).
The reasoning will be pretty much the same as what you had, it's just the way of saying it that's the problem. It probably doesn't matter that much anyway.

---

Why did the vector cross the road?
It wanted to be normal.

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

What about explaining how [hs,ht] = hst? I can 'see' it, but I have no idea how to explain it.

Last edited by Daniel123 (2008-08-22 00:59:09)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Euclidean Algorithm and GCD

IS ANYBODY LISTENING TO ME? I ALREADY PROVED THE RESULT HERE!

http://www.mathisfunforum.com/viewtopic.php?id=8048

Last edited by JaneFairfax (2008-08-22 01:24:38)

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

Is anybody listening to me? I already proved the result here:

http://www.mathisfunforum.com/viewtopic.php?id=8048

We are listening to you! When I first looked at your proof I didn't really follow it. The theorem that "(a,b) = 1  ⇒ there exist integers x and y such that xa + yb = 1" comes after this question in my book, and I hadn't yet seen it.

Sorry! I can now see how your proof works

Could you please explain to me why [hs,ht] = hst if (s,t)=1?

Last edited by Daniel123 (2008-08-22 01:29:30)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Euclidean Algorithm and GCD

Thanks.

Could you please explain to me why [hs,ht] = hst if (s,t)=1?

Let

,

.

Thus

and

for some

.

Then

is common multiple of

. Since

we have

.

Now

and

. Thus

is a common divisor of

.

since

.

HENCE

.

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

Brilliant, thanks Jane

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

This is driving me crazy.

We prove that 75 and 34 are coprime:

75 = 2 x 34 + 7,
34 = 4 x 7 + 6,
7 = 1 x 6 +1,
6 = 6 x 1

The working of the above example may be recast as follows:

1 = 7 - 1 x 6
   = 7 - 1 x (34 - 4 x 7)
   = 5 x 7 - 1 x 34
   = 5 x (75 - 2 x 34) - 1 x 34
   = 5 x 75 - 11 x 34

I don't see how they've done this. How do you get from the second to the third line?

Last edited by Daniel123 (2008-08-22 02:35:33)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Euclidean Algorithm and GCD

7 - 1 x (34 - 4 x 7) = 1x7 - 1x(34 - 4x7) = 1x7 - 1x34 + 4x7 = 5x7 - 1x34

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Euclidean Algorithm and GCD

That step's just expanding and simplifying.

    7 - 1 x (34 - 4 x 7)
= 7 - 1 x 34 + 4 x 7
= 5 x 7 - 1 x 34.

The step from the 4th to 5th line is the same kind of thing.

The general method is to go "backwards" through Euclid's algorithm, displaying the HCF as multiples of the various remainders until you get back to the original two starters.

---

Why did the vector cross the road?
It wanted to be normal.

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

Thanks. I think I'm being rather thick today.

EDIT: Another question:

Write down integers x and y such that 7x + 4y = 1. Find expressions for all integers x and y such that 7x + 4y = 1.

The first part is easy.. I used the Euclidean Algorithm backwards to get x = -1, y = 2. I'm not too sure about the second though. Here is the solution in my book:

"Having got one solution you can get all solutions in the following way: Put x = -1 + X, y = 2 + Y, then 1 = 7x + 4y = 1 + 7X + 4Y, so 7X + 4Y = 0. then since 7 and 4 are coprime, it follows that an integer k exists such that X = -4k, Y = 7k . Hence the soloutions are x = -1 - 4k, y = 2 + 7k where k can be any integer"

My problem is the bit in bold. Why must 7 and 4 be coprime for this to work?

Thanks, again.

Last edited by Daniel123 (2008-08-22 06:18:45)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Euclidean Algorithm and GCD

I'm guessing it's because if they weren't coprime, then some solutions would get missed.
Say you had 4 and 6 instead. Putting X = -4k, Y = 6k means that, for example, X = -2, Y = 3 wouldn't get included even though it would work.

But if they weren't coprime then you couldn't use Euclid to get some multiples of them that total 1 anyway, so it wasn't really a problem in the first place.
It's also odd that they've said an integer k exists, when they go on to use all integers rather than just one.

---

Why did the vector cross the road?
It wanted to be normal.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Euclidean Algorithm and GCD

"Having got one solution you can get all solutions in the following way: Put x = -1 + X, y = 2 + Y, then 1 = 7x + 4y = 1 + 7X + 4Y, so 7X + 4Y = 0. then since 7 and 4 are coprime, it follows that an integer k exists such that X = -4k, Y = 7k . Hence the soloutions are x = -1 - 4k, y = 2 + 7k where k can be any integer"

My problem is the bit in bold. Why must 7 and 4 be coprime for this to work?

since 4 and 7 are coprime.

for some

.

Similarly

since 4 and 7 are coprime.

for some

.

.

I'm guessing it's because if they weren't coprime, then some solutions would get missed.
Say you had 4 and 6 instead. Putting X = -4k, Y = 6k means that, for example, X = -2, Y = 3 wouldn't get included even though it would work.

WHAT ON EARTH ARE YOU TALKING ABOUT?!?!?!

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

Right ok, thank you Jane

I think I have this one right, I'd just like someone to check it please:

What is the smallest positive integer h for which x and y can be found such that 133x + 84y = h?

Thanks.

Last edited by Daniel123 (2008-08-22 12:46:55)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Euclidean Algorithm and GCD

It’s the gcd of 133 and 84.

From the point of view of ring theory, the set

is the ideal of

generated by a and b. Since

is a PID (principal-ideal domain),

must be an ideal generated by some integer. It turns out that

.

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Euclidean Algorithm and GCD

It’s the gcd of 133 and 84.

Which is 7 I followed up until "ring theory".

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Euclidean Algorithm and GCD

Proof.

Note that a and b are positive integers but x and y can be positive or negative (or 0).

Let

.

Then S contains some positive integers, e.g.

and

.

Let d be the smallest positive member of S. So

for some

.

Now, by the division algorithm, we have

for some

with

. Then

. By minimality of d,

. Hence d divides a.

By applying the division algorithm to b, we also have that d divides b.

If

is any integer dividing a and b, then c must divide

.

This proves that

.