Hello everyone.
In this video, I'd like to talk about
a couple of problems involving the greatest common divisor.
So for our first example, I'd like to talk about this problem:
show that the gcd of n factorial plus 1
and n plus 1 factorial plus 1 is 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 factorial over here,
and then n plus 1 factorial, so this is n plus 1 times n factorial 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,
but it's a type of…yeah.
I mean it's your best bet. So let's try to do that here.
So using GCDWR, we see that…
So what are we going to have? Let's put the big term
on the left.
So let's see what we have here. So n plus 1 factorial, well
n factorial plus 1 that goes in there, into
n plus 1 factorial, that definitely goes in at least
n times. In fact, if we do n plus 1 here,
what do we have? Well we have n plus 1 times n factorial,
that’s n plus 1 factorial, and then we get the extra n plus 1 term.
So we have to account for that, so we're going to subtract n.
This is a true statement. Now notice here
that this isn't using the Division Algorithm, right? This is a negative remainder,
right? 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 - let's write this properly - we see that since this is true, then…
So the gcd
of a and b, which a is the left-hand side, and b is this
term n factorial plus 1, is the same as the gcd of
n factorial plus 1 and n.
Well okay, I'll write it as negative n just to be precise.
That's what GCD With Remainder tells us.
Now let's look at this, right?
Let d be a divisor of n, right?
Then what do we know about - so if we take a divisor of n,
then we know that d must divide n factorial.
So let's actually clarify this, instead of d being a divisor n, let d be a divisor of the whole thing.
That’ll make my life a little bit easier.
So let d be a divisor of the whole thing,
then what do we know?
Then d divides n factorial plus 1,
let's be a little more correct now, and…
and d divides negative n
hence d divides n.
This implies that d divides n factorial, right,
d divides n, then clearly d divides n factorial.
Since n is one of the factors of n factorial.
Now what have we showed? So we have d is a factor of n factorial plus 1,
d is a factor of n factorial,
or divisor, so thus
by
Divisibility of Integer Combinations,
d divides n factorial plus 1
minus n factorial, and that's equal to 1.
And hence d is equal to 1.
Well d is equal to plus minus 1.
So in fact let me word this a little bit differently. Instead of saying d is a divisor of here,
let me fix this up and tidy this up, make it look real nice,
and make d equal [to the gcd] and then I don't have to worry about the
plus minus 1 because d is going to be positive.
So there we go. Let d equal the gcd of n factorial plus 1 and minus n,
then d divides n factorial plus 1, and d divides minus n,
so this implies that d divides n factorial.
Thus, Divisibility of Integer Combination says -
or gives us…
gives us that d divides n factorial plus 1 minus n factorial, and that equals 1.
d is a positive divisor of 1 that must mean that d is 1,
and this completes the proof.
Since we've shown that d is equal to this gcd and that gcd was equal to the expression…
and d equals the gcd in question. So maybe I'll put the concluding sentence
And that's it. Okay?
So one more time through the question.
So my claim was that these two terms
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 of the
leftmost term and this
right-hand term, this is going to be my a and my b in the theorem.
So that gcd must be equal to the gcd of n factorial plus 1 and negative n, that's my remainder.
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 factorial.
Let me put this in brackets,
just that you don't have to deal with the exclamation point and the period beside each other.
Thus by Divisibility of Integer Combinations…
thus - maybe I'll remove the word “by” so that it's a little clearer.
Thus Divisibility of Integer Combinations gives us that d divides
n factorial plus 1 minus n factorial, that's just 1.
Hence d equals 1, and thus the 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.