You are not logged in.
In what cases does repeated use of the Euclidean Algorithm not give the greatest common divisor as the last non-zero remainder?
Thanks.
Offline
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..."
Offline
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.
Offline
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..."
Offline
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)
Offline
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.
Offline
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
Offline
Offline
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)
Offline
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.
Offline
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)
Offline
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)
Offline
Is anybody listening to me? I already proved the result here:
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)
Offline
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
.Offline
Brilliant, thanks Jane
Offline
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)
Offline
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..."
Offline
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.
Offline
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)
Offline
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.
Offline
"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?
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?!?!?!
Offline
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)
Offline
Its 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 .Offline
Its the gcd of 133 and 84.
Which is 7 I followed up until "ring theory".
Offline
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
.Offline