Divisibility and the Division Algorithm (Beautiful and Useful)

Video Series: Divisibility in the Integers (Step-By-Step Tutorials for Number Theory)

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

00:00
you want to learn about divisibility what are the basic properties of
divisibility can you prove the division algorithm
without the well ordering axiom we’ll also do some examples together
let’s do some math hi everyone welcome back uh we’re going
to begin with the question what is divisibility
and so we’re going to start off with this definition here
if a and b are integers a is not zero then we’re going to say a divides b
if there exists an integer c such that b equals a times c
now if you haven’t seen this definition before
then i highly recommend that you check out the series right here
the visibility and the integers step by step tutorials for number theory
so in previous episodes of this series we talked more about this and we

00:01
motivated why we would want to look at such things
and so we’re going to carry on with our studying of divisibility and so
we’re also going to say that a divides to b is equivalent to
all the following we’re going to say a is the divisor of b
so it all means the same thing right here if
if if there exists an integer c right so a is the divisor b means the same thing
a divides b this is the typical way of writing it
um b is divisible by a that’s also all these are very typical
um and then b is a multiple of a right so b is a multiple of a
and a is a factor of b so we can factor out when you’re looking at b you can
factor out an a um and so what are some of the basic properties of divisibility
uh well actually before i go on to that let me um
you know give some very quick basic examples here

00:02
we talked about this in in other episodes i just want to run through them
really quickly again when we say 3 divides 6 so that means that six is equal to
there has to exist an integer c right and so what will be that integer
here we have six equals you know six equals let’s try to get right there
six equals three and then what’s that c so
that c right there has to be an integer c and two is an integer so
you know it’s just three times two so yes that works and what about 6 divides 24
so we can write 24 equals 6 times 4 and so yes this works also
what about 8 divide 0 so 0 equals 8 times 0 so again yes

00:03
so in each case i’m coming up with an integer 2 4 0 these are all integers here
what about minus 9 divides 909 right so we can write 909 as minus 9
times an integer if we can find an integer then we can say yes
and in fact that integer is just what minus 101 and so yes this is also true
now if it’s not true for example minus 9 divides 10 that’s not true
then we’ll just use a symbol like something like that right there to
you know say it doesn’t work and we always assume that a is not zero
so if i have zero here then no matter what i put right here this is
not going to hold just by definition um now if if a divides in
and a and n are positive then what we can say here is if a divides in

00:04
i’ll put it over here a divides in a and n are positive
so you know sometimes we’ll use an n instead of a b but the point is is that
n is equal to a times k for some integer k and so
you know these two sentences are also the same
n equals a times k for some integer k or said differently a divides in now so
let’s look at some of the basic properties of divisibility here
if you’re going to be working with in the integers working with number theory
or computer science or anything like that you’re going to need to know the
basic properties of divisibility so property number one is if a divides b

00:05
and b divides c then a divides c and so for each one of these let’s see
if we can sketch a short proof here so number one here here’s what a proof
would look like so a divides b and b divides c so we have two
uh two things here this is known as the hypothesis right here we have an if then
so this right here is the hypothesis so um assume a divides b and b divides c
so by definition of divisibility which i’ll just abbreviate by definition of
divisibility there exist integers and i’m going to use an integer for this
statement right here so we’re really using definition of divisibility twice
once for here and one’s for here so for this one right here i’ll say i have an m
there exists there exists an integer m and

00:06
i’ll use an n for this statement right here there exists integers
now i need to say integers integers m and n such that
so for this right here we have b equals and for this one i’m going to use the m
so b equals a times m and this one right here c is equal to and
i’m going to use the n for this statement right here so c is equal to b times n
okay now what we want to end this proof is to
reach our conclusion right here we need to reach this conclusion so the step
before this one would be c is equal to a times some integer right
we need to fill in this blank right here and this doesn’t give it to us and this
doesn’t give it to us but putting them together we can get it so since
b is uh sorry not b c is equal to b times n and this b is a times m

00:07
right so using substitution for b and then using the fact that
multiplication is associative so now i have c is equal to a times m times n
and it’s important that whatever we put here has to be an integer so since this
holds and m times n is an integer we have c divides a as needed and so um
i’ll get all the way here a little bit so we have c divides a as needed there
we go let’s get rid of that and that and that and there’s our proof of number
one very good so let’s look at number two now get rid of that real quick
if c divides a and c divides b then c will divide this thing over here

00:08
and x and y can be anything so you can put any x and y you want here
so let’s see if we can write a proof for number two here so proof
and i’ll put a two here proof of number two so assume that c divides a
and c divides b so by definition of divisibility again by definition of
divisibility there exist and again i’m using two
statements so there’s going to be i’m going to use two integers there exist
integers uh m and n i’ll use an s and t this time actually s and t such that
so i’ll use the s for this one and the t for that one
so here i’m going to get a is equal to c times s and that should say c divides b

00:09
right c divides b and so b is equal to uh let’s use the t c times t
okay so now let’s take a look at what we want
so this is this is the direct direct proof i’m just starting with my
hypothesis and coming up with my conclusion but before i come up with my
conclusion i need to know what my second to last step is in other words what
would get me here what does it mean to say c divides this
so it means that x a whatever all this over here is plus y b
is equal to c times some integer so we have to fill in this blank here with
some integer so we need to build this equation right
here and come up with an integer right here
that says b equals c times t that’s a t sorry um so let’s
to build this equation we need an x and a y right so let’s say x and y are any
positive integers for any positive integers x and y so let x and y be

00:10
positive integers and i’ll say then and now i’m going to try to build this
right here so then here we go x a plus y b
equals and for this a right here we’re going to substitute in cs
that’s for the a and then y times the b and for this b i’m going to substitute
in c times t and we can factor out a c and then i can say this is x x s plus y t
and then i can say where all of this is an integer x x s plus y t is an integer
now that’s important to know that that’s an integer we’re only working with
integers in this episode so we have that c and then times some blank

00:11
which is an integer is equal to all of this so by definition
so i’ll just say by definition we have c divides you know this xa plus yb
as needed it might say why do that i don’t like to end
on some math symbols unless i can just naturally avoid it so by definition of
divisibility we have c divides this as needed there there we go all right so
there’s number two right there and let’s look at number three real
quick let me erase this and uh play this right here for us
all right number three if c divides a and c divides b then uh
uh hey wait a second that’s actually the same one isn’t it well that’s not uh

00:12
you know what we want so let’s see if we can not have that repeated
sorry i had to look off screen there for a second one to get rid of that uh
all right here’s number three so let’s say proof and let’s go up here and say
if a and b are non-zero and a divides b and b divides a so assume
a and b are not zero and all right so also assume that
a divides b and b divides a so again i’m going to use the definition
twice once for this statement once for this statement
so by definition of divisibility again by definition of divisibility there

00:13
exist integers say i’ll use one integer for this and one
for this this time let’s use a u and a v
so there exist integers and i’ll say a u for this one and a v for this one
such that so these integers exist such that b is equal to a times u
and a is equal to b times v hence a is equal to b times v
which is if we substitute in for this b a times u times v
which we’ll write it out as a is u times v and we know that these u and v are um
integers right so we have an integer here now
everything’s an integer the only way this could happen is hence this right

00:14
here uh shows that u times v is in fact one
and they’re both integers right so the only way this can happen is
um if they’re both positive one or they’re both negative one
now could they both be negative one so a and b are you know not zero um and so
[Music] non-zero so why can’t we have uh they’re both negative right
so then we would have b is equal to negative a
and a is equal to negative b negative v right here um so if a and b are non-zero
yeah so if a and b are positive let’s just say are positive

00:15
that way we don’t need to use anything like an absolute value
so if a and b are positive right so since um now we’ll assume that they’re both
positive otherwise we’ll have to put absolute value on here which is fine
and you could write proof out for that but all right so that since they’re both
positive since they’re both positive we have that u and v are both one hence
a is equal to b a here is uh these are both ones so um
yeah so these are both ones here so a is equal to b
however you want to look at it all right so for part four here
let’s look at another one here part four and so here we go proof of 4 proof of 4

