text: # 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
  talked about this definition a great deal what it means to be divisible
  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
  this case happens to be one again and so if you think about this through what
  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
  um what about this expression over here well let’s write that out a little bit
  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
  means that this is divisible by three what about this case right here
  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
  you think in the comments
  
  About The Author
  
  David A. Smith (Dave)
  
  Mathematics Educator
  
  David A. Smith is the CEO and founder of Dave4Math. His background is in mathematics (B.S. & M.S. in Mathematics), computer science, and undergraduate teaching (15+ years). With extensive experience in higher education and a passion for learning, his professional and academic careers revolve around advancing knowledge for himself and others. His work helps others learn about subjects that can help them in their personal and professional lives.
  
  Let's do some math together, today!
  
  Contact us today.
  
  © 2022 DAVE4MATH.com