+0  
 
0
187
4
avatar

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
 #1
avatar+23812 
+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}\)

 

laugh

 Jul 22, 2019
 #2
avatar+1692 
+3

Great Solution, Heureka!

tommarvoloriddle  Jul 22, 2019
 #3
avatar
+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
avatar+1692 
0

Great Solution, Guest!

tommarvoloriddle  Jul 22, 2019

9 Online Users

avatar
avatar
avatar