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

2 Asked on December 8, 2021 by uno

commutative algebra formal completions power series valuation theory

1 Asked on December 8, 2021 by fq00

1 Asked on December 8, 2021

1 Asked on December 8, 2021 by harukr

0 Asked on December 8, 2021

2 Asked on December 8, 2021

2 Asked on December 8, 2021

1 Asked on December 6, 2021

1 Asked on December 6, 2021 by marooz

1 Asked on December 6, 2021

1 Asked on December 6, 2021

4 Asked on December 6, 2021

calculus limits limits without lhopital solution verification

1 Asked on December 6, 2021

1 Asked on December 6, 2021 by code-mx

integration limits multiple integral multivariable calculus probability

2 Asked on December 6, 2021 by leviathantheesper

6 Asked on December 6, 2021 by general-kenobi

1 Asked on December 6, 2021

Get help from others!

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

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