Thread: 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

Originally Posted by pwr_hngry

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

Originally Posted by pwr_hngry

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

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.

Originally Posted by mathshelpneeded

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