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

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

• Wilson's theorem may be apply able! Feb 6 '18 at 15:54
• no number nearby is a prime Feb 6 '18 at 16:08
• yeah,I did no notice it....sorry Feb 6 '18 at 16:16

Since

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

Euclid's algorithm yields

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

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.$$

• can you explain the step before gcd(-2015,1) I dont get it Feb 6 '18 at 16:05
• I'm letting $k=2014!$. Subtract $k2015=2015!$ from the right number. Feb 6 '18 at 16:09
• ohhhh ok I got it . Thank you so much. I was able to reduce it till gcd(-2015,2015!+1) . This has been an eye opener Feb 6 '18 at 16:12

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$

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

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

$$(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$$