Examples of $\gcd$ Part $1$

Hello everyone. In this video, I'd like to talk about a couple of problems involving the greatest common divisor.

Question: Show that $\gcd(n!+1,(n+1)!+1)=1$

So we're showing that these two numbers are co- prime. Now when you see a $\gcd$ problem, again we've been instructing our students to go through the theorems that they know in their mind and seeing if any one applies to this situation.

I'll go one step further here and notice here how there's the $n!$ on the left, and then $(n+1)!$ on the right, so this is $n+1(n!) on the right. Now when you have the two terms that kind of depend on each other in some weird way, using the greatest common divisor theorem called GCDWR, Greatest Common Divisor With Remainder, that's sort of your best bet.

So let's try to do that here. So using GCDWR, we see that

$$(n+1)!+1=(n+1)(n!+1)-n$$

This is a true statement. Now notice here that this isn't using the Division Algorithm, right? This is a negative remainder. So GCDWR, we think about it in terms of the Division Algorithm, but it can be used outside of that scope.

So with this, we see that

$$\gcd(n!+1,(n+1)!+1)=\gcd(n!+1,-n)$$

That's what GCD With Remainder tells us. Now let's look at this, right? Let $d=\gcd(n!+1,-n)$ n, right? Then $d\mid n!+1$ and $d\mid -n$ which implies $d\mid n$.

This implies that $d\mid n!$, right, $d\mid n$, then clearly $d\mid n!$, since $n$ is one of the factors of $n!$.

Now what have we showed? So we have $d$ is a factor of $n!+1$, $d$ is a factor of $n!$, our divisor, so thus by Divisibility of Integer Combinations, $d\mid n!+1-n!=1$. And hence $d=1$. $d$ is a positive divisor of $1$ that must mean that $d=1$.

Thus, $\gcd(n!+1,(n+1)!+1)=d=1.\quad\blacksquare$

Recap

This completes the proof. So one more time through the question. So my claim was that $n!+1$ and $(n+1)!+1$ look similar to each other. They have elements in common so GCDWR seems like a natural choice to use, so we use it.

Once we use it, it tells us the $\gcd(n!+1,(n+1)!+1)=\gcd(n!+1,-n)$. So letting $d$ equal this greatest common divisor term and $d$ is a factor of both terms, and hence must be a factor of $n!$.

Thus Divisibility of Integer Combinations gives us that $d\mid n!+1-n!=1$. Hence $d=1$, and thus $\gcd$ must be equal to $1$. Okay, so that’s great. Thank you very much for your time and hopefully this helps you out on your assignments.