Are These Huge Numbers Relatively Prime?

Number Theory Level 1

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

Notation :

$\gcd(A,B)$ denotes the greatest common divisor of the two numbers $A$ and $B$ .

The answer is 1.

4 solutions

Abhishek Sinha
Dec 8, 2015

We can apply the Euclidean Algorithm .

Let $g$ be a common divisor of $2015!+1$ and $2016!+1$ . Hence $g$ must divide $2016(2015!+1)-(2016!+1)=2015$ Hence $g \leq 2015$ . But $2015!+1$ does not have a divisor (other than $1$ ) which is less than $2015$ . This implies that the only possible value of $g$ and the GCD is $1$ .

Moderator note:

Good application of the Eucliedean algorithm.

Thanks for both solutions. :)

Priyanshu Mishra - 5 years, 6 months ago

Do you say that 2015!+1 doesn't have divisors leas than 2015 because gcd(2015!, 2015!+1)=1?

jose esteban beleño barrozo - 2 years, 9 months ago

How were you able to conclude that $g$ would be less than or equal to $2015$ ?

Krish Shah - 1 year, 2 months ago

I don't really see where Euclidean algorithm was applied in the solution above.

Sergei Filatyev - 11 months, 2 weeks ago

Aareyan Manzoor
Dec 8, 2015

extended euclidean algorithm $2016!+1=2016(2015!+1)-2015$ $2016=-1(-2015)+\boxed{1}$ $-1=-1(1)+0$

Moderator note:

Good explanation. Instead of resorting to Extended Euclidean Algorithm, it is often easier to directly write it up as a sequence of $\gcd(A, B) = \gcd(A-nB, B)$ statements.

Prasit Sarapee
Jan 9, 2016

Let a=2015! b=2016!
gcd(a,ab)=a
gcd(a+1,ab+1)=1

Lisa Liu
Jan 31, 2021

Let $a=2015!$

Then we have

$\text{gcd}(2015!+1,2016!+1)=\text{gcd}(a+1, 2016a +1)$

Applying the Euclidean Algorithm, we see that:

$\text{gcd}(2016(a+1)-2015, 2016a +1) \Rightarrow \text{gcd}(2015,2016a+1)$

Therefore, we see that the greatest common divisor is $\boxed{1}$ .

Are These Huge Numbers Relatively Prime?

The answer is 1.

4 solutions

Moderator note:

Moderator note:

0 pending reports