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?

Guest Oct 27, 2020

#1**+1 **

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

A short computer code shows that no matter what the value of "n" is, the GCD of (13n + 8) and (5n +3) is ALWAYS = 1.

Sorry, I cannot explain it algebraically, but maybe Alan, Melody, EP....can!.

Guest Oct 27, 2020

#2**+1 **

Answer #1 seems to show that the gcd is always equal to 1.

It looks like this can be verified using the Euclidean algorithm.

\(\displaystyle 13n+8 =2(5n+3)+3n+2, \\ \;5n+3=(3n+2)+2n+1,\\ \;3n+2=(2n+1)+n+1, \\ \; 2n+1=(n+1)+n, \\ \;\;\; n+1 = 1.n+1.\)

So gcd is equal to 1 for any positive integer n.

Tiggsy Oct 28, 2020