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
Find $k$ values that satisfy $gcd(a,b)=5$

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

My try :


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.

2 Answers

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP