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

of our computations and so real excited about this video

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

at that right there already sorry about that

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

about this case right here so now if a looks like three n plus one

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

you think in the comments