Prove that the gcd of ( 8n+19 , 3n+7 ) =1

Question

I want to show that the gcd of $( 8n+19 , 3n+7 ) =1$ $\forall n \in \mathbb{Z}$. I would like to prove this through mathematical induction and generalize it for the set of all integers.

Base Case: $n=1$

$$gcd(8+19,3+7) = gcd(27,10) = 1 $$

Assume $n = k$ holds.

WTS it is also true for $n=k+1$. $$gcd(8k+27,3k+10)=1$$

I am stuck here, please let advise me on how to continue from here. Also I am not sure if mathematical induction is the right approach. If a more elegant approach exists, please let me know.

Answer 1

Is suffices to find $x,y\in \mathbb{Z}$ such that $$ (8n+19)x+(3n+7)y=1 $$ that is $n(8x+3y)+(19x+7y)=1$. In order to do so, let us find $x,y$ such that $$ \begin{cases} 8x+3y=0\\ 19x+7y=1 \end{cases} $$ And the solution of the last system is $x=3$, $y=-8$.

Answer 2

Another approch would be consider the polynomials of $\mathbb{Q}[x]$, \begin{align} f(x)&=8x+19,\\g(x)&=3x+7. \end{align} Divide $f(x)$ by $g(x)$, you get $$ f(x)=\frac{8}{3}g(x)+\frac{1}{3} $$ and then $$ 1=3f(x)-8g(x). $$ In particular, for all $n\in\mathbb{N}\subseteq\mathbb{Q}$, $$ 1=3f(n)-8g(n). $$ This is a Bézout identity which tells you that gcd$(f(n),g(n))=1$, for all $n\in\mathbb{N}$, which is what you want to prove.