As $n$ ranges over the positive integers, what is the maximum possible value for the greatest common divisor of $11n+3$ and $6n+1$?
I want to find the greatest common divisor of two expressions that depend on $n$. One way to do that is to use the Euclidean algorithm, which repeatedly applies the division algorithm to find the remainder of dividing one expression by the other, until I get a constant remainder. Let me start by dividing $11n+3$ by $6n+1$ and see what the remainder is. Using long division, I get $11n+3 = (6n+1)(1) + (5n+2)$. So the remainder is $5n+2$. Now I repeat the process with $6n+1$ and $5n+2$. I get $6n+1 = (5n+2)(1) + (n-1)$. So the new remainder is $n-1$. One more time, with $5n+2$ and $n-1$. I get $5n+2 = (n-1)(5) + (7)$. So the final remainder is $7$. This means that the greatest common divisor of $11n+3$ and $6n+1$ is the same as the greatest common divisor of $7$ and any multiple of $7$. But the greatest common divisor of $7$ and any multiple of $7$ is just $7$. So the maximum possible value for the greatest common divisor of $11n+3$ and $6n+1$ is $7$. This happens when $n-1$ is a multiple of $7$, or equivalently, when $n$ is one more than a multiple of $7$. 