2. The Euclidean algorithm

Problem Q-4. The Euclidean algorithm is an efficient way of finding the greatest common divisor of two integers: Given two positive integers such as 30 and 56, replace the larger one by its remainder after division by the smaller one, and keep repeating this process until one of them is 0. Then the gcd is the other number left. For example, 30 and 56 become 30 and 26, which become 4 and 26, which become 4 and 2, which become 0 and 2, so the gcd is 2.

(a) Explain why this works. (Method: If the integers are $a$ and $b$ with $0 < a < b$, if you divide $b$ by $a$ and get quotient $q$ and remainder $r$, then $b = qa + r$. Show that the set of positive integers that divide both $a$ and $b$ is exactly the same as the set of positive integers that divide both $a$ and $r$. How about the gcd of 0 and $d$, once you have reached that stage? If you wish, you may use the notation common in number theory: $d\vert a$ means ``$d$ divides $a$''. Note: It is OK to divide into 0 but not by 0.)

(b) Find the gcd of 91 and 221 this way.

Problem Q-5. Decide which two numbers $a,b$ between 30 and 60 with $a < b$ will take the most steps of the Euclidean algorithm to get their gcd. (Give your reasoning.)

Problem Q-6. Solving for the gcd as a linear combination.

It is a theorem about integers that if $d =$   gcd$(a,b)$ then there exist integers $r$ and $s$ with $d = ar + bs$. For example, there should be $r$ and $s$ so $2 = 30r + 56s$.

Here is a method to find $r$ and $s$ by getting more information out of the Euclidean algorithm. First, put the two numbers as a column of a matrix augmented by the identity matrix: $\left[\begin{array}{rrr}56&1&0\\ 30&0&1\end{array}\right]$. Then row-reduce as best you can using integer operations only, as follows. At each step, subtract off an integer multiple of one row from the other row so that the left columns follow the Euclidean algorithm. Do not scale rows. You don't need to swap rows either.

$\left[\begin{array}{rrr}56&1&0\\ 30&0&1\end{array}\right] \rightsquigarrow \l... ...\rightsquigarrow \left[\begin{array}{rrr}2&7&-13\\ 0&-15&28\end{array}\right]$.

Now in the last matrix look at the row that has the gcd. This row is in the row space of the original matrix. With what coefficients? Easy--from the identity matrix part, we see that this row with 2 is 7 times the first row of the original matrix minus 13 times the second row. But this says $7 \cdot 56 + (-13) \cdot 30 = 2$.

As a check on arithmetic, since these row operations do not affect determinants, along the way the determinant of the right-hand $2 \times 2$ submatrix should always be 1.

Do this procedure to express the gcd of 91 and 221 as an integer linear combination of these two integers.

(You are not asked to prove the theorem, but this procedure itself really amounts to the proof. Be careful about which coefficient goes with 91 and which with 221, and check your answer.)

Problem Q-7. $p = 101$ is a prime. Find the multiplicative inverse of $97$ in the field $\mathbb{Z}_ {101}$.

(Method: This sounds difficult but it's not. The gcd of a prime $p$ and a number not divisible by $p$ is 1, so you can find $r$ and $s$ with $1 = 101r + 97s$. In $\mathbb{Z}_ {101}$, 101 is the same as 0 so this expression says $1 = 0r + 97s$, so $s$ is the multiplicative inverse. If $s$ is among 0 to $p-1$, you'll need to change it by $\pm$ a multiple of $p$.)