# Examples Using The Division Algorithm (Useful)

(D4M) — Here is the video transcript for this video.

00:00
[Music] hi everyone welcome back in this episode you’ll learn why the
division algorithm is so useful now in the previous episode we
started touching upon that we talked about what the division algorithm is and
why it’s so useful um in this in this video though we’re
going to do more examples and really drive home and really understand
um the importance of the division algorithm at least by looking at some examples
so now before we get started with that though i wanted to
uh mention that this video or this episode is part of the series
divisibility in the integers step-by-step tutorials for number theory
and so in this uh episode we’re going to take a look at the division algorithm
and we’re going to try to understand better the proof by cases which i was

00:01
talking about in the at the end of the previous episode
and we’re also going to use some computer algebra to help us uh with some
today and so let’s get started so um first here we’re going to um
look and recall what the division algorithm is
now in the next episode we’re actually going to go through the proof of this
but before we do that i wanted to work out some more examples
so here’s what the division algorithm is so
again we can extend this to all integers um but in this series of videos here
we’re just going to look at positive integers here
um and so there exists unique integers and they’re called um um q and r
uh the quotient and the remainder um actually i want to change something

00:02
right here real quick um okay yeah so let’s change that to there exists
unique integers q and r such that a and b all right so very good and so um
yeah in the last video we talked um more or we talked a little bit about this
phrase right here of the form so if you’re curious what that phrase
right there means of the form bq plus r this is kind of a definition right here
although in the previous episode we kind of talked about in in much more detail
but it says there exists integers b q and r such that a equals b q plus r
so there’s just sort of a technical definition
um but we’re going to go through lots of examples and really drive home the
meaning of this right here and so let’s um i want to mention one
more thing though before we get started here with some examples is
the division algorithm in a certain sense measures the divisibility

00:03
right because if your a is actually zero then you know you have divisibility
but the closer your r is to be well in any case it’s kind of a measure of
divisibility all right any case this isn’t a very
there’s just some intuition there all right so the advantage of the
division algorithm is it allows us to prove statements
about the positive integers by considering only a finite number of cases
so this is different type of proof than say mathematical induction
but it’s very powerful as we’ll see in today’s examples
so for our first example we’re going to show that six divides the product of any
three consecutive positive integers and so this will be our first example here
now the way i’m going to do this example here is um i want to show six divides
and but i need three consecutive positive integers so to get

00:04
to get consecutive positive integers i can say something like m
n plus one and then m plus two and then m can be any
positive integer and that will give us three consecutives
so in other words we need to show that six divides m times m plus one
times m plus two and this is for any m for any positive integer m
we need to show this or said differently m times n plus one times m plus two
is equal to six k for some k for some positive integer k
and so you know we need to look at the various cases or here we can say 6n
for some n [Music] so we need to look at the various different cases of m here

00:05
now i’m going to show you this example right here three different ways
the first way is sort of a brute force intuitive way which you might first
discover this result on your own and then we’ll write it up as a nice proof
that you might try to communicate to somebody else
and then the last way is we’ll look how to do this on a computer and check
and see how it’s easier and then we’ll work out some other examples that are
more the more meteor alright so here’s how brute force way in
which you might kind of discover this right here so remember m here can be
any integer at all right here so if i take any integer if i divided by six
i know that one of only six possibilities must hold must hold so the first case
is that m looks like 6k so if m looks like six k

00:06
then we have six k plus one here and we have six k plus two here
and we’re asking can i make this look like six n and what will be the n
so it’ll be k times 6 k plus 1 times 6 k plus 2
so this will be the n right here and n n is a natural number
and this is a natural number right here a positive integer
and so yeah this case works right there’s a six sitting right there so it works
so case two so case two means six k plus one so again we’re trying to show that
any three consecutives well if i take any m it might look like six k plus one
but what will the three consecutives look like
so it’ll be look like six k plus one that’s for the m
and then six k plus one plus one which is six k plus two

