Reading: Read sections 6.6, 6.7, 15.6
Exercises:
Use the Euclidean Algorithm to find integers \(m, n\) in the equation \(\gcd(91, 161) = m91 + n161\).
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*}\]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\).
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\).
Use the Euclidean Algorithm to compute \(\gcd(89, 55)\).
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.
The Euclidean algorithm takes \(10\) steps to show that the GCD is 1.
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})\).