Results 1 to 5 of 5

Math Help - Euclidean Algorithm

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    23

    Euclidean Algorithm

    Hello again,

    Here is another one that is giving me trouble.

    I have 2 given integers: 110, 273
    I am supposed to find the greatest common divisor of the pair using the Euclidean Algorithm:

    Input: a and b (nonnegative integers, not both zero)
    Output: Greatest common divisor of a and b

    gdc(a,b) {
    if(a<b)
    swap(a,b)
    while (b not=0) {
    r=a mod b
    a = b
    b = r
    }
    return a
    }

    hope this makes sense.
    Any help with this would be greatly appreciated.

    Pwr
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by pwr_hngry View Post
    Hello again,

    Here is another one that is giving me trouble.

    I have 2 given integers: 110, 273
    I am supposed to find the greatest common divisor of the pair using the Euclidean Algorithm:

    Input: a and b (nonnegative integers, not both zero)
    Output: Greatest common divisor of a and b

    gdc(a,b) {
    if(a<b)
    swap(a,b)
    while (b not=0) {
    r=a mod b
    a = b
    b = r
    }
    return a
    }

    hope this makes sense.
    Any help with this would be greatly appreciated.

    Pwr
    And what is the problem, that is the Euclidean algorithm, so why not
    just trace through this with a=110 and b=273.

    Code:
     
       a       b       r       a'       b'
      110     273     53      110      53
      110      53      4       53       4
       53       4      1        4       1
        4       1      0        1       0
    So gcd(110,273)=1

    RonL
    Last edited by CaptainBlack; May 7th 2007 at 04:19 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by pwr_hngry View Post
    Hello again,

    Here is another one that is giving me trouble.

    I have 2 given integers: 110, 273
    I am supposed to find the greatest common divisor of the pair using the Euclidean Algorithm:

    Input: a and b (nonnegative integers, not both zero)
    Output: Greatest common divisor of a and b

    gdc(a,b) {
    if(a<b)
    swap(a,b)
    while (b not=0) {
    r=a mod b
    a = b
    b = r
    }
    return a
    }

    hope this makes sense.
    Any help with this would be greatly appreciated.

    Pwr

    Note there is no need to do the swap, as if a<b first time through the
    while loop will swap them as:

    a mod b = a

    if a<b.

    So you can neaten your algorithm to:

    Code:
    gdc(a,b) {
      while (b not=0) {
        r=a mod b
        a = b
        b = r
      }
      return a
    }
    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2007
    Posts
    18

    mathematical proof by induction

    Prove:

    1. 3^n > n^3 for all n, n>3

    Please help i don't understand, i know how to do proof by induction but when i tried to make 3^(k+1) > (k+1)^3
    it looked so terribly wrong.
    thanks.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by mathshelpneeded View Post
    Prove:

    1. 3^n > n^3 for all n, n>3

    Please help i don't understand, i know how to do proof by induction but when i tried to make 3^(k+1) > (k+1)^3
    it looked so terribly wrong.
    thanks.
    Let P(n) denote the statement: 3^n > n^3

    A) when n=4; 3^4= 81, and 3^3=27, so P(4) is true.

    B) Suppose P(k) is true, then by assumption 3^k > n^3.

    so:

    3(3^k) > 3 n^3,

    or 3^{k+1} > 3 n^3 ...(Ieq1)

    Now for k>4; 3k^3>(k+1)^3 since:

    (k+1)^3 = k^3 + 3 k^2 + 3 k +1

    so:

    (k+1)^3 /k^3 = 1 + 3/ k + 3/ k^2 +1/k^3

    and if k>=4

    (k+1)^3 /k^3 <= 1 + 3/ 4 + 3/ 4^2 +1/4^3 < 1.95

    so:

    (k+1)^3 < 1.95 k^3 < 3 k^3

    Thefore Ineq1 becomes:

    3^{k+1} > 3 k^3 > (k+1)^3 ... (Ineq2)

    Which is P(k+1), so by assuming P(k) with k>=4 we have proven P(k+1)
    which together with (A) above proves by mathematical induction that:

    3^n > n^3 for all n, n>3

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 11:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 07:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 07:45 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 04:20 AM
  5. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 09:28 AM

Search Tags


/mathhelpforum @mathhelpforum