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?
+26367 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}\)
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.
