If $a$ is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$

Question

If $a$ is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$

-We have just started the section on greatest common divisor, one thing I know is that $gcd(a,b) = ax + by$

-My initial thought is that we would plug our values into that equation to get the following:

$$(14a + 3)x + (21a + 4)y = 1$$

-I am a bit confused as to how to proceed though, as I assume that I have to prove this for all values of a. Any help is appreciated.

Answer 1

Using Euclidean algorithm: \begin{align} \gcd(14a+3,21a+4)&=\gcd(14a+3,7a+1)\\ &=\gcd(7a+1,1)\\ &=1 \end{align}

Equivalently, and more directly, \begin{align} (14a+3)(3)+(21a+4)(-2)&=(42a+9)-(42a+8)\\ &=1 \end{align}

Answer 2

$$21a + 4= 14a + 3 +7a+1\implies \gcd(14a + 3, 21a + 4) = \gcd(14a + 3, 7a + 1).$$

$$14a + 3= 7a + 1 +7a+2\implies \gcd(14a + 3, 7a + 1)=\gcd(7a + 2, 7a + 1).$$

$$7a + 2= 7a + 1 +1\implies \gcd(7a + 2, 7a + 1)=\gcd(7a + 1, 1)=1.$$