For Problem Q-4:

(a) For $b = qa + r$, let's follow the suggestion and show that $a$ and $b$ have the same divisors as $r$ and $b$: If $d\vert a$ and $d\vert b$ then $d\vert qa$ and $d\vert b-qa$, i.e., $d\vert r$. Therefore any divisor of $a$ and $b$ is also a divisor of $r$ and $b$.

If $d\vert a$ and $d\vert r$ then $d\vert qa$ and $d\vert qa+r$, i.e., $d\vert b$. Therefore any divisor of $r$ and $b$ is a divisor of $a$ and $b$.

Here we have use the pretty obvious idea that if $d$ divides $a$ then $d$ divides any integer multiple of $a$ and also the idea that if $d$ divides two integers then it also divides their sum and difference. Since ``$d$ divides $a$'' means ``$a = kd$ for some integer $k$'', these rules are not hard to prove officially.

(b) $221 = 2 \cdot 91 + 39$; $91 = 2 \cdot 39 + 13$; $39 = 3 \cdot 13 + 0$, so the gcd is $13$.

(There was some secret algebra in inventing this problem: $(10+3)(10-3) = 100 - 9 = 91$ and $(15+2)(15-2) = 15^2 - 2^2 = 225 - 4 = 221$. Both of these involve 13.)

For Problem Q-5:

Some informal reasoning that could be made official:

Run the Euclidean algorithm backwards. The integers involved should build up as slowly as possible when the final result, the gcd, is 1 and $q$ is 1 in every step--except the last (or the first going backwards), where $q = 1$ won't work since the list of numbers used has to increase. So going backwards, we have

$2 = 2 \cdot 1 + 0$
$3 = 1 \cdot 2 + 1$
$5 = 1 \cdot 3 + 2$
$8 = 1 \cdot 5 + 3$
$13 = 1 \cdot 8 + 5$
$21 = 1 \cdot 13 + 8$
$34 = 1 \cdot 21 + 13$
$55 = 1 \cdot 34 + 21$.

Note (not part this course). The sequence $1, 2, 3, 5, 8,\dots$, in which each number from the third on is the sum of the preceding two, consists of the Fibonacci numbers (fib-o-na-chi). Actually it's better to start with $0,1$, getting $0,1,1,2,3,5,8,\dots$, even though that doesn't quite fit the Euclidean algorithm application.

Fibonnaci numbers have a close connection to the golden mean (golden ratio) of the ancient Greeks, the number that is the positive solution of the equation $r^2 = r + 1$, specifically $r = (1 + \sqrt 5)/2 \approx 1.618$. In fact, the $n$-th Fibonacci number is the integer closest to $r^n/\sqrt 5$ if we agree that 0 is the 0-th Fibonacci number. For example, $r^9/\sqrt 5 \approx 33.9941$ and $r^{10}/\sqrt 5 \approx 55.0036$. Fibonacci numbers and the golden mean turn up in unexpected places.

For Problem Q-6:

$\left[\begin{array}{ccc}91&1&0\\ 221&0&1\end{array}\right] \rightsquigarrow \... ...] \rightsquigarrow \left[\begin{array}{ccc}13&5&-2\\ 0&-17&7\end{array}\right]$.

As a check notice that the right $2 \times 2$ determinant is still 1. Now we can see that $(13,5,-2)$ has to be $5(91,1,0) -2(221,0,1)$, so $13 = 5 \cdot 91 - 2 \cdot 221$. This checks.

For Problem Q-7:

As suggested, $\left[\begin{array}{ccc}101&1&0\\ 97&0&1\end{array}\right] \rightsquigarrow ... ... \left[\begin{array}{ccc}1&4&-1\\ 1&-24&25\end{array}\right] \rightsquigarrow$
$\left[\begin{array}{ccc}0&97&101\\ 1&-24&25\end{array}\right]$. Then $(1,-24,25) = -24(101,1,0) + 25(97,0,1)$, so $1 = -24 \cdot 101 + 25 \cdot 97$ (which is true). Then in $\mathbb{Z}_ {101}$, $1 = 25 \cdot 97$ and the multiplicative inverse of $97$ is $25$.

The moral is that finding inverses in fields $\mathbb{Z}_ p$ is fast and easy on a computer, even if $p$ is a large prime. (For a computer, large can mean very large-even 200 digits!)