3. The greatest common divisor of two natural numbers $a$ and $b$ is $d$. Determine the greatest common divisor of the numbers $5a + 3b$ and $13a + 8b$.
Solution. $\operatorname{GCD}(5 a+3 b, 13 a+8 b)=d_{1}, \operatorname{GCD}(a, b)=d$, $8(5 a+3 b): d_{1}, 3(13 a+8 b): d_{1} \Rightarrow(8(5 a+3 b)-3(13 a+8 b)): d_{1} \Rightarrow a: d_{1}$. $13(5 a+3 b): d_{1}, 5(13 a+8 b): d_{1} \Rightarrow(13(5 a+3 b)-5(13 a+8 b)): d_{1} \Rightarrow b: d_{1}$. $\Rightarrow d: d_{1}$.

Since $a: d$ and $b: d$, then $5 a+3 b: d$ and $13 a+8 b: d, \Rightarrow d_{1}: d$. Thus, $d_{1}=d$.

Answer: $d$.