+0  
 
0
40
1
avatar

As n ranges over the positive integers, what is the maximum possible value for the greatest common divisor of 11n + 3 and 2n + 1?

 Dec 29, 2021
 #1
avatar+20 
+1

5.

 

say X divides both 11n+3 and 2n+1, and is the greatest common divisor.

 

then we have the following system of equations

 

11n+3=ax

2n+1=bx 

 

where a, b, and x are all positive integers.  

 

then, multiplying 2n+1=bx by 3 and subtracting it from 11n+3=ax (elimination for a system of equations), 

 

we have ax-3bx=5n

 

x(a-3b)=5n

 

n=x(a-3b)/5

 

using this value for n, we substitute it into the first equation 11n+3=ax

 

\(\frac{11x(a-3b)}{5}+3=ax \)

 

we simbplify this equation to get \(x(2a-11b)=5\)

 

However, because all x, a, and b are positive integers, we have either x=1, or x=5.  The greatest value of x is 5.  

 

we can note that when n=2, both 11n+3 and 2n+1 are divisible by 5 (25 and 5 respectively).  

 Dec 29, 2021

14 Online Users

avatar
avatar