00:16
and here we’re going to assume that c is not 0 and a divides b so assume [Music]
c is not 0 and a divides b uh so why write your hypothesis twice
well some people don’t assume c is not zero and a divides b
by definition of divisibility there exists an integer and now i just
need one integer because i only have one divisibility here there exists an
integer um let’s say n such that b is equal to a times n
all right and now we’re just going to say
you know c you know we already know c is not zero now what do we need to finish
our proof we need that and what does it say bc is a times c
times some integer so we need to put an integer in here

00:17
so that means i need to start off with bc and come up with some integer here
all right so such that all right then bc is so we already know what b is right
so b is a times n and then so bc and then moving parentheses around i get
a times n times c and but what we really want is ac next
to each other we can do that because we can just uh switch all this around here
well integer multiplication we got associativity we got commutativity so and so
again by definition of divisibility ac divides bc
all right so we could say all those words if we want to
you know multiplication is associative in the integers and
cumulativity is also used right there all right so
um let’s use this one right here number five so this one is going to use uh

00:18
mathematical induction so let’s do a proof here proof of 5 and so by the way
if you don’t know what mathematical induction is then you just have to skip
this example or if you want you can hey you can start
out on this series right here mathematical induction the complete
step-by-step guide i take you through mathematical induction everything you
want to know about it and then now we can use it right so we’re going to assume
that a divides b we’re going to do proof by induction so proof by induction in
so the case for the base case holds by assumption so the base case holds
because we have a to the 1 divides b to the 1 which we’re assuming holds the

00:19
base case holds by assumption so assume that a to the k divides b to the k for
an integer k okay so we’re going to show that a to the k divides b to the k
plus one sorry we’re going to show that and let me let me drop that down here a
little bit further we want to show this this is where we want to end
we want this we’re assuming this holds for integer k um
now for a positive for a positive integer k
and so we want to end up with this so right so what do we need the step right
before this that will guarantee that we get this so we need b to the k plus one

00:20
is a to the k plus one times something we need to fill that in right there with
an integer what is the integer that goes here can we in fact find one if we can
find an integer that goes here then we’ll have this right here and then
mathematical induction will hold so we need to start off with this then
so b to the k plus one which i’ll break down as b to the k times b
and then now for this b to the k here i’m going to use this uh statement right
here so b to the k remember we’re gonna use
definition of divisibility right here so b to the k
is a to the k times some integer which we’re gonna need to name so i’m to say s
so just some s i’m not using s anywhere in this number 5 here so i’ll just come
up with s so b to the k so remember we’re assuming this holds so that means

00:21
we can find some integer s so i’m going to say here this b to the k is
uh a to the k times some s and then all that is still times b and then i’ll say
for some integer for some uh integer s okay
and that’s exactly what we wanted right there and so all right
let me erase this part right here so this b here now what we also know
is that a divides b right so you know we’re assuming that right so
not only did we apply divisibility uh for this statement right here
definition uh divisibility but also for this one right here so from this right
here we know definition of divisibility so a is equal to

00:22
so b is equal to a times some let’s call it t
right that comes from this hypothesis right here
and so let’s rephrase this right here so a to the k s b and then a to the k
and then an s and for this b we’ll write it as a times t
and then that will append the sentence for some integers s and t
so this s came from uh this using the definition of
divisibility here and this t came from using the definition of divisibility here
all right and so um so then all that happens which yields
b to the k plus one is equal to a to the k plus one
times some s and time times some t and since s and t are integers
where s times t is an integer also right the product of two integers is an

00:23
integer is an integer hence b to the k plus one divides eight to the k plus one
so by induction and let me get all the way here a little
bit i’ll try to move small up here so by an induction this has to hold for all
so by induction uh a to the n divides b to the n for all positive integers in
and there we go so there’s number five right there so there’s five basic
properties of divisibility and you know a small proof to help you
it’s important to look at these proofs for a variety of reasons uh number one
you really just don’t want to believe someone is true that’s not the
scientific method that’s not you know the way to do mathematics but

