$\gcd (2016!+1, 2015!+1)$

Question

Can someone tell how to do this? I know the answer when there is no additional 1 in it. But with +1, I have no clue. Can someone give insights? I tried using $\gcd(a,b) = \gcd(a, b-a)$ but could not get anywhere. Thanks in advance

Answer 1

So, if integer $d(>0)$ divides both,

$d$ must divide $2016!-2015!=2015!(2016-1)$

Now $(d,2015\cdot2015!)$

divides $(2015!+1,2015\cdot2015!)=1$

Answer 2

Use the same rule $2016$ times to get $$ \gcd(a, b) = \gcd(a, b-2016a) $$

Answer 3

Since

$$2016!+1=2016(2015!+1)-2015,$$

Euclid's algorithm yields

$$\gcd(2016!+1,2015!+1)=\gcd(2015!+1,2015)=1$$

Answer 4

$$\gcd(2016!+1, 2015!+1) = \gcd(2016!+1 - 2016(2015!+1), 2015!+1) \\= \gcd(2015, 2015!+1) = 1$$

Answer 5

$$ (2015!+1)-2014!\,\overbrace{(2016\,(2015!+1)-(2016!+1))}^{2015}=1 $$ That is, $$ 2014!\,(\color{#C00}{2016!+1})-(2016\cdot2014!-1)\,(\color{#C00}{2015!+1})=1 $$ Therefore, $$ (2016!+1,2015!+1)=1 $$

Answer 6

You can do better with $\gcd(a,b) = \gcd(a+kb,b)$ for any integer $k.$

$$\gcd(2016!+1, 2015!+1) = \gcd(2016!+1 -2016(2015!+1), 2015!+1) $$

$$= \gcd(-2015, 2015!+1) =\gcd(-2015, 2015!+1 - 2014!(2015))$$

$$ = \gcd(-2015,1) =1.$$