# The biggest $\gcd(11n+4, 7n+2)$?

I am having problems solving this problem with greatest common divisors: What is the greatest common divisor of $11n+4$ and $7n +2$?

I tried Euclidean algorithm, and I tried to deduce the answer and I tried to incorporate

$$\gcd(a,b)\cdot\mathrm{lcm}(a,b)=|ab|$$

Let use that

$$\gcd(a,b)=\gcd(a,a-b)$$

that is

$$\gcd(11n+4,7n+2)=\gcd(4n+2,7n+2)=\gcd(4n+2,3n)=\gcd(n+2,3n)=\gcd(n+2,2n-2)=\gcd(n+2,n-4)=\gcd(6,n-4)$$

then $\gcd_{MAX}=6$.

• And the maximum is assumed for $n=4$, for example. – Servaes Apr 17 '18 at 20:47
• @Servaes Yes indeed we obtain $\gcd(48,30)=6$ – gimusi Apr 17 '18 at 20:49

If $d\mid 11n+4$ and $d\mid 7n +2$ then $$d\mid 7(11n+4)-11(7n+2)= 6$$

so $d\in \{1,2,3,6\}$. Now, can $d=6$. In this case $6\mid (7n+2)-6n=n+2$ so if $n=6k-2$ then $d=6$ so $\gcd =6$.

\begin{align} (11n+4) &= 1(7n+2) + (4n+2) \\ (7n+2) &= 2(4n+2) + (-n-2) \\ (4n+2) &= -4(-n-2) - 6 \end{align}

This suggests that the biggest gcd must be a divisor of $$6$$.

Such a value should occur when $$n=-2$$.

\begin{align} 11(-2)+4 &= -18 \\ 7(-2)+2 &= -12 \\ \gcd(-18, -12) &= 6 \end{align}