<s>[INST] Proving that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$ 
Prove that $\gcd(5^{98} + 3, \; 5^{99} + 1) = 14$.

I know that for proving the $\gcd(a,b) = c$ you need to prove 


*

*$c|a$ and $c|b$

*$c$ is the greatest number that divides $a$ and $b$ 
Number 2 is what I'm struggling with. Does anybody have any ideas?
 [/INST] By euclid's algorithm $$\begin{align}gcd(5^{98}+3,5^{99}+1) &= gcd(5^{98}+3,5^{99}-1-5*(5^{98}-3))
\\ & =gcd(5^{98}+3,14)\end{align}$$Now we can see that 2 divides $5^{98}+3$. Also $5^3$ is -$1 (mod 7)$. Therefore $5^{98}=5^2*5^{96}=4(mod 7)$. So $5^{98}+3=0(mod 7)$. Hence 14 divides $5^{98}+3$. So $gcd(5^{98}+3,14)=14.$
</s>