Find the values of $k$ that satisfy $\gcd(a,b)=5$

Question

Let $a$,$b$ and $k$ be integers such that $$a=6k+4$$ $$b=11k+4$$ Find $k$ values that satisfy $\gcd(a,b)=5$

Note: $(a,b)$ are solutions to the equation : $11a-6b=20$

My try :

$\gcd(6k+4,11k+4)=\gcd(k-16;20)=5$

Possible values of $\gcd(a,b)$ are ${1,2,5,10,20}$ so we want $(k-16)$ to be divisible by $5$ but not by $10,20$

So we pose the following :

$k-16 ≡ 5 \pmod{20}$

$k ≡ 1 \pmod{20}$

This means that $k$'s ones number is $1$ so

$k≡ 1\pmod{20}$

$k=10p+1$ , $p$ is an integer.

Answer 1

As Anurag mentioned in the comments, $k \equiv 1 \pmod 5$. Nice work finding that $k \equiv 1 \pmod {10}$. I think that there should be infinite solutions to this. I'm a newbie but those two congruences do have infinitely many solutions, I know that.

Answer 2

Use Euclids algorithm

$\gcd( 6k + 4,11k+4) = \gcd(6k+4, 5k)=\gcd(k+4,5k)=\gcd(k+4, 5k-5(k+4))=\gcd(k+4, -20)=\gcd(k+4,20)$

so $5|k+4$ but $k+4$ is odd.

That is $k+4 \equiv 0 \pmod 5$ or $k\equiv 1 \pmod 5$. And $k+4\equiv 1 \pmod 2$ so $k\equiv 1\pmod 2$ and (we know by Chinese remainder theorem that there is one unique solution $\mod 10$) so $k\equiv 1 \pmod {10}$.

So as long as $k = 10m + 1$ we have

$\gcd(6(10m + 1)+4,11(10m+1)+4)=\gcd(60m+10, 110m + 15)=$

$\gcd(5(12m+2), 5(22m+3)) = 5\gcd(12m+2, 22m+3)=$

$5\gcd(12m+1, 10m+1)=5\gcd(2m,10m+1)=5\gcd(2m, 1)=5$

And if $k = 10m + i; i\ne 1;0\le i \le 9$ we have

$\gcd(6(10m + i)+4,11(10m+i)+4)=\gcd(60m+5i+(4+i), 110m + 10i+(i+4))$

$=\gcd(5[12m+i] + (4+i),5[22m+2i] + (4+i))$.

If that is to equal to $5$ we must have $5|i+4$ but $i\ne 1$ so $i$ must equal $6$

But $\gcd(5[12m+6] + (4+6),5[22m+12] + (4+6))=$

$\gcd(10[6m+3] + 10, 10[11m+6] + 10)=10\gcd(6m+4,11m+7) > 5$.