We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
69
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+22892 
+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+1034 
+5

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+1034 
0

Great Solution, Guest!

tommarvoloriddle  Jul 22, 2019

17 Online Users

avatar