Calculate $\gcd(2a+4b, 2a +8b)$, if $a\equiv b \pmod{\! 5},\ 6a+11b = 5$ Given:

*

*$a$ is even


*$6a+11b=5$


*$a-b=0\pmod 5$
Q: Calculate $\gcd(2a+4b,2a+8b)$

My try:
We know there is some $i$ such that $a=2i$, plus from 3 we know there is some $j$ such that: $a-b=5j$ which means $b=a-5j=2i-5j$. From 2, we get: $34i-55j=5$
So, $$\gcd(2a+4b,2a+8b)=\gcd(12i-20j,20i-40j).$$
I'm stuck here, how to continue?
 A: Use the property that $gcd(m,n) = gcd(m \mod n , n)$.
$$ (2a + 8b) \mod (2a+4b) = 4b \mod (2a+4b)$$
So, we have:
$$ gcd(2a+ 4b, 2a+8b) = gcd(2a+4b,4b)$$
Repeating the process, we have $$ gcd(2a+4b,4b) = gcd(2a,4b)= 4gcd( \frac{a}{2},b)$$
Can you finish now?
A: This helps with the last step after @Buraian's answer.
Now $\gcd(a,b) \in \{1,5\}$ because there is an integral linear combination of $a$ and $b$ that sums to $5$; in particular, $6a+11b=5$.
Meanwhile, as $a$ is even, it follows that $\frac{a}{2}$ is an integer, and as $\gcd(2,5)=1$, if $5|a$ then $5|\frac{a}{2}$. [In fact, let $k$ be any integer satisfying both $\gcd(k,5)=1$ and $k|a$, such as $k=2$. Then as $\gcd(a,b) \in \{1,5\}$, it follows that $\gcd\left(\frac{a}{k},b\right) = \gcd(a,b)$.] So from this it follows that $\gcd\left(\frac{a}{2},b\right)=\gcd(a,b)$.
So let us now calculate $\gcd(a,b)=\gcd\left(\frac{a}{2},b\right)$. Then from the first answer by @Buraian, $4\times \gcd(a,b) = \gcd(2a+4b,2a+8b)$.
Now, we claim that both $a$ and $b$ divide $5$. [Indeed, let $a \pmod 5 = r$. Then $b \pmod 5 =r$ as well, by the condition that $5|(a-b)$. However, on the one hand, (a) $6a+11b \pmod 5$ is $a \pmod 5 + b\pmod 5$ which is $2r$. As, on the other hand, (b) $6a+11b = 5 \equiv_5 0$ by hypothesis, it follows from putting (a) and (b) together that $2r \equiv_5 0$, so $r$ must be $0$, and thus indeed, both $a$ and $b$ divide $5$.] So $\gcd(a,b)$ must be a multiple of $5$. However, as noted already, $\gcd(a,b)$ is either $1$ or $5$, and so $\gcd(a,b)$ must indeed be exactly $5$.
As noted above, $\gcd(2a+4b,2a+8b)=4\gcd(a,b)$, so $\gcd(2a+4b,2a+8b)$ must be $4 \times 5 = 20$.
A: Taking (2) and (3) mod 5 shows that $a+b=0$ and $a-b=0$ over ${\mathbb Z}/5{\mathbb Z}$. Clearly both $a$ and $b$ are multiple of $5$. Hence by (1), one may write $a=10a'$ and $b=5b'$. Using (2), one has $$6(10a')+11(5b')=5$$ $$\Leftrightarrow 12a'+11b'=1,$$ which implies that $\gcd(a',b')=1.$ Now since $a$ is even,$$\gcd(2a+4b,2a+8b)=4\gcd\left(\frac a 2+b,\frac a 2+2b\right)$$ $$=4\gcd(5a'+5b',5a'+10b')=20\gcd(a'+b',a'+2b')$$
$$=20\gcd(a'+b',b')=20\gcd(a',b')=20,$$ where one uses $\gcd(a,b)=\gcd(a-b,b),$ etc.
A: Below are a couple proofs that work generally for problems of this type. They highlight the key role played by the coprimality of the determinant $\color{#c00}{\Delta}$ of gcd linear transformations.

A quick, easy way via gcd laws: by $\,a\,$ even we can renotate $\,a\to 2a,\,$ so by $\,\rm\color{#c00}T \!=\,$this Theorem
$\qquad d := (4a\!+\!4b,4a\!+\!8b) = 4(a\!+\!b,a\!+\!2b)\overset{\bf\color{#c00}T}= 4\color{#0a0}{(a,b)}= \bbox[5px,border:1px solid #c00]{4\cdot\color{#0a0}5}\ $ by $\,\color{#c00}{\Delta = 1}\,$ in $\rm\color{#c00}T,\,$ and by
$\qquad (2)\ \&\ (3)\Rightarrow\! \begin{align} 12a\!+\!11b &= 5\\ 2a\ -\,\ b &= 5c\end{align}\, $ therefore $\,\color{#0a0}{(a,b)} \overset{\bf\color{#c00}T}= (5,5c)\!=\!\color{#0a0}5,\,$ by $\ \color{#c00}{\Delta = -34}$ coprime to $\color{#0a0}5$
We used the gcd distributive law to factor $\,4\,$ from the gcd in the first displayed equation above.

Alternatively we can avoid $\:\!\rm\color{#c00}T\,$ by using $(a\!+\!b,a\!+\!2b) = (a\!+\!b,b) = \color{#0a0}{(a,b)}\,$ by Euclid, and then finish using the following $\rm\color{#90f}{Bezout}$-based characterization of certain $\rm\color{#0a0}{gcds}$.
Thm $ $ $\,\ \color{#90f}{j\,a+k\,b\:\! =\:\! c}\ \:\!$ & $\:\!\ (c,\color{#c00}{j\!+\!k})\!=\!1\,\Rightarrow\,$ below are equivalent:
$(1)\qquad\! \color{#0af}{a\!\equiv\! b \pmod{\!c}}$
$(2)\qquad\! c\mid a,b$
$(3)\qquad\!\! \color{#0a0}{(a\,,b)=c}$
Proof
$(1\Rightarrow 2)\,\ \bmod c\!:\ 0\!\equiv\!\color{#90f}{c\!=\!ja\!+\!kb} \!\overset{\color{#0af}{a\,\equiv\,b_{\phantom |}}}\equiv\! (j\!+\!k)b$ $\smash{\overset{\times\ (\color{#c00}{j+k})^{-1}\!\!}\Longrightarrow}$ $b\!\equiv\! 0,\,$ so $\, a\!\equiv\! b\!\equiv\! 0.\,$
$(2\Rightarrow 3)\,\ $ a $\rm\color{#90f}{linear}$ common divisor $\,\color{#90f}{c}\,$ is greatest: $\,d\mid \color{#90f}{a,b}\Rightarrow d\mid \color{#90f}{c\!=\!ja\!+\!kb}$
$(3\Rightarrow 1)\,\ \ \color{#0a0}{c\mid a,b} \,\Rightarrow\, \color{#0af}{\bmod c\!:\,\ a\equiv 0\equiv b}$
Remark $ $ Note Thm is a special case of Theorem $\rm\color{#c00}{T},\,$ applied to the linear system ${\begin{align}\color{#0af}{a \:\!-\:\! b\:\! }&= \color{#0af}c\:\!d\\[-.1em] 
\color{#90f}{ja\!+\!kb}&\color{#90f}=c\end{align}}\,$ with determinant  $\, \color{#c00}{\Delta =j\!+\!k}\ $ (similar to the first proof).
