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

Mathematics Asked by ricin on January 5, 2022

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≡ 1pmod{20}$$

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

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 $$kequiv 1 pmod 5$$. And $$k+4equiv 1 pmod 2$$ so $$kequiv 1pmod 2$$ and (we know by Chinese remainder theorem that there is one unique solution $$mod 10$$) so $$kequiv 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)) = 5gcd(12m+2, 22m+3)=$$

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

And if $$k = 10m + i; ine 1;0le 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 $$ine 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)=10gcd(6m+4,11m+7) > 5$$.

Answered by fleablood on January 5, 2022

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.

Answered by OlympusHero on January 5, 2022