**Definition**

Fibonacci numbers grow rapidly.

**Proof By Induction**

Base Case:

n = 6,7 (by direct computation)

Inductive step:

Formula For nth Fibonacci Number

**Definition**

Fibonacci numbers grow rapidly.

**Proof By Induction**

Base Case:

n = 6,7 (by direct computation)

Inductive step:

Formula For nth Fibonacci Number

**Naive Algorithm**

Function NaiveGCD(a, b) best <- 0 for d from 1 to a+b: if d|a and d|b: best <- d return best

- Runtime approximately a+b
- Very slow for 20 digit numbers

**Python Implementation**

def gcd(m, n): gc = 0 for i in range(1, m+n): if m % i == 0 and n % i == 0: gc = i return gc default_a = 3918848 default_b = 1653264 a = input("Enter a: [%s]" % default_a) b = input("Enter b: [%s]" % default_b) a = a or default_a b = b or default_b g = gcd(int(a), int(b)) print("GCD is: ", g)