+0  
 
0
47
2
avatar

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?

 Oct 27, 2020
 #1
avatar
+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!.

 Oct 27, 2020
 #2
avatar+149 
+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.

 Oct 28, 2020

15 Online Users