# Math Help - Euclidean Algorithm

1. ## 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

2. 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

3. 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

4. ## 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.

5. 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