The Infinity of Primes

Last week, I was teaching my class about the prime numbers – the positive integers greater than $1$ that are divisible only by $1$ and themselves. For example, $3$ is prime because it has no whole number factors other than $1$ and $3$. The whole number $6$, however, is composite – not prime. Why is $6$ not prime? Because $6$ is divisible by both $2$ and $3$, neither of which is $1$ or $6$.

It can be shown that $3$ has no whole number factors other than $1$ and $3$ by dividing it by every whole number less than $3$, except $1$. We do not need to check that $3$ is divisible by itself or $1$ because every whole number is divisible by itself and $1$.

The only number less than $3$ that is not $1$ is $2$. So, let me divide $3$ by $2$. Well, $\frac{3}{2} = 1 r 1$, where $r 1$ denotes a remainder of $1$. If a quotient has a remainder other than $0$, or some other factor of the dividend then the divisor does not divide the dividend. Thus, $2$ does not divide $3$ and is not a factor of $3$. Then, because any factor of $3$ must be less than $3$, and no number less than $3$ is a factor of $3$, $3$ is prime.

I choose to write quotients, such as $\frac{m}{n}$, in which $n$ does not divide $m$, as a result with remainder because that is how divisibility is defined.

An Important Note

We define $1$ to be neither prime nor composite (if a number other than $1$ isn’t prime, it’s composite) even though it has only $1$ and itself  as factors. We do so because we need $1$ to be non-prime. Were $1$ prime, the absolutely vital Uniqueness of Prime Factors Theorem which states that every positive integer greater than $1$ can be written as the product of a unique set of prime numbers would fail. Why? Consider the prime factorization of $8$. $8 = 2 \times 2 \times 2$. However, suppose we allow $1$ to be defined as prime. Then

$$8 = 2 \times 2 \times 2 \times 1$$

and,

$$8 = 2 \times 2 \times 2 \times 1 \times 1$$

and,

$$8 = 2 \times 2 \times 2 \times 1 \times 1 \times 1$$

And so on, ad infinitum. This would contradict the Uniqueness of Prime Factors Theorem. We solve this conundrum by simply defining $1$ to be neither prime nor composite. (We designate $1$ a unit of the whole numbers.)

Many, if not most, people not formally trained in mathematics believe that mathematics is cut-and-dried – there is one, and only one, way to work a math problem; one, and only one, set of mathematical facts – and they are fixed, and that every civilization anywhere in the universe that creates mathematics must ultimately create the exact same mathematics. Nothing could be farther from the truth. It is not at all unusual for the community of mathematicians to simply redefine some mathematical concept in order to force some theoretical outcome. The redefinition of $1$ as a unit rather than a prime is but one such example.

As the lesson hook in my lesson on prime numbers,  I asked the class whether there is a finite number of prime numbers, an infinite number of prime numbers, or if it were impossible to determine whether there are finite or an infinite number of primes.

As I have come to expect, my class eventually agreed that it is impossible to know whether there are a finite or an infinite number of primes. Their reasoning was along the lines of, “since there is an infinite number of whole numbers, we can never check them all to see how many are prime.” This is actually, for students the ages of mine, not a bad guess. It is not, however, a solution arrived at by any deductive logical argument, which is what we want students to use to come to a valid conclusion. It also has the disadvantage of being false.

There are an infinite number of primes, and it can be proven that there are. One of the proofs, a classic, is detailed below.

The Infinity of the Primes Theorem and a Proof

Claim:

The set of primes is infinite.

Explanation of the method of proof:

Let’s consider some set of successive prime numbers, beginning with the number $2$. Their product plus $1$ is necessarily prime. Why? An explanation follows.

This shall be a proof by contradiction. Some statement is assumed to be true, and via a series of logical statements, the assumption is contradicted (contra – against, diction – to speak.) Thus, the original assumption is false and its negation is true.

Suppose $2$ is the only prime number. This would imply that every successive number is a multiple of $2$. However, $2 + 1$ cannot be a multiple of $2$ because $\frac{2 + 1}{2} = 1 r 1$. That is, $(2 + 1)$, when divided by $2$ does not have a remainder of $0$, it has a remainder of $1$. (This is the definition of even and odd numbers, by the way.)

Perhaps $2 + 1$ is a multiple of some other prime number. What could that number possibly be? First, we have claimed that $2$ is the only prime number. Second, any prime number other than $2$ that divided $2 + 1$ would necessarily be less than $3 = 2 + 1$. But, $3$ is the next whole number after $2$. There is, then no number other than $2$ that is also less than $3$ and a factor of $3$. Hence, $3$ must be prime. I understand perfectly that the argument in this paragraph is difficult for some readers to follow. It is important that it is understood. The remainder of the argument follows the same logic. Take the time to re-read it until you understand the argument.