00:24
also more importantly as you move along in your you know
understanding and learning mathematics is you need to start moving from numbers
to theory right and that’s one of the reasons why
i love number theory at least teaching it is that it’s
you know it’s very practical it’s about numbers but at the same time it’s a good
place to start learning how to write proofs alright so
now it’s time to get to the division algorithm so here we go
what is the division algorithm uh let me play another one of these real quick
all right so what is the division algorithm
so first off we’re going to review the well ordering axiom so the well ordering
axiom states that every non-empty set of positive integers
contains a least element and now this statement we’ve talked about before
we’ve talked about it previously in this series but we also talked about in the
mathematical induction series this is a very fundamental statement

00:25
about the natural numbers and you know you should absolutely know
this statement right here have it you know just just you just know it
it’s an axiom meaning we’re not going to prove it um
on the other hand in terms of the mathematical induction series we
actually show this statement under certain conditions is logically
equivalent to mathematical induction so um
let’s see what the division algorithm is
now so the division algorithm is and the reason why i’m showing both of these is
because we’re going to regard this as a theorem
this is going to be something that we’re going to prove and we’re going to base
our proof off this more obvious statement here if it’s a bunch of
positive integers then it has to have a least element
all right so what does the division algorithm say so if a and b are non-zero
positive integers then there exists unique integers q and
r q is called the quotient and r is called the remainder and they’re unique

00:26
and such that this equation holds and this inequality holds
so i’ll just do as we’re going to work on the proof over here i’ll have an
example out for us over here so what about if say a is 5 oh sorry a is 12 and
b is 5. is there a q and an r right so they’re
positive integers so there has to exist a q and an r
so we can write this 12 as five times a quotient which will be two
plus some remainder and the inequality over here is zero is
less than or equal to the r which is the two and that’s strictly less than the b
which is 5 right there so here’s our example right here
and we’re going to need this as we go through the proof right here so proof
proof now this proof will have two parts so i’ll put part one and i’ll just say

00:27
it has two parts here i’ll put it up here actually part one and it has part two
and so i’ll let you know that we’re on these two different parts
right now so we’re on part one right now and the part one is called existence
so i’m just going to put the word existence here
so first off you see because there’s two parts to it because q and r are unique
so first off we have to show that q and r exists
and then we have to show there’s at least one
and then we have to show they’re unique there cannot be more than one right so
there’s two things to prove that q and r exist first
all right and so let’s do that right here so let’s say here that let b be a
natural number and it’s just going to be a natural number greater than zero

00:28
be a positive integer and let s we’re going to make up a set here
uh let me move down here and let s be this set right here so s is the set of
multiples of b um and you know b is a natural number and bi is greater than a
so i’m making up this set right here so and let’s think about what this set here
s is over here so so the s is the multiples of b
right so b is running here one two three four five and then we got a condition
we’ll we’ll see this condition here in a
second but just think about multiples of b so s is made up of multiples of b
so this in this example over here we’re looking at 5. so 5 times 1 5 times 2 5

00:29
times 3 5 times 4 and so on 25 right and so s is all the multiples of a 5.
now s also has another condition though all the multiples of b
that are greater than a so what is the a over here
is 12 right so these are not in b cross these out here oh sorry these are not in
s right so s is made up of all the multiples of b that are greater than the a
and so no matter what a is we can keep adding multiples of b just add multiple
add multiple add multiples just keep adding a bunch of multiples right 15 20
25 and so on but start your set s for the ones that are greater than a
right so that’s what the set s is now it’s important to use the set s and
the reason why is because we’re going to use the well ordering axiom here
so the well ordering axiom says every non-empty set of positive integers

