# The Division Algorithm (Step-By-Step Tutorial)

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

00:00
[Music] hi everyone welcome back in this episode you’re going to learn
what the division algorithm is and you’re going to see lots of examples
so let’s get started but actually before we get started i wanted to go through
and mention that this episode is part of the series the visibility in the
integers step by step-by-step tutorials for number theory
so what is in this episode today so we’re going to have a quick
divisibility review and we’re going to talk about the division algorithm
and then we’re going to see actually we’ll see some lots of examples
we’ll see a couple of examples so let’s get started here and to do that
let’s go here and do a quick divisibility rule review now

00:01
again this is video is part of a series in the first episode of the series we
and we also in the next episode went through and proved these lemmas here so
a divides a and a if a divides a and b divides a
then a equals b if they’re both positive and
if a divides b and b divides c then a divide c and in the last lemma
in the previous episode we proved that if c divides a and c divides b
then c divides any linear combination of a and b yes so we went through those
proofs last video so um again if you want to see those
proofs and how to write those proofs then i recommend checking out that video
there now today’s video is going to be all about the division algorithm

00:02
so what is the division algorithm so we’re going to start off by
saying that a and b are non-zero positive integers
now that’s not a big huge restriction because
we can extend this division algorithm to all integers but and
as an introduction here we’re just going to say positive integers so we’re
thinking that a and b are positive um and so the conclusion is there exists
unique integers q and r so q is going to be called the quotient
and r is going to be called the remainder and they’re unique and they exist so
there’s two two words there is existence and uniqueness
and so of course you have to have both conditions in order to get
to get this right here and so we’re going to see
some examples today and then in an upcoming episode we’ll see the proof but
first i want to go through two videos two episodes where uh in this one we’re

00:03
going to see why it’s important to see what it is
and then in the next episode we’re going to look at some more serious examples
and then in the third episode after this one here or
the second one after this one we’re going to go ahead and write a
proof up for this right here after we get a good understanding of what it is
so in this video i want to uh work out this division algorithm by hand
and i want to work it out by computer also
and i also want to understand what this phrase right here means of the form so
if you’re taking a number theory course or if you’re reading number three books
you see this phrase here a lot of the form and so i want to
make the connection between that verbage and
the division algorithm and make sure that whenever we use this phrase right
here that we understand what it means so let’s go through these three three

00:04
things here quickly so let’s look first um by hand so let’s say our a is 28
and let’s say our b is seven right so they’re non-zero positive
integers so we can write out um and find the q and the r and so the
way that we would typically see that would be something like
how about let’s go with say 78 and 7 and so let’s say here
78 can go here one time um in fact let’s say maybe 79 so one time remainder nine
seven can go one more time now we have remainder two
and so the way we can write that out is by writing 79 that’s the a is equal to

00:05
7 times 79 so that’s 7 b’s the 7 7 times 79
sorry 7 times the quotient which is 11 and then plus the remainder so 11
plus the remainder which is two so there’s how we
you know you might write it out like this you might write it out like this
whichever way but the quotient is um you know positive it’s unique here’s the
remainder and the remainder 2 is less than the 7.
now say greedy here why is it greedy well when we’re doing this project here uh
sorry when we’re doing this computation right here we’re trying to be as greedy
as possible so for example if we start over here
and we say how many times can seven go into
seven here um we can’t use two that’s too many and we don’t want to use zero

00:06
because that will be zero and then we subtract we
we got 79 that didn’t go anywhere that just didn’t do anything for us
so we choose the number right here that is the most that we can without going
over so 70 and then you know nine now we choose the most again which in
what we’re trying to do is we’re trying to choose the most here and the least
here you could kind of think of it out as a min max thing all right so
let’s also look at this um by computer so let’s do that by computer using
let’s use python real quick so let’s look at a quick python notebook
or some quick python code and i have a link to the description in the
bottom if are in the description if you want to see how to get set up

