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

Quote:

---

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

Quote:

---

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.

Quote:

---

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