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