# 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

## Related Questions

### Complete DVR containing a field isomorphic to residue field

2  Asked on December 8, 2021 by uno

### Positive semi-definite real matrix with unit diagonal

1  Asked on December 8, 2021 by fq00

### Prove $prod_{nge0}^{ }frac{left(n+aright)left(n+bright)}{left(n+cright)left(n+dright)}=frac{Gamma(c)Gamma(d) }{ Gamma(a)Gamma(b)}$

1  Asked on December 8, 2021

### Closed-form expression for $prod_{n=0}^{infty}frac{(4n+3)^{1/(4n+3)}}{(4n+5)^{1/(4n+5)}}$?

1  Asked on December 8, 2021 by harukr

### Examples of topological Immersion which are not embedding

0  Asked on December 8, 2021

### Is $sin(frac{1}{|z|})$ holomorphic on $Bbb C-{0}$?

2  Asked on December 8, 2021

### Show that $V=Z(x;T)oplus Z(y;T)$ and the $T$-annihilators $mu_{T,x},,mu_{T,y}$ do not share any common divisors implies that $V$ is cyclic

2  Asked on December 8, 2021

### What is exponential map in differential geometry

1  Asked on December 6, 2021

### Question on cardinality of sets

1  Asked on December 6, 2021 by jshthng

### Riemann-Roch and sum of powers

0  Asked on December 6, 2021

### how to integrate a function like this: $int_0^x frac{(t)^{a-1}}{(x-t)^a} dt$

1  Asked on December 6, 2021 by marooz

### Why does $frac{n!n^x}{(x+1)_n}=left(frac{n}{n+1}right)^xprod_{j=1}^{n}left(1+frac{x}{j}right)^{-1}left(1+frac{1}{j}right)^x$

1  Asked on December 6, 2021

0  Asked on December 6, 2021 by ammrra

### Show that $V=text{Fix}(phi )oplus text{Eig}(-1, phi)$

1  Asked on December 6, 2021

### Evaluate $lim _{xto 0} frac{e^x+e^{-x}-2}{xtan x}$

4  Asked on December 6, 2021

### Show that the restriction is diagonalizable

1  Asked on December 6, 2021

### Expectation = Probability?

1  Asked on December 6, 2021 by code-mx

### Every $2$-dimensional commutative $k$-algebra with only one prime ideal is isomorphic to $k[x]/(x^2)$

2  Asked on December 6, 2021 by leviathantheesper

### Problem with $A.M.geq G.M.$ Inequality

6  Asked on December 6, 2021 by general-kenobi

### Matrix Norm With Respect to Another Matrix?

1  Asked on December 6, 2021