00:07
and then six k plus three so can we factor a six out of all this six times
so that doesn’t have a six in it because it’s got plus one this has a two in it
and this has a three in it so actually yes we can factor out a six
between these two combined so what do we get left over we’ll get six k plus one
i’m not factoring anything from here here i’m factoring out a two so what do
we have left 3k plus 1 and here i’m factoring out a 3
so what am i going to have left 2k plus 1.
so as you can see we wrote this as 6 n and n is some natural number if you
calculate all that up no matter what k is it’s a natural number it’s positive
it’s going right there so um you know that’s it that’s it for case two

00:08
and so we can go through just by brute force and looking at all six cases so
let’s just write one more case down here case let’s say case five
so m looks like six k plus five i’ll let you fill in the
six k plus one six k plus two next would
be six k plus three then six k plus four so i’ll let you fill those in
now i’m going to go to the last case right because if you’re dividing any m
by six it’s going to have remainder zero 1 2 3 4 or 5 last case right here
so let’s build up our three consecutive integers if m looks like this so it’ll
be m times m plus one times m plus two as you can see this all has a six in it

00:09
because we can just factor it out this one right here so six
and then we’ll have six k plus five still and here we’ll have k plus 1
and here we’ll have 6 k plus 7 and the important thing to notice is
that all of this right here is an integer a positive integer at that and so
three consecutive integers when m looks like this is divisible by six
so once you do all five cases then you’ll know that any
three consecutive positive integers because we chose any m
so that means we’ll have any three consecutives
and it’ll always be divisible by six and so that’s how proof by cases would work
is you know we would show all the cases i confidence that you can fill in these
right here um but i’m actually going to fill those in
for you but i’m going to do it using computer algebra and so let me

00:10
show you how to do that next that’s sort of our next approach here [Music]
so let’s pull in some code right here so the first thing i want to do is to
[Music] set up this code for us right here let’s move out of the way and so
if we set this code up this is python and what i’m going to do is i’m going to
bring in some packages to make uh life very easy
so just type this up and then hit shift enter and
that will import some python packages and then i want to import this one
that will make it look uh nice and pretty for us when we look at the math
so i’m going to execute those cells now i’m going to do some
computation here with some symbols so i’m going to say n here is going to be

00:11
my variable here or my symbol here alright so for our first example right here
we’re going to look at what we just did here
so what i’m going to do is i’m going to expand out and then i’m going to
simplify and i’m looking at three consecutive integers
with 6k or 6n and then 6m plus 1 and then 6n plus 2. and if we
expand that out and then simplify it and as you can see right here it is
divisible by 6. so just you know doing that computation
really quick it’s really fast just notice here that this is divisible by 6.
so this case works right here and then for this case
six n plus one six n plus two six n plus three
we’ll execute that cell right there and then now we’ll have these
coefficients right here but you can check them all they’re all divisible by six

00:12
and in fact we could just actually do that over here at the end
just divide it by six and then you see it’s still an integer
right here so if i cube an integer multiply an integer by 36
square an integer multiplied by 36 add those up you see all this is integers
right here so we can work through all six cases here in fact the cases that um
i didn’t show where this case right here we can check all of these are divisible
by six so this whole thing is divisible by six
so in other words if you have three consecutive integers of the form
where you’re starting integers of the form six n plus two and you do three
consecutives it’ll be divisible by six and then we do six n plus three six n
plus four six n plus five if we check all the coefficients here

00:13
they’re all divisible by six and the other missing case here
is if we expand this out divided by six so i divided all by six already and we
still get here now you know you might ask what does it look like if you
don’t get an integer well for example if
i divide this by seven you see those are not integers there so in number theory
here we’re going to be restricted to talking about integers we’re talking
about integers this is an integer n is an integer all of this computation
computed out as an integer and then the last case that we did
so we get this part right here and all of this is divisible by six
we can check that out real quick dividing by six there we go
so those are all the cases for uh this problem right here uh working it out by

