We just had about the greatest common divisor, gcd(a,b). We've seen the proof, and now we have to prove that the gcd(a,b) = gcd(a,b-ax). I'm sitting here have troubles even starting the problem. It also says that a,b,x is in Z. I see that if x is 0, then it says that gcd(a,b) = gcd(a,b) which is of course true. And it also seems that the highest x can be is the gcd(a,b), since if it goes any higher than the greatest common divisor, that will of course be the greater common divisor. I'm not really sure how to even start this problem, and am I supposed to prove it always works, since couldn't I just say that x always have to be 0? Or do I need to prove that it works for all the numbers from 0 up to the gcd(a,b) or am I misunderstanding the problem completely? It would be nice if anyone could just give me some ideas to start it off, I would be very grateful.
Greatest common divisor
- Thread starter Fisk92
- Start date
- Joined
- Feb 4, 2004
- Messages
- 16,583
Does this mean that your class has just covered the topic of the Greatest Common Divisor?
You've "seen the proof" of what, exactly?
What information were you given about "x"?
Does "it" mean "the instructions for the exercise"?
Does "it" mean "the equation that I've been asked to prove"?
How did you arrive at this conclusion? For instance, if a = 3, b = 6, and x = 5, so GCD(a, b) = 3, then we have:
. . . . .b - ax = 6 - 15 = -9
...and the GCD is still 3.
My bad, I have formulated it extremely wrong. I'll try again.
Before we were introduced the GCD, we were to solve that for all (a,b) there exists an unique (b,r) that follows that a = b * k + r. And I'm pretty sure that a, b, k, r is in N. Also that r is bigger or equal to 0 but lesser than b. We've seen that for every b there is, we can write b = the r from before, and times k(1), + another r. And we can keep doing this and since r becomes smaller and smaller at some point it hits zero, and that means everything "adds up", that it ends with b = r from before * another number + 0, which means it's a whole nubmer since they're all whole, and that means a = b*k + r is possible. I'm writing extremely cluttered because I don't how to exactly write the formal proof, so if anyone knows it, it would be nice if they could make it easier to read.
We were then introduced to GCD, and what it did. And now we have to prove that the GCD(a,b) = GCD(a,b-ax). Also I made a mistake. A,b and x belongs to N. but I cannot find any more info on x. I hope it answered some questions, but I might just be confused because I don't really understand the problem, if anyone had the same it would be nice if they could clear up my misunderstandings.
Before we were introduced the GCD, we were to solve that for all (a,b) there exists an unique (b,r) that follows that a = b * k + r. And I'm pretty sure that a, b, k, r is in N. Also that r is bigger or equal to 0 but lesser than b. We've seen that for every b there is, we can write b = the r from before, and times k(1), + another r. And we can keep doing this and since r becomes smaller and smaller at some point it hits zero, and that means everything "adds up", that it ends with b = r from before * another number + 0, which means it's a whole nubmer since they're all whole, and that means a = b*k + r is possible. I'm writing extremely cluttered because I don't how to exactly write the formal proof, so if anyone knows it, it would be nice if they could make it easier to read.
We were then introduced to GCD, and what it did. And now we have to prove that the GCD(a,b) = GCD(a,b-ax). Also I made a mistake. A,b and x belongs to N. but I cannot find any more info on x. I hope it answered some questions, but I might just be confused because I don't really understand the problem, if anyone had the same it would be nice if they could clear up my misunderstandings.
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,382
x has to be an integer.
The problem for example is saying that gcd(6,27)=gcd(6,27-6x). That is gcd(6,27)= gcd(6,27)=gcd(6,21)=gcd(6,15)=gcd(6.9)=gcd(6,3)=....
Is this always true for any a and b in Z? If yes, then prove it!
Will taking a from b (and getting c) yield that gcd(a,b) = gcd(a,c)? This is basically what you need to prove or show a counter example
Alright, I think I understand. Just to be completely sure. So what I need to prove is that if we have the gcd(a,b), then the gcd(a, b-ax) will be equal to that. And I have to prove it no matter what x, so that for all pairs of (a,b) all x'es in gcd(a,b) =gcd(a,b-ax) has to make the equation true?
Here is a fairly intuitive but lengthy way to do deal with this.
\(\displaystyle m \text { is a common divisor of } (a,\ b) \iff\)
\(\displaystyle a,\ b \in \mathbb Z,\ m \in \mathbb N^+ \text { and } \exists\ p,\ q \in \mathbb Z \text { such that } mp = a \text { and } mq = b.\)
Buy that as a definition?
\(\displaystyle \text {Given: } x \in \mathbb Z\ \text { and } m \text { is a common divisor of } (a,\ b).\)
\(\displaystyle a,\ b,\ x \in \mathbb Z \implies b - ax \in \mathbb Z \implies a,\ b - ax \in \mathbb Z.\)
\(\displaystyle \exists\ p,\ q \in \mathbb Z \text { such that } mp = a \text { and } mq = b \implies\)
\(\displaystyle b - ax = mq - (mp)x = m(q - px) = mr, \text { where } r = q - px.\)
\(\displaystyle \text {But } p,\ q,\ x \in \mathbb Z \implies r \in \mathbb Z.\)
\(\displaystyle \therefore a,\ b - ax,\ p,\ r \in \mathbb Z,\ m \in \mathbb N^+, \text { and } mp = a \text { and } mr = b - ax \implies\)
\(\displaystyle m \text { is a common divisor of } (a,\ b - ax).\)
Now show that if m is a common divisor of (a, b - ax) for any integer x, it is a common divisor of (a, b). At that point you have shown that the two sets of common divisors are equal. Consequently the largest number in each set set is equal.
\(\displaystyle m \text { is a common divisor of } (a,\ b) \iff\)
\(\displaystyle a,\ b \in \mathbb Z,\ m \in \mathbb N^+ \text { and } \exists\ p,\ q \in \mathbb Z \text { such that } mp = a \text { and } mq = b.\)
Buy that as a definition?
\(\displaystyle \text {Given: } x \in \mathbb Z\ \text { and } m \text { is a common divisor of } (a,\ b).\)
\(\displaystyle a,\ b,\ x \in \mathbb Z \implies b - ax \in \mathbb Z \implies a,\ b - ax \in \mathbb Z.\)
\(\displaystyle \exists\ p,\ q \in \mathbb Z \text { such that } mp = a \text { and } mq = b \implies\)
\(\displaystyle b - ax = mq - (mp)x = m(q - px) = mr, \text { where } r = q - px.\)
\(\displaystyle \text {But } p,\ q,\ x \in \mathbb Z \implies r \in \mathbb Z.\)
\(\displaystyle \therefore a,\ b - ax,\ p,\ r \in \mathbb Z,\ m \in \mathbb N^+, \text { and } mp = a \text { and } mr = b - ax \implies\)
\(\displaystyle m \text { is a common divisor of } (a,\ b - ax).\)
Now show that if m is a common divisor of (a, b - ax) for any integer x, it is a common divisor of (a, b). At that point you have shown that the two sets of common divisors are equal. Consequently the largest number in each set set is equal.
I hope I understood what you meant, but I'm not sure what you're asking for in the last bit. Didn't we start assuming that m was a common divisor for (a,b)? So if I understand correctly what you did was, saying that the gcd(a,b) = some number, let's call it k.
Since k is the gcd(a,b) k|a and k|b must be true. That means kp = a, and kq = b. So we look at the line, b-ax and out from the info that the gcd(a,b)=k, we can replace b and a, so it says kq-kp*x and then take k out, so k(q-px), and then q-px is some whole number since q, p and x is whole numbers it also has to be a whole number, so we can call it r. So it now says that b-ax is the same as k*r. So we statred by saying gcd(a,b)=k, and now we see that b-ax=k*r and we also know that a = kp,
So a = kp, and b-ax = kr, so that means the gcd of a and b-ax is k? Is that correctly understood, or did I misunderstand something?