# Harrison Chapman

## Math 301: Homework 6

Due: Friday, October 18, 2019

Exercises:

1. Use the Euclidean Algorithm to find integers $$m, n$$ in the equation $$\gcd(91, 161) = m91 + n161$$.

1. The Euclidean algorithm gives the remainder calculations;

So $$7$$ is the GCD, and we combine the equations to get

2. Show that for any two integers $$a, b$$; $$\DeclareMathOperator{lcm}{lcm}\gcd(a,b)\lcm(a,b) = ab$$.

Let $$p_1, \cdots, p_k$$ be all of the primes that appear in the prime factorizations of either $$a$$ or $$b$$. Then there exist non-negative integer coefficients $$e_1, \cdots, e_k$$ and $$f_1 \cdots, f_k$$ so that

$a = p_1^{e_1} \cdots p_k^{e_k} \quad b = p_1^{f_1} \cdots p_k^{f_k}.$

Now with this in mind, the GCD and LCM can be written,

$\gcd(a,b) = p_1^{\min(e_1,f_1)} \cdots p_k^{\min(e_k,f_k)} \quad \lcm(a,b) = p_1^{\max(e_1,f_1)} \cdots p_k^{\max(e_k,f_k)}.$

The result follows from observing that $$\min(e_i,f_i) + \max(e_i,f_i) = e_i + f_i$$.

3. Find an integer $$x$$ between 0 and 42 that satisfies $$8x \equiv 4 \mod 43$$.

First we solve for the multiplicative inverse of $$8$$ by solving $$8y \equiv 1 \mod 43$$. We have that

So $$y = -16$$ satisfies, and we multiply the congruence we are solving to get the equivalent congruence $$x \equiv -64 \mod 43$$ and so we get $$x = -64 + 2(43) = 22$$.

1. Use the Euclidean Algorithm to compute $$\gcd(89, 55)$$.

2. Notice that $$89 = F_{11}$$ and $$55 = F_{10}$$ are both Fibonacci numbers. Call a division step of the Euclidean Algorithm a step where we have $$a < b$$ and we replace $$\gcd(a,b)$$ by $$\gcd(a,r)$$.

Find inputs $$a$$ and $$b$$ so that computing $$\gcd(a,b)$$ requires at least 100 division steps.

1. The Euclidean algorithm takes $$10$$ steps to show that the GCD is 1.

2. By the recurrence of the Fibonacci numbers $$F_n = F_{n-1} + F_{n-2}$$ we see that it would take 100 steps to find $$\gcd(F_{101}, F_{100})$$.