<s>[INST] Show that $\gcd(7^{79}+5,7^{78}+3) = 4$ How can I prove that $\gcd(7^{79}+5,7^{78}+3) = 4$ ? This was a question on a past exam, so the naive euclidean algorithm doesn't seem to suffice.
I'm not really sure where to start with this.
Note: This is exam prep, not homework.
 [/INST] Since $\gcd(a,b)=\gcd(a-b,b)$, $$\begin{align}
\gcd(7^{79}+5,7^{78}+3)
&=\gcd(7\cdot 7^{78}+5-7^{78}-3,7^{78}+3)
\\
&=\gcd(6\cdot 7^{78}+2,7^{78}+3)
\\
&=\gcd(6\cdot 7^{78}+2-7^{78}-3,7^{78}+3)
\\
&=\gcd(5\cdot 7^{78}-1,7^{78}+3)
\\
&\vdots
\\
&=\gcd(7^{78}-13,7^{78}+3)
\\
&=\gcd(7^{78}-13,7^{78}+3-7^{78}+13)
\\
&=\gcd(7^{78}-13,16)
\\
\end{align}$$
From there, I'd determine the remainder when $7^{78}$ is divided by 16 and use that to see how $7^{78}-13$ compares to 16.
</s>