00:07
and so that you can follow along so what i’m going to do is i’m going to
define a function which i just happen to be calling a division algorithm
and i’m going to take in an a and a b just like we do over here
and i’m going to say q is set it by default to be 0 and by default i’m going
to set r to be equal to the a and i’m going to be doing while r is too big
right because you need r to be less than so while r is too big i’m going to
subtract a b from it i’m going to keep subtracting a b and subtracting a b and
subtracting a b until we get less than b when we get less than b then we’re done
and each time we subtract a b i’m going to i’m going to start at 0 and i want to
count how many times i’ve subtracted the b
so that’s what the quotient is it’s how many times we’ve subtracted the b
so for example we had a minute ago a minute ago we had 79 and we were

00:08
looking at seven so i’m going to attract i’m going to subtract a seven another
seven another seven another seven in the end i’m gonna subtract seven
eleven times and then i’m going to look and see
what’s left over well r will be two because we’ve subtracted
seven from it and we’ve gone through here 11 times and each time we’ve gone
through the loop here we’ve incremented q
so we’ve gone through the loop 11 times so q will end up being 11
and then what will be left over will be the two and we’ll stop because
two is less than the b and so we’re not going to keep doing this we’re only
going to do this while r is greater than or equal to b
so here’s a quick illustration of how you would code or at least one way you
would code the division algorithm so we can execute that cell by hitting
shift enter and then we can now just execute at will so 78 and 4
or for the one we did here what do we do 79 and seven

00:09
so you see we get the 11 and two or if we want to do another example
suppose we do 78 and 4 and so then we would be doing the
quotient would be 19 and we would be having remainder 2.
so you know we could write that out as an equation
this is the a right that’s the a so we would say 78 equals the quotient’s 19
so the b is 4 so 4 times 19 and then plus the remainder this gives
us the remainder so we’re going to return the remainder of two
so then we have the division algorithm here and q and r
are unique that’s the unique quotient and the unique remainder that satisfies
these two things here so this is how we can do this by computer or you know it’s
just one way one implementation and it will write a proof up in an

00:10
upcoming episode so there’s bike by hand and by computer
and so now let’s look at what’s next [Music]
so what does it mean to say of the form so of the form means
um we’re going to be using the division algorithm to break things up into cases
let’s get rid of that and look at what it means to say of the form so if we a b
and an a right so we can say a is of the form b q plus r and r is the remainder
so we can say of the form three k plus one
right so of the form three k plus one so we can ask the question is 17

00:11
of the form 3k plus 1. so that’s a question yes or no
so we’re going to divide 17 by 3 and see if the remainder is 1.
so that’s the way you can translate this so yes or no but this question is is
the remainder when 17 is divided by three equal to one
so that’s the same question so you know this is a lot shorter of the
form is a lot shorter than all this words here but it means the same thing
is the remainder when 17 is divided by three equal to one
and so you can see this has got the remainder it’s got divis divided by
so this is you know longer and this is a lot shorter but we

00:12
can go answer that question we can say three seventeen
we can see here and say five fifteen remainder two
and so the the answer this is no right the answer is no
now what makes the division algorithm so powerful is that you can break up
man any number and ask the same question i mean for example 17
i asked the question for three k plus one but
what are all the possibilities three k three k plus one or three k plus two
so seventeen has to look look like of the form three
k or three k plus one or three k plus two because that’s the only
possibilities because when you’re dividing by three what are the only
possible possible remainders would be zero one or two
so here this is the case when the remainder is zero when the remainder is

00:13
one when the remainder is two so which is true seventeen is of the form three k
seventeen is of the form three k plus one
or seventeen is of the form three k plus two and of course we already answered
that because when we divided it out we said the remainder was two so seventeen
is three times 5 17 is 3 times 5 plus the remainder
so 17 is of the form 3k plus 2 and the k is 5.
now when we’re asking it is of the form we’re not really interested in the
quotient we’re just interested in the remainder and we’re interested in yes or
no so the question would be is 17 of the form is 17 of the form three k plus two