00:30
must have a least element now when we’re looking at a concrete example over here
we can say yeah it has the least element
it’s 15. it’s 15. but over here we don’t know what a and b are and so we don’t
know what the least element is we can’t say exactly what it is but we can use
the statement to say it has to have at least one and the reason why is because
this is non-empty so let’s say let’s write that first so notice
notice s is not empty since a times b which is in this set s right because
it’s multiples multiples of b multiples of b and that is greater than a
um and so now we’re going to use the well ordering axiom so what by
and i’ll just say well ordering axiom s has a least element has a least element

00:31
has a least element um say let’s call it bk b times k now since k is non-zero
right so there exists a natural number there exists a natural number q
i’m going to call it q such that so we can back off one right here from this k
we can back off because k is not zero right so k could be one two three so we
can back off one such that k is equal to q plus one
or q is equal to k minus 1 if you want so notice that
b times q is less than or equal to a because b times k is the least one

00:32
that’s greater than a and so if you back
off one right here then it could be less than or it could be equal to a so this
right here is less than or equal to a so notice that this right here is true
so there exists a natural number a natural number r
um natural number r such that a is equal to bq plus r
now before we go any further let’s just check it out over here right so
over here it’s 15 right so b times k s has the least element b times k
and it’s 15. so it’s five b times k so the k is three now three is not zero
so there exists a natural number q so you know we back it off right k is three

00:33
and so over here we’ll write it as two times plus one and so the q is the two
so we’re backing it off one and then if we back it off one right we
get we use the 2 5 times 2 is less than or equal to a it’s not in here
because these are the ones that are greater than a so b q
b times q is less than or equal to a so if it’s less than that means we can
add a number r and it could be zero right so we add another r
so that we get equal right here right so b q is
less than or equal to a so we’re going to add a number r to it to get equals
all right and so now we got the q and the r here
but we got to check this right here also so the r here is greater than or equal
to zero right but what about is it less than b so here’s where we’re going to

00:34
i’ll put a assume that that doesn’t hold so assume that r
is greater than or equal to b so then there exists a natural number
a natural number let’s call it m such that natural number m let me move
up here now a natural number m um you know so it’s zero or greater um such that
right and so you know we’re gonna have to add a little bit of something to the b
to get to the r so let’s say it’s b plus m equals r
and now we’re going to substitute it all in and check it out so by substitution

00:35
so a is equal to b times q plus one so you know plus m and so that comes from
if we’re looking at um a is equal to bq plus r and now we can say bq plus um
and use this right here and so we get this right here now and so
now we can say bk is b q plus 1 is less than or equal to a
and that’s a contradiction because remember b times k was the smallest one
that was greater than a so there’s our contradiction right there
so we’ll just say contradiction hence r is less than b as needed there we go
so this right here is just scratch work it’s not really part of the proof here’s

00:36
the proof right here it’s just part one the existence part
we came up with a q and an r and the way that we did that is we
looked at the b we looked at the a and we made up the set here s and we made
multiples of b’s multiples of b’s but then we took out the ones that were less
than a and we said it has to be at least and that least one
was not going to quite be the q here the q is a two so we had to back off one
and now we’re less than or equal to the a and so then we’ll end up getting the
remaining part right there which is going to be the remainder part right
there and then we prove that that remainder had to be less than the
less than the five because it was greater than the five then we would end
up with something that wasn’t going to be in the set right there
so there we go there’s the proof of the existence part
now let’s prove part two now that we know that there is at least one q and one r

00:37
now let’s go and prove that it’s unique so let’s do that real quick uh let me
get this out of the way and so now we’re going to do proof
and i’m going to say uniqueness right here
so proof of the uniqueness here we go so suppose and let me move down here
so i’m going to put it all up here so suppose a is equal to bq1 plus r1
and a is equal to b q2 plus r2 and this r1 here is a remainder so it’s
less than the b and the r2 is also a remainder so it’s less than the b here
so suppose this this and this let’s let’s write that sentence out
there like that right there all right and so now we’re going to say

