Math 20 - Lesson 13

Uploaded by PCCvideos on 09.09.2009

A Portland Community College mathematics telecourse.
A Course in Arithmetic Review.
Produced at Portland Community College.
Every once in a while, one reads in the newspaper
about how some computer whiz
had just discovered another new, large prime number.
It seems to be important. Just what is a prime number?
A prime number is a whole number greater than 1
whose only factors, that is divisors, are 1 and itself.
For instance 3.
I can't divide it by anything except 1 and 3.
The same with 11 and 23.
All other whole numbers are called 'composite numbers.'
An example would be 6.
I not only can divide that by 1 and 6,
I can divide it by 2 and 3.
So prime number is a number I can't divide
by anything except itself and 1.
Prime numbers are of great importance to number theory
and to computer coding.
As of yet, it is not known how to predict the nth prime
without going through those below it.
That is, if I wanted the 1,000th prime,
I'd have to find the 999 primes under it first.
Great prizes are being offered by various scientific agencies
if anybody can find such a rule.
We don't even know if such a rule is possible.
But nevertheless,
prime numbers are of importance to advanced studies.
And we will use them ourselves within the next few lessons.
They will make many tasks a lot easier.
To get ready for its use, we will be asking questions like this:
Is a given number [ 723 ] either prime or composite?
It's easier to check for composite-ness.
If it's composite that means some number
other than 1 and this [ 723 ] will divide into it.
Well, we can tell that 2 won't because that's not even.
Let's use our divisibility test.
7 and 2 is 9 and 3 is 12. [ 7 + 2 + 3 = 12 ]
3 goes into 12, [ 12 ÷ 3 ] so 3 will divide it.
So we know that that number is a composite.
How about 151?
Well, let's set up some possible divisors other than 1.
Now, how far should I go?
Well, remember our last exercise?
The approximate square root of 151.
12 times 12 is 154. [ 12 · 12 = 154 ]
13 times 13 is bigger, than this [ 151 ] [ 13 · 13 ]
so 12 is about as far as we have to go.
If none of these divide, that's prime.
See, that's why we've had the preceding lessons,
and that's why the divisibility test is nice here.
To check 2, we check the ones digit, the answer is no.
To check 3, we add the digits,
1 and 5 is 6 and 1 is 7. [ 1 + 5 + 1 = 7 ]
3 won't divide that.
To check 4, well if 2 won't, 4 can't, so we can forget that.
To check 5, that's [ 1 ] not 0 or 5 so 5 won't.
6, well 2 wouldn't, 3 wouldn't, so 6 won't.
Now 7, there's only one fast way to try 7,
that's just to flat try to divide it.
And we'll use a calculator.
151, divide by 7 is, [1][5][1][÷][7][=]
see we get a decimal, so 7 won't.
Now of course, if one has a calculator
it's almost to try the divisibility
all the way through with a calculator,
but let's stay with our divisibility list.
8 we won't try because 2 wouldn't,
and 8 has lots of 2s in it. [ 2 · 2 · 2 = 8 ]
9, sum is 7, 9 won't divide 7.
10 won't.
11, we have to just flat try it out.
And that's not too hard even to do mentally.
We can see, no.
12, well 12 is 3 times 4 [ 3 · 4 = 12 ] and they won't.
So none of the numbers up to this maximum one that have I to try,
which is the approximate square root of my number,
none of them up to this will divide that.
So that means that this number is a prime number.
Prime numbers are of such importance
that all math handbooks will contain a list of prime numbers.
Here's an old handbook that's older than most of my students.
And sure enough, here's two pages of factors and primes,
of numbers all the way to 1,000.
And that's a small list.
I have books that have even more than that.
Have you noticed a partial list at the back of your own textbook?
It's there.
How does one get primes?
Well, the technique used by the ancients
called 'a Sieve of Eratosthenes,'
who was a Greek mathematician who lived many centuries ago,
was simply this:
Start counting.
Here I've counted all the way up through 110,
but make this list as long as you want.
Then hire somebody, who's cheap, but can count,
and start with 2. That's my first prime number.
Now start counting, and every time you get 2
2, cross it out.
2, and so on.
Now, you just crossed out half your list.
But you've crossed out in fact all the numbers divisible by 2,
and they're composites because they're divisible by 2.
Then the next number in your list must be a prime.
That's 3 and it is.
Now start counting.
1, 2, 3, cross out.
See 6 was not only divisible by 2 but by 3.
1, 2, 3.
And of course 9 is divisible by 3.
1, 2, 3.
12 was divisible by 2 and 3.
And so on forever.
And you have just crossed out all the multiples of 3.
Now, the next number in your list that's not crossed out is 5.
And always the next one that's not crossed out
will be a prime number.
Now we would instruct our hired hand
to cross out every fifth one.
1, 2, 3, 4, 5, and that's 10, which is divisible by 5.
1, 2, 3, 4, 5.
And so on forever.
And we've just eliminated all the multiples of 5.
The next one on my list, which is 7, will have to be prime.
Now we start crossing off every seventh one.
Now you begin to get the idea
and also the idea this is a long, tedious job.
As it turns out, to compute primes is a very complicated task,
and that's why they're involved in tables.
For that reason it would be well for you
to have a short list with you
for some of the work coming up very soon.
And here is some primes up to 109.
Of course the list is endless.
But you don't need a very long list
for most of the problems we will handle.
At our school, we have a small 3 x 5 cards
which will have a list of primes up to about 500.
Then on the other side we have some basic formulas.
It might be handy for you to make such a card
that you can just carry in your pocket
or use in your book as a bookmark.
If primes are that important,
how far must one go
in order to check if a given number is prime?
How about 409?
Let's say we were going to try, 2, 3, 4, 5, 6, 7, 8, etc.
Well, as it turns out, we don't have to try all those numbers.
There's a real nice rule which cuts our work greatly.
To check for prime-ness,
one need only check for divisibility by other primes
up to that prime number which is less,
just less, than the approximate square root of the number.
Now this statement here
that I only have to check divisibility by other primes
saves me a lot of trouble because most numbers are composites,
and this says we need not even try them.
That rule says to check divisibility into 409,
I need first only use prime numbers,
all the in-between composites I need not try.
And furthermore, I don't have to go on forever,
I just have to go as far as that prime
which is approximately equal to the square root of 409.
Well, if one has a calculator with a square root key,
and most do,
you punch in 409, punch in square root, [4][0][9][√]
and this says 20.22.
So that says, Find the nearest prime number in your list
less than 20.
So that's 19.
So that says the only numbers I need try
to see if 409 is a prime,
that is, if I didn't have a list
if I had a list, I'd just look on it,
is these right here.
Now, let's talk calculators, on this a little bit.
We're going to see if 409 is divisible by any of these,
which means we're going to use 409 for each one of these.
Therefore, put your 409 into memory and simply say divide by 2.
Well, 2 we don't have to try because we can see it's not even.
3, well, 4 and 9 is 13, [ 4 + 9 = 13 ]
3 won't go into that. [ 13 ÷ 3 ]
5, that's not 0 or 1, 5, 5.
So the divisibility test that we've had just a moment ago
eliminates those without the calculator.
Now we try 409 divide by 7. [ 409 ÷ 7 ]
If I get decimals, it won't go in.
So I eliminate that.
Memory recall. [RM] There's my 409 again.
Divide by 11, [RM][÷][1][1][=] decimals, it won't go in.
Memory recall, 409 again, divide by 13. [RM][÷][1][3][=]
Decimals, that won't go in.
Memory recall, divide by 17, [RM][÷][1][7][=]
decimals, that won't go in.
Memory recall,
my last prime number I need to try now,
divide by it, [RM][÷][1][9][=] decimals, it won't go in.
So now we can add 409 to our list.
It is prime.
Now, see if we use all the facts
we've been learning up to now along with the calculator,
this is a fairly easy, fast job.
Students often ask:
can we use calculators instead of arithmetic?
Actually you'll end up using both,
arithmetic facts and the calculator together.
Let's go through this next problem very slowly together
so we can use it as an excuse to formulate a clean set of rules
for answering the question,
given a certain number,
can we determine whether it's prime or composite?
So once we have been given that number,
the first thing we probably want to do
is to find the approximate square root of that number.
And to state this symbolically of course,
this symbol [ √731 ] means I want to find the square root of 731
And these two wavy equal signs [ ≈ ]
says I want the approximate one.
Let's use a calculator.
Here I'll use a slightly different calculator
where we can see things a little bit easier.
I want the square root, here's the square root sign, of 731.
Push the equal. [√][7][3][1][=]
And I want the approximate one,
so I'll just take the whole number portion which is 27.
So we know this approximate square root of 731, is 27.
Now, of course you could do this by hand
by guessing 20, which is too low,
then maybe 30, which is too high.
And after three or four guessings and checking them
by squaring each of these to see if it's close to that,
we would finally arrive at 27.
So the only difference between a calculator and by hand
is a matter of time.
You, the mathematician, in either case
must still know what you're doing.
Once we have that number, the next thing we wish to do is,
list all the primes up to that square root.
And see, this demands
at least we have a list of the beginning primes.
So in our case we want to list all the numbers
from 2 up to the nearest prime just under 27.
So that would be 3, 5, 7, 11, 13, 17, 19, 23.
So we're going to actually try each of these [ primes ]
and see if they will divide this [ 731 ]
Our claim will be if none of these will divide this [ 731 ]
then this [ 731 ] is prime.
Now, you might say,
but what if I don't have such a list as this list of primes,
what would I do then?
Then you would simply list every number.
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
all the way up to 27.
So if you know the primes, that will give you a lesser list.
The next question you might ask is:
are we saying there'll be no divisor of this larger than this?
Well, let's go up to this and that question will answer itself.
So after we've listed all the prime numbers
up to the approximate square root of our given number,
next we want to try each
to see if any of them will divide into the given number.
And of course we mean to divide evenly.
And you may do the trial division into our given number
by using calculator if your teacher allows you to use it,
or by hand.
But the first three, 2, 3 and 5,
you can always try mentally without the calculator.
In fact, it's faster without that.
We look at 2, this is not an even number, so 2 is not a divisor.
Look at 3, [ 7 + 3 + 1 = 11 ] the sum of the digits here is 11,
3 won't go into 11, so that eliminates that.
The end digit, the units digit is not 0 or 5, so 5 is ruled out.
So usually you can check these three almost instantly
faster by hand than with the calculator.
And if you're reasonably good at whole number arithmetic,
usually at the beginning
it's just as fast to do it by hand as it is to use a calculator.
So to check to see if 7 will divide our given number,
we can see that 7 go into 7 once,
and immediately we can see it doesn't go into 31,
so that rules 7 out.
Checking 11 again by hand, 11 goes into [ 73 ] here 6,
we can see that 11 does not go into 71,
so that rules that out.
731, is it divisible by 13?
Again, by hand, it looks like it goes in about 5 times.
Again, I can see it doesn't go into here,
so 17 is ruled out, or 13 is.
Trying the 17,
looks like it goes in there [ 73 ] about 4 times.
Four 7s, 28, carry the 2. 6, [ 17 · 4 = 68 ]
51. [ 731- 680 = 51 ]
If it goes in at all, looks like it's about 3.
Three 7s, 21, carry the 2, 5. [ 3 · 17 = 51 ]
Bingo. We have it.
I did these by hand to again encourage you
to not over rely on the calculator.
Very frequently it's just as easy to do it by hand,
and it's best that you do it in that case.
Okay. So since we know that
one of these numbers in this stream will divide into this,
then that tells me the number is not prime,
it's a composite number.
But look what else happened.
To check that this division is correct,
do you remember how we did that?
We take this quotient [ 43 ] times this divisor [ 17 ]
and ask: Is the product equal to this dividend [ 731 ]?
And it is. [ 43 · 17 = 731 ]
So that's telling us that
if this [ 17 ] divides our given number, so will this [ 43 ]
So by finding one of these numbers
less than that approximate square root,
if I find such a number, by dividing by it,
the division process gives me a bigger number.
So the answer to our question at the beginning,
is there a bigger number than this
that might divide into our given number, and the answer is yes.
However, these lower numbers will pull it out for us.
So what we're saying is
if none of these numbers up to that approximate square root
will divide into this, then nothing else will either.
Hence it's a prime number.
But if one of the lower ones will,
then they will give us free, so to speak, one of the highers.
So we don't have to look for these,
these will give it to me in the division process.
Do you see that?
Because that relationship will help us see a process
that's very important to our math in a few more lessons.
So these three rules will make it quite easy to determine
whether a given number, even a fairly large one, is prime or not.
First, you find the approximate square root of the given number.
List all the primes up to that approximate square root.
And if you don't know the primes,
then simply list all the whole numbers.
Then simply try each of them
to see if any of them will divide into the given number evenly.
And if there is such a divisor, you have a composite number.
If there is no such divisor, this is prime.
Simple, isn't it?
It can be a fair amount of arithmetic, but the principle is simple.
While we're here,
let's take a peek ahead into a future lesson
where prime numbers in sequential order will be used very heavily.
Let's take the number 72.
That obviously is not prime
because I can see immediately that 2 will go into it.
Well, let's take the lowest prime number in our list,
which is 2, and actually divide it into 72.
And it would go 36 times.
Which is to say that 36 times 2 is equal to 72. [ 36 · 2 = 72 ]
That's how we checked it, isn't it?
But now, let's take that quotient 36 and ask:
is it also divisible by that current prime number 2?
And the answer is yes.
So 2 goes into 36, 18 times. [ 36 ÷ 2 = 18 ]
Which is to say that 18 times 2 is 36. [ 18 · 2 = 36 ]
Or if you want to, since 36 times 2 is 72, [ 36 · 2 = 72 ]
we could say that 18 times 2 times 2 is 72. [ 18 · 2 · 2 = 72 ]
Now, let's look at our topmost quotient and ask:
can I still divide it by yet another 2?
The answer is yes.
Now, what we're saying is
9 times 2 times 2 times 2 is 72. [ 9 · 2 · 2 · 2 = 72 ]
Okay? But now we ask of the topmost quotient:
can I divide this by 2?
And the answer is no.
So then let's jump to our next prime number and ask:
will it divide into this [ 9 ] number?
And the answer is yes.
And so on.
3 will still divide into that once.
So you begin to realize I can take a composite number,
in this case 72, start from the lowest prime,
and begin to divide by only prime numbers
until finally I will always arrive at 1.
And of course 1 times anything is itself.
So what we have now is that
3 times 3 times 2 times 2 times 2 times
times, that's it, [ 3 · 3 · 2 · 2 · 2 ] is equal to 72.
Let's say that.
But let's say it from bottom up now.
2 times 2 times 2 times 3 times 3 is 72 [ 2 · 2 · 2 · 3 · 3= 72 ]
Notice we have written 72 now as a product,
many products, of only prime numbers.
We will later call this way of writing any given number
the 'prime factorization' of that number.
'Factorization' meaning
I've written it as multiplication problems.
'Prime' meaning I've used only prime divisors.
This is so important, you'll see it
throughout this course, in algebra, in business math,
and in many, many courses in the future.
Generally instead of writing it this way though,
we'll write this 2 times 2 times 2 in exponent form [ 2³ ]
And this 3 times 3 in exponent form [ 3² ]
So this [ 2³ · 3² ] is the prime factorization of 72
written in exponent form. [ 2³ · 3² = 72 ]
Now, what that's going to allow us to do in
within a dozen lessons of where you are right now
is this kind of problem:
What is the lowest common denominator
of these three fractions? [ 3/4, 5/6, 1/3 ]
Do you recall that from your elementary school days?
We're asking what's the lowest number
that 4, 6, and 3 will each divide into?
And we can see that that's 24.
Now, we have a whole chapter coming after this
that's going to re-review this if you had forgotten this.
But I hope that you haven't.
Okay. Now, this is fairly easy.
We looked at the denominators,
we're comfortable enough with numbers
that we can just look at it,
perhaps do something in our head
that causes this realization to come out.
But what if we had asked, instead of these three fractions,
this: [ 5/56, 8/75, 1/114 ] these very messy denominators?
What's the lowest number that each of them will all divide into?
Well, it certainly has to be bigger than 114.
It may be a very long number.
But think as we will
it just doesn't come to us like this one will.
And most students in elementary school and high school
simply didn't do this kind of problem because they couldn't.
But what you're learning now about prime numbers
and being able to take a number
and write it in prime factored form
is going to allow us in the next chapter, as a matter of fact
to make this problem be fairly simple.
And it will all hinge from you being quite good
through this and the next few lessons at being given a number
and being able to answer the question
through this kind of a routine:
is it a prime number or is it a composite?
And that all boils down to these three simple procedural rules.
So use this lesson to practice this very heavily
until it's just routine to you.
If it is, then the next dozen or so lessons
will become fairly simple.
This is your math host, Bob Finnell.
We'll see you at the next lesson.