Results 1 to 9 of 9
Like Tree2Thanks
  • 1 Post By Plato
  • 1 Post By Plato

Math Help - Euclidean GCD Algorithm (Proof)

  1. #1
    Junior Member
    Joined
    Jul 2012
    From
    Morocco
    Posts
    25

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2012
    From
    Morocco
    Posts
    25

    Re: Euclidean GCD Algorithm (Proof)

    Thank you for your reply, but we are dealing here with integers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Euclidean GCD Algorithm (Proof)

    Quote Originally Posted by mohamedennahdi View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2012
    From
    Morocco
    Posts
    25

    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Euclidean GCD Algorithm (Proof)

    Quote Originally Posted by mohamedennahdi View Post
    Is this demonstration a valid one:
    Quote Originally Posted by emakarov View Post
    Convert M and N from post #2 from dollars to cents; then you'll have a counterexample with integers.
    .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1582
    Awards
    1

    Re: Euclidean GCD Algorithm (Proof)

    Quote Originally Posted by mohamedennahdi View Post
    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}~!
    Thanks from mohamedennahdi
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jul 2012
    From
    Morocco
    Posts
    25

    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 ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1582
    Awards
    1

    Re: Euclidean GCD Algorithm (Proof)

    Quote Originally Posted by mohamedennahdi View Post
    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}.
    Thanks from mohamedennahdi
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean algorithm
    Posted in the Algebra Forum
    Replies: 7
    Last Post: October 7th 2012, 06:40 AM
  2. Euclidean Algorithm Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 11th 2010, 04:16 AM
  3. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  4. Euclidean algorithm proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 28th 2009, 07:03 PM
  5. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:20 AM

Search Tags


/mathhelpforum @mathhelpforum