# Euclidean Algorithm

• May 6th 2007, 01:57 PM
pwr_hngry
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
• May 7th 2007, 03:08 AM
CaptainBlack
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
• May 12th 2007, 02:00 AM
CaptainBlack
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
• May 13th 2007, 06:48 AM
mathshelpneeded
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.
• May 13th 2007, 07:20 AM
CaptainBlack
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