00:38
we’re going to have three different cases here we’re going to be looking at
the quotients here q1 and q2 and we’re going to be arguing on those
so here we go let’s suppose first so if q1 is equal to q2 what can we say then
so if q1 is equal to q2 and then what are we going to get here
if these are the same then these are the same and the a’s are
the same so then r1 is equal to r2 so if q1 is equal to q2
then i’ll change that to then r1 equals r2
you know just by substitution i’ll just say by substitution
right so you just say r1 is a b a minus b q1 and then these are the
same so this is a minus b q two and which is r two right so r one equals r
two just by substitution right there all right so now let’s look at the case

00:39
where it’s greater and then let’s look at the case where it’s less
and the cases are going to actually be the same
because all the information over here is symmetric with respect to q1 and q2
so we’re actually going to look at the case now where q1 is less than q2
all right so let’s assume that so then q2 which is the bigger one here
is equal to q1 plus some makeup integer let’s call it m for some integer n
greater than zero and that’s because we’re strict here
so this is strictly smaller so we’re going to need something positive some
integer positive to meet it all right um so this implies so this implies that r1

00:40
i’m going to start off with r1 so you know in in all three cases that
we’re going to have we start up we start out by something on
assuming something on the q’s and we’re concluding something about the r’s so
i’m going to assume something about the q’s and now i’m going to show something
about the r’s and in this case there was nothing to
to say other than they’re equal well what about if q1 is smaller so r1 then
will be a minus b q1 right from that one right there
and so now we can substitute in so this will be the the a here will be bq2
plus r2 and then we still have the bq1 here right so we’re just substituting in
what the a is right there for that right there and now we can say right because
you know if we look at this n right here n is what q 2 minus q 1

00:41
we have a q 2 minus q 1 here so we can write this out here as let’s
see if i can squeeze it in over here b and then i’m factoring out the b
and i’m getting q 2 minus q 1 which is the n and then plus r 2 still
and that right there is greater than in fact i think i’m just gonna like
switch it over here so that’s just factoring out the b and then plus still r2
and then i’ll come down here and so we’re going to read along here and then
we come back down to the next line and that’s an n so bn plus r2
now this is strictly greater than or equal it’s greater than or equal to bn
because r2 could be zero right so r2 could be zero right here so this is if i
take away the remainder i i could be taking away nothing zero so it could be

00:42
equals here but r2 could be greater than
so i’m just going to say greater than or equal to here
so right now we got r1 is greater than or equal to bn
which is greater than or equal to b and that is a problem because r1 was
supposed to be strictly less than the b right here all right so
this is a contradiction because arts r1 is strictly less than b right here
all right and so now the case when i switch these will be exactly the same
i would just make a slight change over here i would say then r2
here and blah blah blah blah and i would get r2 is greater than or equal to b
and that would be a contradiction to this one so you know just by symmetry so

00:43
i’ll say if q2 is less than q1 then similar case all right so
no matter what case we’re in whether they’re equal or this one is less than
q2 or the other case um in all cases the um it either can’t hold or
they’re the same here so that’s how we’re going to prove uniqueness right there
alright so you know we did all the cases for the qs all right so let’s um
look at some examples now what is the division algorithm
the advantage of the division algorithm here let’s look at the advantage here
now so we’re gonna say that an integer a is of the form
bq plus r right quotient and remainder if there exists integers b q and r
right and so i just kind of relax the condition and we’re using a little bit

00:44
different words here and we’re going to say is of the form
right so a is of this form meaning we can write b q plus r out
and so you know this is just work nice easy words to represent all of this
right here so the division algorithm in a certain sense measures
the divisibility of a by b by using a remainder if the remainder is zero right
so if you have b q plus r if the remainder is zero then
you know you actually have an integer right here and you have divisibility
in any case the event the advantage of the division
algorithm or one of the advantages of the division algorithm is allows us to
prove statements about positive integers by considering only a finite number of
cases so this is going to give us a different
type of way of proving something other than say mathematical induction

