+0

# How do we do these questions

0
230
4

idk how. can u like, explain how this can be done easily?

As n  ranges over the positive integers, what is the maximum possible value that the greatest common divisor of  13n + 8 and  5n+3 can take?

Jul 22, 2019

### 4+0 Answers

#1
+24388
+2

idk how. can u like, explain how this can be done easily?

As n  ranges over the positive integers, what is the maximum possible value that the greatest common divisor of  13n + 8 and  5n+3 can take?

Formula: $$\boxed{\gcd(a,b)=gcd(a-b,b)}$$

$$\begin{array}{|rcll|} \hline && \mathbf{gcd(13n + 8, 5n+3)} \\ &=& gcd\left(13n+8-(5n+3), 5n+3\right) \\ &=& gcd\left(13n+8-5n-3, 5n+3\right) \\ &=& gcd\left(8n+5, 5n+3\right) \\ &=& gcd\left(8n+5-(5n+3), 5n+3\right) \\ &=& gcd\left(8n+5-5n-3, 5n+3\right) \\ &=& gcd\left(3n+2, 5n+3\right) \\ &=& gcd\left(5n+3,3n+2\right) \\ &=& gcd\left(5n+3-(3n+2),3n+2\right) \\ &=& gcd\left(5n+3-3n-2,3n+2\right) \\ &=& gcd\left(2n+1,3n+2\right) \\ &=& gcd\left(3n+2,2n+1\right) \\ &=& gcd\left(3n+2-(2n+1),2n+1\right) \\ &=& gcd\left(3n+2-2n-1,2n+1\right) \\ &=& gcd\left(n+1,2n+1\right) \\ &=& gcd\left(2n+1,n+1\right) \\ &=& gcd\left(2n+1-(n+1),n+1\right) \\ &=& gcd\left(2n+1-n-1,n+1\right) \\ &=& gcd\left(n,n+1\right) \\ &=& gcd\left(n+1,n\right) \\ &=& gcd\left(n+1-(n),n\right) \\ &=& gcd\left(n+1-n,n\right) \\ &=& gcd\left(1,n\right) \\ &=& gcd\left(n,1\right) \\ &=& \mathbf{1} \\ \hline \end{array}$$

The maximum possible value is $$\mathbf{1}$$

Jul 22, 2019
#2
+1694
+3

Great Solution, Heureka!

tommarvoloriddle  Jul 22, 2019
#3
+1

Suppose that the greatest common divisor is k, and that

$$\displaystyle 13n+8=m_{1}k\dots (1)\\\text{and that }\\5n+3=m_{2}k\dots(2).$$

From (1)

$$\displaystyle 65n+40=5m_{1}k\dots(3) \\ \text{and from (2),} \\ 65n+39=13m_{2}k\dots(4).$$

Subtracting (4) from (3),

$$\displaystyle 1=(5m_{1}-13m_{2})k,$$

implying that k = 1.

Jul 22, 2019
#4
+1694
0

Great Solution, Guest!

tommarvoloriddle  Jul 22, 2019