Greatest common divisor of 2n+1 and 9n+4

Question

Calculate $GCD(2n+1,9n+4)$ and $GCD(2n-1,9n+4)$

$$GCD(2n+1,9n+4)=GCD(2n+1,9n+4-4 \cdot (2n+1))=GCD(2n+1,n)= GCD(n,1)=1$$

How to calculate $GCD(2n-1,9n+4)$

Answer 1

Eliminate $n$

If integer $d$ divides both, $d$ must divide $2(9n+4)-9(2n-1)=17$

As the positive divisors of $17$ are $1,17$

The gcd will be $17$ iff $17$ divides both $9n+4,2n-1$

If $2n-1\equiv0\pmod{17}\iff2n\equiv1\equiv17+1\iff n\equiv9\pmod{17}$

and then $9n+4\equiv85\equiv0\pmod{17}$

For the first case,

if $D$ divides both $9n+4,2n+1,D$ must divide $9(2n+1)-2(9n+4)=1$