00:14
um working it out using some computer algebra there
so let’s go here now to look at our next example [Music]
so in our next example here we’re going to be looking at um proving that
oh i actually wanted to show you one more thing here sorry i almost forgot um
i want to show you one more way of working this out and
that was by writing up a nice proof rather than just by doing everything
um brute force by all these cases and so you know i’m going to say
six divides the product of any three positive integers
so i’m going to say that n be a natural number and i want to show that

00:15
three consecutives for any natural number so this will be all three
consecutives possible is of the form 6k so that’s we want to show so the
division algorithm yields that m is either even or odd
but not both right so the division algorithm if you divide by two you’re
either going to get remainder zero or remainder one now
when i look at this case right here this must be even
um in other words three when you multiply three consecutives it oh the
whole product must be even why is that well if this is even
then the whole thing is even or if this is odd then m plus one will
be even so either one of these two right here will be even so the whole product
right here must be even so now i’m going to look by divisible by three
so this number natural number right here is also divisible by three

00:16
because one of these three right here is divisible by three just like this right
here either one of these two is divisible by two one of them
one of these three is also must be divisible by three so one of these we
can factor out a two and one of these we can factor out a three
so when we consider the whole thing it must be divisible by six
and so that’s a little bit more of a cleaner way of writing out a proof
that looks nice and so we looked at the computer algebra um
doing that right there and so now let’s go on to so we looked
and so now let’s go on to the next one here
prove that the square of any integer is either of the form 3k or 3k plus one
so we can do this by hand or we can do this
uh with some computer algebra help but i don’t think we’ll need it so the square

00:17
any integer so you know we when we talk about any integer i’m going to say a and
a can be what um 3n or a could be 3n plus 1 or a could be three n plus two
so i can break this problem up into two into three cases
and say that no matter which case i’m in i either look like one of these two
right here and so that’s the strategy behind that
to show that something is true for all integers well i’m going to break up all
integers into three buckets just like you would do even or odd i break up any
integer into two buckets even rod i can break up any integer and into three
buckets and for each bucket i’ll show that it
has to be three k or three k plus one so for the first one right here
and remember we’re squaring so if i do a squared so a squared will be

00:18
three n squared which will be three n uh which will be nine n squared and
that looks like three k or three k plus one because i can write it out as three
and then this will be three n squared and so this will be three k
and this is our k right here and this is an integer so we’ll just say where
three n squared is a natural number actually here we’re just talking about
integers so i’ll just say integer so 3n squared is an integer now what
squared which we’re going to get nine n squared plus six n plus one

00:19
and now we can factor out a three from these two so we’ll say three
and then n squared plus two n plus one so this is our k now so where
where n squared where this part right here is an integer so we look like three
k plus one and this is our k right here so what about our last case now
so a squared is three n plus two squared which is nine n squared plus
six times two so 12 n plus four and that looks like
so we can factor out a three from these and factor i can factor out um i’ll
think of this 4 here as a 3 plus 1 so i’m going to factor 3 out of all this

00:20
i’m going to get 3 n squared plus 4 n plus
1 and then plus 1. you see how i broke that four up i broke it up into a three
times one plus one so now this is my k right here so this
looks like three k plus one and we have to you know say hey this is a
integer here this is an integer this is integer so if your a looks like
three and plus two is still the whole thing the square
looks like three k plus one and k is an integer so no matter
what the a is it always looks like either three k
or three k plus one or three k plus one so it’s always going to be one of these
two right here the square of any integer so i took any integer by breaking any

00:21
integer up into three cases so that’s pretty cool i like that
so for our next example we can look at the fourth power
now when we start looking at fourth powers here maybe we can get some help
over here so let’s look at some something over here
and let’s try to make this be a little bit not so big
all right so this just says prove that the fourth power of an integer is either
of the form 5k or 5k plus 1 and then let’s try to zoom in on this
part right here so we can get this a little bit more focused
so as you can see this will help us do some computations over here so
here we’re looking at the fourth power and it’s telling us five k or five k
plus one so we’re going to have five cases