00:14
and the answer would be yes okay so that kind of explains what of the form means
but we’re going to dive into a lot more in the upcoming
examples and so let’s see that so our first example is here is show 3 divides
a times a squared plus 2 for any natural number a now
a can be any natural number when we’re gonna show three has to divide it
so we’re interested in divisibility by three
so when you’re dividing by three there’s only three possibilities so you already
kind of have this intuition for two if you divide by two
you know you’re either going to get remainder zero or remainder one if you
get remainder zero you call it an even number if you get remainder one you call
it an odd number so but this is about division division by three so there’s

00:15
going to be three cases to consider if the remainder zero if the remainder is
one or two so we’ll look at the case um you know three k
three k plus one three k plus two no matter what a we have
right because a can be any natural number no matter what a we have
a is gonna look like one of these three forms here a is either going to be
divisible by three or when you divide it by three it’s going to have remainder
one or when you divide a by three it’s going to have remainder two
so there’s only three possibilities to check for this
so we’ll check case 1 right here so if a looks like 3k and then we have 3k
squared and so you can already see that three divides all of this because

00:16
it’s a multiple of three right here it literally has a three right here
but this one right here if a looks like three k plus one what’s
happening right now so now we have a three k plus one that’s our a
and then now we have parentheses which i’ll change to brackets and then we have
three k plus one squared and then plus two
now how do we know all that is divisible by three this one is clearly because
it’s a multiple of three right here is this one divisible by three
well this is not necessarily divisible by three because it’s three k plus one
three k plus one and then now we have what nine k squared
and then we have a three k times two so six k

00:17
and then plus one and then plus two so as you can see here all of these are
visible by three right here so i can factor a three out of all this which
what if remember a can be anything so a could have remainder two if you divide
it by three so now i’ll have three k plus two
and now i’ll have three k plus two here with the square right we’re getting a
squared and so this will be three k plus two
and then now we’ll have nine k squared again and here we’ll have six k
times two so 12 k and then we’ll have a four and then plus
a two which will be a six and notice that all of this is also
divisible by three again that’s divisible by three so the whole
thing is divisible by three so this is divisible by three

00:18
so if a is any number of the form three k plus two then it’s divisible by three
all of this is divisible by three so that’s kind of the idea how
you can break up a and write a proof something like that
so let’s see it all written up so to show that three divides this
in other words we need to show that this right here is a is of the form 3k
for some k so in other words this we have to be
able to factor three out of all this and so what we’re going to do is we’re
going to break it down into three cases and this is the power
of the division algorithm any natural number when you divide it by three has
to have remainder zero remainder one or remainder two
so i’m going to break any natural number a up into three different cases so

00:19
if a looks like three k plus one then i’ll have a times a square plus two
and if we multiply that out we get a factor of three out of this right here
now for the case uh and and since it’s got a three right here this whole thing
is divisible by three so three divides the a times a squared plus two so three
divides that all right so for the next case if a looks like three k plus two
then plugging it in and we get a times a squared plus two and we simplify that
and we also can factor out a three in that case
so three will divide it in this case as well
finally if a is of the form three k plus zero or just three k
then we have a times a squared plus two and that’s three k
and then we simplify that right here and so no matter um

00:20
you know three will divide the ace a times a square plus two in all three
possibilities and those are the only three possibilities by the division
algorithm and again the way it works is because if you take a any natural number
divided by three there’s only three possibilities and we checked all three
possibilities so in all possible cases three has to
divide and that’s exactly what we’re trying to show up here
so that’s one of the powerful things about the division algorithm is it
allows a proof by cases so you might remember uh mathematical induction or if
you haven’t never learned mathematical induction uh i have a series below
in the description you can find a link to mathematical induction series but in
any case you can try to prove this by mathematical induction because here
we’re talking about all natural numbers and so that would be
a different strategy the strategy for solving this example in

00:21
this video is to use the division algorithm and to use proof by cases okay so
let’s look at um oh no that’s it for this video in the
next episode we’re going to work out a lot more examples and this
one was just to get us kind of warmed up and so i look forward to seeing you in
the next episode and i’ll see you there 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