2
$\begingroup$

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

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

Since

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

Euclid's algorithm yields

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

$\endgroup$
4
$\begingroup$

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

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

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.