# 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;

\begin{align*} 161 &= (1)91 + 70 \\ 91 &= (1)70 + 21 \\ 70 &= (3)21 + 7 \\ 21 &= (3)7 \end{align*}

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

\begin{align*} 7 &= 70 - 3(21) \\ &= 70 - 3(91 - 70) \\ &= 4(70) - 3(91) \\ &= 4(161 - 91) - 3(91) \\ &= 4(161) - 7(91). \end{align*}
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

\begin{align*} 43 &= 5(8) + 3 \\ 8 &= 2(3) + 2 \\ 3 &= 1(2) + 1 \\ \; \\ 1 &= 3 - 2 \\ &= 3 - (8 - 2(3)) \\ &= 3(3) - 8 \\ &= 3(43 - 5(8)) - 8 \\ &= 3(43) - 16(8) \end{align*}

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})$$.