Here it is in simplified form. We claim $2$ is prime and that it is the only number that is. (In fact, since it is the least number that could possibly be prime, it must be prime.) Then, we examine the next number, $2 + 1$. This is the number $3$. Because it differs from $2$ by $1$ rather than some multiple of $2$, it cannot be a multiple of $2$. There is, in fact, no number between $2$ and $3$ that could divide $3$. Hence, $3$ has no divisors other than $1$ and itself. It is, therefore prime.

So, maybe $2$ and $3$ are the only primes. Consider $(2 \times 3) + 1$. Were $(2 \times 3) + 1$ not prime, it would necessarily be divisible by some prime number other than $1$ and itself, i.e., $2$ or $3$ or both. But, if we divide $(2 \times 3) + 1$ by either $2$ or $3$, we have a remainder of $1$.

$$\frac{(2 \times 3) + 1}{2} = 3 r 1$$

and

$$\frac{(2 \times 3) + 1}{3} = 2 r 1$$.

Thus, since $(2 \times 3) + 1 = 7$ Could it be that $7$ is prime?

Why? None of the other (supposedly) exhaustive set of prime numbers (here $2$ and $3$) could possibly divide $7$. In both cases, there is a remainder of $1$.

This does not imply that $7$ is the next prime number (after $3$.) We must check the numbers between $3$ and $7$ for primness. Dividing each of these numbers by $2$ and $3$, we find that $5$ is the only one not divisible by either. Thus, $5$ is prime.

Thus, we know that $2, 3, 5$, and $7$ are successive primes. Let us assume they are the only primes. If we examine the number $(2 \times 3 \times 5 \times 7) + 1$, we see that dividing this number by any of $2, 3, 5$, or $7$ – presumably the only primes – yields in each case a remainder of $1$. That is, $(2 \times 3 \times 5 \times 7) + 1$ is not a multiple of any prime. Thus, it is prime.

This scheme can be abstracted in the following way; suppose the following $n$ numbers

$$p(1), p(2), p(3), …, p(n)$$

are $n$ successive prime numbers, and that they are all of the prime numbers, i.e., there are no other prime numbers. (If this is the case, then there is a finite number of primes. If we can show that this assumption leads to a contradiction because $n$ can be any whole number I chose, there is not a finite number of primes – the set of primes is infinite.)

Assumption:

The set of primes is finite, and consists only of the prime numbers

$$p(1), p(2), p(3), \ldots p(n)$$

where n is any whole number greater than $1$.

Proof of the Theorem:

Consider the value of

$$[p(1) \times p(2) \times p(3) \times \ldots \times p(n)] + 1$$

Dividing this value by any of the n numbers we have assumed to be the complete set of primes, we get a remainder of $1$. In other words, the value

$$[p(1) \times p(2) \times p(3) \times \ldots \times p(n)] + 1$$

is not divisible by any of the numbers $p(1), p(2), p(3), \ldots p(n)$ we have presumed to be all of the primes. Thus,

$$[p(1) \times p(2) \times p(3) \times \ldots \times p(n)] + 1$$

is also prime.

This shows that the statement the primes are finite is false. Hence, the negation of the statement is true – the primes are infinite is true.

q.e.d. <– This is what Mathematicians write to say, “I’m done, now.” It comes from Latin and means:

 Quod Erat Demonstrandum,

or, the thing is shown (demonstrated).

Euro (nee Mark)

The Skip-Counting Heuristic for Teaching the Multiplication Facts

Having spent a year as a Mathematics Response to Intervention Teacher  in a low-performing school, I can attest to the difficulty many elementary school students experience when learning, or attempting to learn, the basic multiplication facts. This difficulty arises usually arises from one common, but ineffective, practice – rote memorization.

An argument I have often heard made by elementary school teachers who employ rote memorization in their classroom is, “learning the multiplication facts is like getting better at sports, practice makes perfect.” I introduce these teachers to Vince Lombardi, the legendary football-coach and wordsmith. Vince Lombardi famously said, “Practice doesn’t make perfect, perfect practice makes perfect.”

Rote memorization of the basic multiplication facts is practice. But, it is necessarily imperfect practice. Imagine a student sitting across from a teacher or parent equipped with a set of multiplication flash cards. The student’s interlocutor presents to the student a card which reads 6 x 7. The student’s job is to somehow find the product of 6 and 7 in her mind and produce it. The product of 6 and 7 is quite likely nowhere to be found in the poor student’s mind. Otherwise, the adult would not be asking the student to produce the product. The student is reduced to guessing the correct product.

