## Task 24/86

Determine the greatest common divisor $a$ of $b=19^{87}+2$ and $c=86 \cdot 19^{86}+9$, without using the Euclidean algorithm!
We use the lemma: "If $a \in N$ is a common divisor of $b \in N$ and $c \in N$, then $a$ is also a divisor of the difference $d=|x b-y c|$ with $x ; y \in N$.

Proof of the lemma:

Let $a \in N$ satisfy the conditions of the lemma. Then $b=m a$ and $c=n a$ with $m ; n \in N$ and with $x ; y \in N$ we also have

$$
d=|x b-y c|=|x a m-y a n|=|(x m-y n) \cdot a|=|x m-y n| \cdot|a|=|x m-y n| \cdot 8
$$

(The lemma is not reversible, as the example $b=19, c=13, a=2$ shows).

We now set $b=19^{87}+2=19 \cdot 19^{86}+2, c=86 \cdot 19^{86}+9, x=86, y=19$ and obtain

$$
d=\left|86 \cdot\left(19 \cdot 19^{86}+2\right)-19 \cdot\left(86 \cdot 19^{86}+9\right)\right|=|172-171|=1
$$

Thus, only $a=1$ is a common divisor of $b$ and $c$. Therefore, $a=1$ is also the greatest common divisor of $b$ and $c$.

### 2.27 Problems and Solutions 1987