+0  
 
0
266
4
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?

 Feb 23, 2022
 #1
avatar
+1

The maximum value of the GCD ==1. Because the two expressions are always "relatively prime" to each other, no matter what the value of n is. Therefore, their GCD will always be== 1.

 Feb 23, 2022
 #2
avatar+118587 
+1

I agree that that may well be the case BUT how do you show it.

Melody  Feb 25, 2022
 #3
avatar
+1

Suppose that 13n + 8 and 5n + 3 have a factor p in common.

Let 13n + 8 = sp and 5n + 3 = tp for some numbers s and t.

Eliminate n between the two equations, (5 times the first minus 13 times the second) and you arrive at 

1 = 5sp - 13tp = p(5s - 13t).

Since we are talking integers, it follows that p = 1.

 Feb 25, 2022
 #4
avatar+118587 
0

Ok thanks, that makes sense :)

Melody  Feb 25, 2022

2 Online Users

avatar
avatar