+0

Number Theory

0
111
1

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
+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