Suppose, however, the student had some method of finding the product of 6 and 7 even though that fact was not part of her memory – some method of finding the product reliably, every time she was asked to find it.  Each time the student found the product 42, the fact that 6 x 7 = 42 would be reinforced in her mind. Eventually, the fact 6 x 7 = 42 would become part of the student’s memory, and the student will have learned this multiplication fact.

The method I used as an RTI Teacher relied on ‘skip-counting’ – beginning with some whole number, state that number and then every multiple of that number. For example, skip-counting by 3 looks like;

3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, …

Then, the product of 3 and 7, 3 x 7, is found by skip-counting by three until the 7th multiple of 3;

3, 6, 9, 12, 15, 18, 21

Each time the student voices a multiple of 3, she counts the multiple. I preferred to teach my students to keep count by pressing a finger onto their desk with each multiple counted. I call this the student’s ‘bookkeeping’ method.

Some of the skip-count patterns are more easily learned than others, and when teaching this strategy to my students, I employed skip-count patterns for 2, 3, 5, and 10. Once a student masters the 2 skip-count pattern, and then the 3 skip-count pattern, I would teach the ‘double skip-count’ heuristic.

The 2, 5, and 10 skip-count patterns come quite naturally to most elementary school age students. It is necessary, however, to teach the 2 skip-count pattern to 40 rather than 20 (20 = 2 x 10). This facilitates using the 2 skip-count pattern to effect the 4 skip-count pattern.

The 4 skip-count pattern is nothing more than the 2 skip-count pattern with each second multiple voiced. It look like;

2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40

Those multiples that are in bold-face above are the multiples of 4. They are every second multiple of 2. It is quite easy to teach a student to employ their skip-count bookkeeping method with each second multiple of 2 rather than each multiple of 2.

The 6 skip-count pattern is the 3 double skip-count pattern, similar to the relationship between 2 and 4 skip-count patterns. It is employed in a manner analogous to the 4 skip-count pattern, but using the 3 skip-count pattern as the underlying pattern. Just as it is necessary to teach the 2 skip-count pattern to 40 rather than 20, it is necessary to teach the 3 skip-count pattern to 60 rather than 30. (6 x 10 = 60)

In my teaching practice, I teach the 2, 3, 4, 5, 6, and 10 skip-count patterns. (In fact, many students master the 2, 5, and 10 skip-count patterns with very little instruction, and the 4 skip-count pattern with only slightly more instruction.) The 3, and consequently the 6, skip-count pattern often takes quite a bit of effort on the part of students to master.

While there are certainly skip-count patterns for 6, 7, and 9, their difficulty to master make them less than useful. For the 9 times facts, I employ a different heuristic (the topic of a later post), and I do not teach any method for finding the 6 and 7 times facts. It is unnecessary.

Multiplication of the whole numbers is commutative. That is, for any whole numbers n and m, n x m = m x n. It makes no difference in which order the factors n and m are written. The consequence of this property of multiplication of the whole numbers is that any time 7 or 8 are exactly one of the factors of a multiplication fact, the fact can be commuted, leaving as the result the possibility of employing some skip-count pattern to find the product. (This does not apply to 7 x 9, or 8 x 9.) Then, only the products 7 x 7, and 7 x 8, 8 x 7 have no heuristic to assist in finding the product. Essentially, a student need only ‘memorize’ two multiplication facts in order to master the basic multiplication facts from 0 x 0 to 10 x 10.

Euro (nee Mark)

Mathematics – Queen of the Sciences

I try to keep the fact that I am a mathematician under wraps. It doesn’t really impress many people, and I wind up having to answer the question, “Why?” Answering, “because Mathematics is the Queen of the Sciences” doesn’t quite mean what it did when Carl Freidrich Gauss first called it that so I refrain from saying it out loud. Sometimes, when I do give that answer, the conversation can get a bit dicey.

Most of the times, these days, I don’t even attempt an answer. If I say, for example, “because it’s so elegant”, which it certainly is, I’m likely to get funny looks. I usually just shrug my shoulders and grunt something unintelligible.

I’m not going to attempt to answer the question, “Why?”, directly in this blog, but by reading it, I hope you come away with the same appreciation that I have for the ‘Queen of the Sciences’.

Euro (nee Mark)

What is “I Got Scammed on the Internet” all about?

I don’t really remember how this got started, but for some time now I have been running down internet scammers and writing about their scams. I find it exhilarating to draw a scammer into my web while the scammer thinks he, or she, is drawing me into his, or hers. The final move in this game is to reveal to the scammer that they’ve been had. Their reactions are as varied as the scams, but every one of them is priceless.

It will likely take me quite a while to get all of my already-written articles posted, and in the meantime, I will be looking for new scams to expose.

Currently, I am working on a possible book project about internet scams. The manuscript title is “I Got Scammed on Craigslist”. When/if it is published, I will let the world know right here.

Euro (nee Mark)