• Theorem: the prime factorization of a natural number is unique (just stated, not proved) - this is also called the Fundamental Theorem of Arithmetic
• The division algorithm (we used to prove the missing step of the proof that there is no largest prime number): see below
• Proving that there is no largest prime number, that is, that the number of prime numbers is infinite.
Special case: (remainder 0) n is divisible by m if and only if n = mq for some natural number q.
The division algorithm: (which is not really an algorithm at all)
If n and m are any natural numbers, then
n = m•q + r
where q (for quotient) and r (for remainder) are natural numbers or 0, and r is less than m.
Comment: you already know this fact, you just may not have seen it written in algebraic language before. It is how we check a division problem when dividing with remainder.
Examples showing what the division algorithms says: in all of these divisions, we have to forget about decimals and even fractions, and just divide natural numbers with remainders left over.
Example 1: Let n=23 and m=5. If we divide 23 by 5, 5 goes into 23 4 times and there is a remainder of 3. So the quotient here is q=4 and the remainder is r=3, and the division algorithm says
23 = 5•4 + 3
Which is true.
Example 2: Let n=35 and m=5. If we divide 35 by 5, 5 goes into 35 7 times with remainder 0. So the division algorithm here says that
35 = 5•7 + 0
Which is also true.
Example 3: Let n=3 and m=5. If we try to divide 3 by 5 (remember, without using decimals or fractions) we see that 5 does not "go into" 3, that is, 5 goes into 3 0 times, and the remainder is 3. So the division algorithm here says that
3 = 5•0 + 3
Which is also true.
The last two examples show why we need to allow q and r to be 0 if necessary. Also, the remainder r is not allowed to be greater than m-1, in other words if we are dividing by 5 (as in the examples above) then the remainder must be 4 or less.
(We will use this later when proving that the square root of 2 is irrational, for example.)
How the division algorithm is used in the proof that there is no largest prime number: an example
We form the number N = 2•3•5•7•11•13•17•19 + 1
We can then observe that N has remainder 1 when divided by 2, by comparing to the division algorithm:
N = 2•(3•5•7•11•13•17•19) + 1, so in the division algorithm the quotient q is the quantity in parentheses, and the remainder r is 1.
Similarly N has remainder 1 when divided by 3, because we can rearrange the factors:
N = 3•(2•5•7•11•13•17•19) + 1
And similarly N has remainder 1 when divided by 5, because we can rearrange the factors:
N = 5•(2•3•7•11•13•17•19) + 1
And so on with the other prime numbers 7 through 19. Each one gives remainder 1 when we divide by it.
• Modular arithmetic (introduction and terminology/notation)
Activity to start with: operations on even/odd numbers
• Modular arithmetic: some vocabulary and notation (from the Art of Problem Solving reading, as well):
modulus: the number we are "dividing out"
residue: the remainder when dividing by the modulus
notation: a ≡ b (mod m)
read it as: "a is congruent to b mod m"
it means: a-b is divisible by m, or equivalently, that a and b have the same remainder when divided by m
In case b is a residue mod m, a ≡ b (mod m) means that b is the remainder when a is divided by m.
Getting used to this language/notation:
So in the example of "clock arithmetic", the modulus is 12, the possible residues are the integers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11; and we can say for example that 98 ≡ 2 (mod 12) because 2 is the remainder we get when we divide 98 by 12.
Homework:
• Journal assignment: Write out the proof that there is no largest prime number, including an explanation for how you know that N is larger than p, and how you know that N is not divisible by any of the primes 2 through p.
Problems:
1) State the division algorithm for each of the following cases:
a) n=31, m=4 (that is, dividing 31 by 4)
b) n=60, m=3 (that is, dividing 60 by 3)
c) n=7, m=11 (that is, dividing 7 by 11)
Next topic: more on Modular arithmetic (reading from The Art of Problem Solving) and connecting it to the odd/even activity.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.