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

Wilson's theorem may be apply able! – Sufaid Saleel Feb 06 '18 at 15:54 — Sufaid Saleel, Feb 06 '18 at 15:54
no number nearby is a prime – Dragon Surfer Feb 06 '18 at 16:08 — Dragon Surfer, Feb 06 '18 at 16:08
yeah,I did no notice it....sorry – Sufaid Saleel Feb 06 '18 at 16:16 — Sufaid Saleel, Feb 06 '18 at 16:16

score 6 · Answer 1 · answered Feb 06 '18 at 15:54

6

Since

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

Euclid's algorithm yields

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

answered Feb 06 '18 at 15:54

ajotatxe

65,084

score 4 · Answer 2 · answered Feb 06 '18 at 15:58

4

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

answered Feb 06 '18 at 15:58

B. Goddard

1

can you explain the step before gcd(-2015,1) I dont get it – Dragon Surfer Feb 06 '18 at 16:05
I'm letting $k=2014!$. Subtract $k2015=2015!$ from the right number. – B. Goddard Feb 06 '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 – Dragon Surfer Feb 06 '18 at 16:12

score 2 · Answer 3 · answered Feb 06 '18 at 15:50

2

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$

answered Feb 06 '18 at 15:50

lab bhattacharjee

274,582

Macavity · Answer 4 · 2018-02-06T16:00:27.113

1

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

edited Feb 06 '18 at 16:00

answered Feb 06 '18 at 15:54

Macavity

46,381

score 0 · Answer 5 · answered Feb 06 '18 at 15:52

0

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

answered Feb 06 '18 at 15:52

Arthur

199,419

score 0 · Answer 6 · answered Feb 06 '18 at 15:55

0

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

answered Feb 06 '18 at 15:55

robjohn

345,667

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

6 Answers6