Question

Please help: (Proving the Euclidean algorithm maybe?) Here's the question:
Show that if a 13 years ago

Answer 1

Start with \(g=\gcd(a, b)\). This means that \(g|a\) and \(g|b\). By some properties of divisible, you have that \(g|k\,a\) where \(k\) is an integer. Also, this means that \(g|b-k\,a\) since if a number divides two other numbers, it divides their difference.

Answer 2

Thus, \(g|a\) and \(g|(b-k\,a)\). Since \(0<b-k\,a<b\) this means that \(g\) is also the gcd of a and b-ka.

Answer 3

I suppose I should have put \(0\leq b-k\,a<a\) instead.

Answer 4

So would this be correct:
Show that if a<b, then gcd(a,b) = gcd(a, b-ka), where 0≤ b-ka < a

Let g = gcd(a,b)
(Let m = gcd(a, b-ka)
Show g = m) DO I NEED THIS PART???

We know that g|a and g|b
So g| (b-a)

We know that g|ka for some integer k, and g|b
So g| (b-ka)

OR USING M... We know that m|a and m|b-ka
So m| (a + (b - ka))
So m| a (b-k)

See I'm lost on how to say it... :(

Therefore g|a and g| (b-ka)

Answer 5

The way you're trying to do it would work if you were to show that \(m\leq g\) and that \(g\leq m\).

Answer 6

Here's what our teacher gave us to start from and told us to modify it for this new problem. He said:
If a <b, then gcd(a, b) = gcd (a, b-a)
Let d= gcd(a,b)
Let m = gcd (a, b-a)
Show d= m

We know that d|a and d|b
So d| (b-a)
Therefore d|a and d| (b-a)
So d ≤ m

We know that m|a and m| (b-a)
So m| (a + b - a)
d| b
Therefore m|a and m|b
So m ≤ d

So m = d

I need to modify all of that for "If a <b, then gcd (a, b) = gcd (a, b-ka), where 0 ≤ b - ka < a "

Answer 7

So you would have something like this.

Let g= gcd(a,b)
Let m = gcd (a, b-ka)
Show g= m

We know that g|a and g|b so g|ka,
So g| (b-ka)
Therefore g|a and g| (b-ka)
So g ≤ m

We know that m|a and m| (b-ka)
So m| (a + b - ka) so m|(a(1-k)+b)
Since m|a, m|(a(1-k))
Thus, m| b
Therefore m|a and m|b
So m ≤ g

So m = d

Answer 8

There's just a few extra steps in there to show that \(m\leq g\)

Answer 9

you put in the extra steps?
or should I figure those out...

Answer 10

I already put the extra steps in the explanation.

Answer 11

Although it should say \(m=g\) at the end. Not m=d

Answer 12

ok thanks, so should that last part say

We know that m|a and m| (b-ka)
So m| (a + b - ka) so m|(a(1-k)+b)
Since m|a, m|(a(1-k)), and m| b
Therefore m|a and m|b
So m ≤ g
So m = d

Guess I'm confused how you can say Thus m| b

Answer 13

Suppose \(m \nmid b\). Since \(m|a(1-k)\) we can write it as \(a(1-k))=mz\) where \(z\in\mathbb{Z}\). This means that \(m|mz+b\) so we need to be able to factor an \(m\) our of \(mz+b\). If \(m \nmid b\) then it's impossible! This is a contradiction, so \(m|b\).

Answer 14

Ok, so I should include that contradiction in the problem, or is it generally understood?

Answer 15

That's generally understood. I probably wouldn't include it in one of my proofs.

Answer 16

Gotcha. Thank you so much for your help, you are awesome :D

Answer 17

You're welcome.