Prove that $\{\gcd(10n-1,5n+6) : n \in \mathbb{Z}\}=\{1,13\}$?

Question

So I started with $gcd(10n-1,5n+6)$ States that $d|(10n-1,5n+6)$ Which also implies that $d|10n-1$ and $d|5n+6$. Now I dont know how to show gcd of equals to 1 or 13.

Answer 1

So, $d$ must divide $$2(5n+6)-(10n-1)$$

The basic idea is to eliminate $n$ from the relation to find a constant as dividend.

Answer 2

Use that $(a,b)=(b, a-b).$

Then we have

$$ (10n-1,5n+6)=(5n+6,5n-7)=(5n-7,13)=13 \text{ or } =1. $$