Thread: Euclidean GCD Algorithm (Proof)

1. Euclidean GCD Algorithm (Proof)

I'd like to have a formal proof of the following case (case 2) related to the euclidean GCD algorithm:

We have M > N, and N > M/2, I'd like to show that M - N > M / 2.

Thank you!

2. Re: Euclidean GCD Algorithm (Proof)

You might have inequalities wrong. Also, are there any restrictions on M,N?

Otherwise here's a counterexample.

M= 1.1 N = 1
M > N, N > M/2

M-N = .1
M/2 = .55

.55 > .1, and hence the statement you posted is false.

3. Re: Euclidean GCD Algorithm (Proof)

Thank you for your reply, but we are dealing here with integers.

4. Re: Euclidean GCD Algorithm (Proof)

Originally Posted by mohamedennahdi
Thank you for your reply, but we are dealing here with integers.
Convert M and N from post #2 from dollars to cents; then you'll have a counterexample with integers.

5. Re: Euclidean GCD Algorithm (Proof)

Is this demonstration a valid one:
Let M, N € Z, M > N, and N > M / 2, show that M - N > M / 2:
Basis:
M = 1, N = 0 --> 1 - 0 > 1 / 2 --> 1 > 1 / 2 (TRUE)
Induction:
Assume true k = M, l = N
k - l > k / 2
l > k - k / 2
l > k / 2

6. Re: Euclidean GCD Algorithm (Proof)

Originally Posted by mohamedennahdi
Is this demonstration a valid one:
Originally Posted by emakarov
Convert M and N from post #2 from dollars to cents; then you'll have a counterexample with integers.
.

7. Re: Euclidean GCD Algorithm (Proof)

Originally Posted by mohamedennahdi
Is this demonstration a valid one:
Let M, N € Z, M > N, and N > M / 2, show that M - N > M / 2:

That statement is false.

Let $M=11~\&~N=10$

$M>N,~N>\frac{M}{2}\text{ BUT }M-N\not >\frac{M}{2}~!$

8. Re: Euclidean GCD Algorithm (Proof)

You're right, Plato, let me rectify:
We have M > N, and N > M/2, I'd like to show that M - N < M / 2.

The actual statement that I want to prove is:
case 2: N > M/2. In this case the remainder would be M - N, and since N > M/2, M -
N would be less than M/2.

How would you write a formal proof ?

9. Re: Euclidean GCD Algorithm (Proof)

Originally Posted by mohamedennahdi
We have M > N, and N > M/2, I'd like to show that M - N < M / 2.
How would you write a formal proof ?

$N>\frac{M}{2}\\-N<-\frac{M}{2}\\M-N<\frac{M}{2}$.