00:22
any integer so i’m going to say a is any integer and it’s gonna look like five k
or five k plus one or five k plus two and we’re going to
have these different cases because a can be any integer we don’t
know what the remainder is so we’re gonna look at these five cases
all of them individually but for each one of these cases we have to go look at
a to the fourth which in this case will be five k to the fourth
and 5k to the fourth or over here i’m using an n so in fact
to stay consistent with what i did over here let’s switch these to ends real
quick and so that’s a two three and a four here
and so this will be five n to the fourth of course when you go compute that out

00:23
that’s easy that’s just 625 to the fourth and so you have to ask does this look
like 5k or 5k plus 1 and the answer is yes because there’s a 5
there’s a five in here we can write that out in fact we can
just go do that over here i can just hit shift enter and then if i
want to find out what it is if i divide it by five
it’s 125 right that’s obvious 125 n to the fourth and so here’s 5k that’s
our k right there and so this right here 125 into the fourth
that’s an integer that’s our k so this case is done right here
and we can just go through each one of these cases so let’s look at the next k
our next case so five n plus one so now i’m looking at five n plus one to the
fourth when i look at five times right so the next case will be

00:24
a to the fourth is five n plus one to the fourth right and we multiply that out
and then simplify it we get this right here and we can check
that each one of these is divisible by five
this is the y five is the y five just by five this is what so it looks like the
case for this one right here we’re going to look like 5k plus 1 because we’re
going to have a 1 left over and we can check that right here
by dividing by 5 and then it actually simplifies
and it finds the k for us right there of course this is one over five that means
that means the remainder is one so we’re going to be in that case right here the
five k plus one right there all right so that’s good
so now what about uh the next case four five k plus uh five n plus two
so you know now we have a a five n plus two raised to the fourth
and we can just expand it out and then simplify it

00:25
let’s do that so all these are divisible by five
this one’s not this one looks like five k plus one
right because we can divide the five out and subtract a five subtract a five
subtract a five we end up with a remainder of one so
this case now works also because this is all divisible by this looks like the
four five k plus one now what about the next case
five n plus three so now we have five n plus three to the fourth
we expand and simplify that we get this and then we check if it’s divisible by
five and we’re going to get a fraction over here so all this is divisible so
but we’re gonna get remainder one right we can subtract five subtract five
and we’re finished with all that we’re going to get remainder one
so it looks like this case looks like the form five k plus one

00:26
and then the last case to check would be the five n plus four raised to the
fourth and so we execute that cell and we check is all this divisible by
five or not as you can see all these are divisible by five
and then the last one right here is going to have remainder one left over now
what i did was i said you know what that’s kind of a lot of work to do
so i actually just in two lines here we can actually do all the stuff up here so
because we’re looking here at um we’re looking at the range here is five
because we’re going zero zero one two three four will be our last case
and we’re gonna check the 5 in and we’re going to and so the i is ranging

00:27
i starts at 0 1 2 3 and then the last case is 4
so we can just execute this right here and that gives us all these up here that
we just found it gives it to us all in one step and so we could check here the
remainder zero so this is of the four five k
this is of the form five k plus one this is of the form five k plus one
this is of the form five k plus one in fact all of them are of the form five k
plus one except for this the first case right here
so no matter what integer you choose i can divide it by five and see which
case i’m in and then check my case over here alright so um
that’s going to be it for this video and i hope you saw some really good
examples there that you liked of proof by cases
and if you’d like to see more examples worked out let me know in the comments

00:28
below and i’ll make a video for you until then i’ll see you in the next video
if you like this video please press this
button and subscribe to my channel now i want to turn it over to you math can be
difficult because it requires time and energy to become skills i want you to
tell everyone what you do to succeed in your studies either way let us know what