00:45
so here’s an example of what i’m talking about show 3 divides a
times a squared plus 2 for any for any natural number a no matter what a is
3 has to divide this number right here so for example what if a is say 6 right
then what is 6 times um 36 plus 2 38 right so
3 will divide that because it already divides 6.
what if i put a 7 here or let’s say 5 does 3 divide
this right here let’s see here what’s 5 times let’s say here 25 plus 2 will be
27 does 3 divide this yeah there’s a 3 in
here right so let’s prove this no matter what a is
whether a is 6 or 5 no matter what a is and so here’s how we’re going to do that

00:46
so proof so by the division algorithm by the let’s abbreviate that by division
algorithm a has exactly one of these forms one of the forms three k
three k plus one or three k plus two in other words if i take uh any a
and divide it by three it has to have remainder zero one or two there’s no other
there’s no other possibilities when you take an a no matter what a is
and you divide it by three it has to have one of these remainders here
so let’s look at each of these three cases so this is going to be a finite
number of cases so i’m going to say case 1. what if a looks like 3k so a is 3k

00:47
so what does this become now in that case so a a squared plus 2 this will be 3k
and then 3k squared so that’ll be 9k squared plus two
and this is already three times something what is that something three
and then i’ll put a k and nine k square plus two
and all that doesn’t really matter we got a three out right the first part was
a three just like when we did a a was six six already had a three in it so it
already it already worked so here this this product right here already has a
three in it so three already divides this right here so hence
three divides a times a squared plus two as needed now let’s look at case two
now if we divide three by a by three we get remainder one

00:48
what happens in this case right here so now we’ll look at a times a squared
plus two and this will be the a will be three k plus one
and now this will be three k plus one squared
and so if i if i square this i get nine k squared plus six k plus one
and then we’re going to add a two so i just square the k and then plus 2 and
this doesn’t have a 3 in it because it’s 3k plus 1.
but if we look at all this there is a 3 in it here isn’t there because i did 1
plus 2. so this has a 3. so i can factor three out of all this
and i’ll do that real quick right here so i’ll say a is three and then three k
plus one and then what do we get here when we
factor out the three we still get a three left here
and we get a 2k here because we’re taking out three and then this is the
three and so if i factor out a three i get a one left over

00:49
and so i get three times something and so again in this case right here we
get hence three divides a times a squared plus two
all right and so then we have one more case to go
one more case to go and i’m going to have to erase part of this to get to
that case so let’s just erase case 2 and we’ll do the case for 3k plus 2
there so let’s do that real quick so case three
is when the remainder is two so three k plus two
and then a times a squared plus two becomes so the a is three k plus two
times and then now i’m going to have to square this so this is going to be 9 k
squared plus 3 times 2 times 2 so 12 k and then 2 squared is 4

00:50
and then we’re still doing so we did the a squared and now we need to do plus 2.
and so can we factor out a 3. again we cannot factor out 3 on this one
but can we factor a 3 out of all this this has got a 3 in it this has got a 3
in it this is a 6 so that has a 3 in it so long story short right i’ll just
write it out real quick 3 k plus 2 and what happens if we factor a 3 out of
here we get a 3 k squared and then this 12k here we get a 4k
now this is a 6 and i’m going to factor 3 out of it so i got a 2 left over
and so hence 3 divides a times a squared plus two
now we showed this in all three cases that three divides this no matter what k
is i divided three so no matter what a is i divided a by three and there’s three
cases in each of the cases three will divide this right here

00:51
so you know there’s an example of how to use the division algorithm so for any
natural number a sounds like we have to prove something for infinitely many
values of a which we do but the division algorithm allowed us to
break our proof up into only three cases right here so very powerful proof
all right so there we go there is um let’s go here now all right so there’s our
video our episode um and in the upcoming episodes we’ll look
at prime numbers and we’ll have a lot of fun with that so i look forward to
seeing you then have a great day bye if you enjoyed this video please like
and subscribe to my channel and click the bell icon to get new video updates

About The Author
Dave White Background Blue Shirt Squiggles Smile

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.

Account

Affiliates

About Us

Blog

© 2022 DAVE4MATH.com

Privacy Policy | Terms of Service