Without a calculator, find gcd(20!+95, 19!+5).

Question

I think it is $5$ because the gcf of just $20!$ and $19!$ is $19!$, and with the addition it cancels the other factors.

Answer 1

An Euclidean division yields

$$20!+95=20(19!+5)-5$$

So the gcd is $5$.

Answer 2

Let $d=\gcd(20!+95,19!+5)$. Then d divides $20(19!+5)=20!+100$. Thus $d$ also divides $(20!+100)-(20!+95)=5$. Therefore $d=5$.

Answer 3

Put $\ n\,=\,19!\ $ in $\ \underbrace{(\color{#0a0}{n\!+\!5},\,20n\!+\!95) = (20(\color{#c00}{-5})\!+\!95,n\!+\!5)}\!=(-5,n\!+\!5)=(5,n)$ ${\rm mod}\,\ \color{#0a0}{n\!+\!5}\!:\ \color{#c00}{n\equiv -5}\,\Rightarrow\,20\color{#c00}n\!+\!95\,\equiv\, 20(\color{#c00}{-5})+95\ $ by the Euclidean algorithm

Answer 4

$\gcd(20! + 95, 19! + 5)=$

$\gcd((20! +95)-20(19! + 5), 19! + 5)=$

$\gcd(95 - 100, 19!+5)=$

$\gcd(5, 19! + 5) = $

$5\gcd(1, \frac {19!}5 + 1)=$

$5*1 =5$