Using the Euclidean algorithm to show that $\gcd(11k+7, 5k+3)=1$

Question

Came across this question in the textbook and I've ran into some difficulties whilst attempting it:

$11k+7 = 2(5k+3) + (k+1)$

For $\gcd(5k+3,k+1)$ I am not sure on how to factor $k+1$ into $5k+3$, as the approaches I attempted do not seem to lead to what needs to be shown.

I then went ahead and tried to show that there are integers a, b such that:

$(11k+7)a + (5k+3)b = 1,$

however, solving the resulting simultaneous equations:

$11a + 5b = 0; 7a + 3b = 1$

seem to lead to the contrary being shown. What am I doing wrong here?

Answer 1

The main problem is that the claim is false: try an odd value of $k$ and see what happens. However, the Euclidean algorithm can still be carried out. You have $11k+7=2(5k+3)+(k+1)$, which is fine. Then

$$5k+3=4(k+1)+(k-1)\;,$$

and

$$k+1=(k-1)+2\;,$$

so you want $\gcd(k-1,2)$. If $k$ is odd, this is clearly $2$; if $k$ is even, it’s equally clearly $1$. Thus

$$\gcd(11k+7,5k+3)=\begin{cases} 1,&\text{if }k\text{ is even}\\ 2,&\text{if }k\text{ is odd}\;. \end{cases}$$