Prime and Composite Numbers

If you’re a mathematician or a student of mathematics, you know what prime and composite numbers are.  But if you’re someone who teaches mathematics, you’ll find the standard definition of prime and composite numbers are problematic.  In the following, we’ll take apart the standard definitions, and come up with a better one.

Here’s a common definition:  A prime number is a number that can only be divided by 1 and itself; all other numbers are composite.

At this point, we have to inject some fine print:

  • Actually, any number can be divided by any (non-zero) number:  5 can be divided by 3, since 5 \div 3 = \frac{5}{3}, so we have to specify that we are talking about whole number divisors.
  • Oh, and 1 isn’t prime, even though its only whole number divisors are 1 and itself.
  • Incidentally, 1 isn’t composite either.

Thus, we get the following standard definition:  Any number larger than 1 is prime if it has no whole divisors besides 1 and itself; the number is composite otherwise.

Now there’s nothing really wrong with the standard definition…if you’re a mathematician.  But in terms of doing anything with a prime number, it’s a good example of how our choice of definitions can make mathematics easier or harder.

There are two problem with the standard definition of prime.  First, to most non-mathematicians, divisors implies division, so to find if a number is prime, we see if any number divides it.  Thus if I want to find whether 5 is prime, I’ll check 5 \div 2, 5 \div 3, 5 \div 4, and since none of them work, I’ll conclude 5 is prime.  But this means that in order to verify whether a number is prime or composite, we must divide…and division is the hardest of the elementary operations.   As a result, this definition discourages verification!

There’s a second problem:  it defines a prime number by a property it doesn’t have. Determining whether something has a property is relatively easy; determining whether something doesn’t have a property is harder, and tends to produce answers like “It just doesn’t have that property.”

What do I mean by that?  I’ve asked questions like “Prove 5 is prime” on assignments, and more often than not, I get answers like “5 has no divisors, so it’s prime.”  While this is true, it misses the point of a prove question:  A politician can claim something is true without giving any supporting evidence, but a sensible person is supposed to do better.   Mere claims are meaningless:  you’ve got to present the supporting evidence.

So here’s an alternative definition:  A number is composite if it can be expressed as a product of smaller numbers.  A number greater than 1 is prime if it cannot be expressed as a product of smaller numbers.

Note several features of this definition:

  • We don’t have to specify we’re dealing with whole number products.  While it’s true that 5 can be expressed as a product of other numbers, none of these pairs involve smaller numbers.
  • This also makes clear from the beginning that 1 is not composite, because it can’t be written as a product of smaller numbers.
  • We avoid division and focus on the easier operation of multiplication.

What about “Prove 5 is prime?”  It’s still possible to respond with a simple assertion:  “No product of smaller numbers gives 5.”  However, because the focus of the definition is on the product, and not the property, it’s more likely to cause a respondent to recognize they must provide evidence.

More importantly, students sometime have difficulties trying to prove “5 has no divisors.” I suspect it’s because they see “No divisors” and the immediate response is “But the divisors could be anything at all, so where can I start?”  In contrast, “No product of smaller numbers gives 5” automatically limits the scope of the problem:  products of smaller numbers.

I’ve started using the above definition for prime and composite numbers in all the classes I teach.  I hope you’ll start to use it as well.

Advertisements

Why Do Proofs

Proof is an essential part of mathematics, but it’s sometimes not clear why we prove things in mathematics.  By way of example, let’s consider a simple problem:  Multiplying two even numbers.

If you were a scientist, you would collect data. For example:  4 \times 6 = 242 \times 8 = 1610 \times 10 = 100, and so on.  After a few hundred pieces of evidence, you would form an hypothesis:  The product of two even numbers is even.  You might then perform some more experiments to test the hypothesis:  82 \times 14 = 114814 \times 32 = 44811 \times 4 = 44 (then sheepishly realize that 11 isn’t even, so we’ll ignore that), 24 \times 4 = 95 (better recheck that…yup, it’s supposed to be 96), and so on.

But if you’re a mathematician, you’d next try to prove that the product of two even numbers is an even number.  The first thing to realize is this:  No one ever tries to prove anything they don’t already believe to be true.  If you asked me to prove the product of two even numbers is an odd number, I’d say “But that’s not true…why should I waste time trying to prove it?”  What this means is that we don’t prove things because we doubt their truth:  proof isn’t a way of obtaining truth, because in some sense, we already have it.

So why do we prove things?  Let’s consider what we’d have to do.

  • First, what do we mean by “the product of two even numbers?”  We need to clarify what we mean by an even number:  “I know it when I see it” isn’t good enough.  We come to the conclusion:  An even number is any number that can be written as the product of 2 and some other whole number m.
  • So now we multiply two even numbers:  (2m) \times (2n) = 4mn.
  • But we need to write this as a product of 2 and some other number, so we have 4mn = 2 (2mn).

There’s our proof.

But stop and smell the roses.  Halfway through, we found the product of two even numbers was 4mn.  This means that the product of two even numbers is in fact a multiple of 4.  If we go back to our data, we’ll see that it’s there…but it might not have been obvious at the time.

So what has this effort of proof given us?

  • We had to dig down deep and elaborate on what we man by “even number.”  In general, proof requires us to define our terms in a meaningful and useful way.
  • We had to use a little bit of algebra.  In general, proof requires us to review mathematics we’ve already learned.  (In fact, since most terms in mathematics have a standard definition, the first step also requires a review of the mathematics we’ve learned…or the mathematics we should have learned)
  • We discovered something that we might have missed the first time around.

How To Get Good At Math (In Ten Minutes a Day)

Some years ago, a Certain Toy Corporation got into quite a bit of trouble for marketing a (girl) doll that spoke phrases.  In particular, one phrase:  “Math is hard.”

I’ve always argued that that phrase isn’t objectionable.  Math is hard.  So is throwing a three-point shot in basketball, doing a triple gainer, bowling a perfect game, and changing out a car engine.  One of my favorite episodes of The Bernie Mac Show was when Bernie Mac made this very point:  yes, math is hard…but you do hard things all the time, so why not do math?  (Season 1, Episode 16, Mac 101)

So how do you get better at basketball?  You practice, practice, practice.  The same is true in math, and teachers often tell students this.  And while that’s all true, and certainly good advice, it occurs to me there are two components to being “good at math.”  The first is being good at doing math.  Maybe you’ve just learned how to solve a quadratic equation, and so solving x^{2} - 3x - 7 = 0 takes a little effort.  But after you’ve solved a few hundred quadratic equations, it becomes second nature, and you can throw down the solution (x = \frac{3 \pm \sqrt{37}}{2}) without hesitation.

But the other component of being “good at math,” and ultimately what it means to be a mathematician, is being good at creating math.  This is far more difficult.  It’s the difference between doing 30 push-ups a day, and inventing a new calisthenic.

So how do you do that?  Let’s consider two of the greatest mathematicians ever:  Gauss and Euler.  They actually talked about what it took to be a great mathematician, and the short form is this:  Never solve a problem one time.

For example, in 1736, Euler proved a result of Fermat, namely that if p is prime and a < p, then a^{p - 1} - 1 is divisible by  p.  Euler proved this, using an induction argument so obscure that it keeps being rediscovered by mathematicians, both great ones (Laplace and Cauchy) and obscure ones (me, actually…this may be the only time I’ve sat at the same table as Euler, Laplace, and Cauchy).

But Euler didn’t stop with one proof.  About every ten years,  he came up with a new way to prove the theorem.  His re-examination of the problem led him to discover the \varphi-function (where \varphi(n) is the number of numbers less than n which are relatively prime to n) and generalized it to what is now called the Euler-Fermat Theorem:  For any number N and any number a relatively prime to N, the least value x for which a^{x} -1 is divisible by N is a divisor of \varphi(N).

Incidentally, this result is the basis of modern computer security (the RSA algorithm).

What about Gauss?  In 1799, Gauss proved the Fundamental Theorem of Algebra,namely that a nth degree polynomial with real coefficients has n real and/or complex roots.

And then, over the course of his career, Gauss proved the Fundamental Theorem three more times, each time extending the result and developing new mathematics.

What’s the practical application?  Let’s consider something really basic:  multiplication of two numbers, say 47 \times 153.  We all know how to do this:  we were taught how to do this computation in school.  We can practice the multiplication algorithm by trying different products:  47 \times 153 today, 23 \times 17 tomorrow, 153 \times 301 the day after, and so on.  If you do this, you will develop your skills at applying the standard algorithm.

On the other hand, suppose that instead of doing new products the way you were taught, what if you tried to find the same product using a completely different method?  You know what the answer is supposed to be, so you’ll have a good way to check if your method works.

How might that work?  In this case, 47 \times 153 is the sum of forty-seven 153s.  So you could add 153 + 153 + 153 + \ldots + 153.  That’s one method of multiplying; one nice feature of it is that it’s something a first grader can do.  (Granted, you’d probably have them do something easier, like 5 \times 4 = 4 + 4 + 4 + 4 + 4, but the important thing is that they don’t have to know multiplication to be able to solve the problem “Find 5 \times 4“)

Obviously, you don’t want to spend the next half hour adding forty-seven 153s together…but progress comes when someone asks “Can we find a better approach?”  So you start thinking about how to improve the efficiency of your sums.   Maybe tomorrow, you realize 153 = 100 + 50 + 3, so adding together forty-seven 153s is the same as adding together forty-seven 100s, forty-seven 50s, and forty-seven 3s.

And even that gets a little tricky, so the day after, you come up with a new insight that allows you to make the addition even more efficient.

A Mathematical Litmus Test: The Handshake Problem.

Broadly speaking, mathematics can be separated into two very broad categories:  algebra and analysis.  Mathematicians likewise fall into these categories.

Which type of person are you?  One possible litmus test concerns the handshake problem, which I was introduced to as an undergraduate.  The handshake problem is the following:

Every person in the world has a handshake number, which is the number of times they’ve shaken hands with someone else.  This handshake number is either odd or even.  Is the number of people with an odd handshake number even or odd?

I’ll let you think about the answer for awhile.

 

Order of Operations

So if you’re on social media, you will sooner or later get exposed to one of those math questions tagged with “What’s the answer:  9 out of 10 people get this one wrong!!!!!”

Many of these deal with mathematical problems:  8 \div 4 \times 2 - 1, for example.  Before talking about this, here’s an important insight:

Order of operations is like driving on the left side of the road:  it’s a convention, decided by society, and there’s no right or wrong as long as everyone agrees on it.  

In fact, the existence of a standard order of operations is because there was no general agreement, so you couldn’t be sure how to answer a question like 8 \div 4 \times 2 - 1.  It was only during the twentieth century that order of operations became standardized.

So what’s the standard?  The basic rule of order of operations is this:  All operations are to be performed from left to right unless

It’s the unless that makes it complicated:

  • Expressions inside grouping symbols (parentheses usually, but there are implied grouping symbols; I’ll return to this topic later) go first.
  • Multiplication and division are equiprecedent:  they’re dealt with, left to right, at the same time.
  • Addition and subtraction are equiprecedent:  they’re also dealt with, left to right, at the same time.

Those who remember PEMDAS may think I’ve omitted something.  But read on…

Let’s take a look at that 8 \div 4 \times 2 - 1.  We have a division and a multiplication, which are equiprecedent, so we proceed from left to right:

  • We find 8 \div 4 = 2,
  • Next we find 2 \times 2 = 4,
  • Finally we find 4 - 1 = 3.

Now many of us learned PEMDAS:  parentheses, exponents, multiplication and division, addition and subtraction.  One problem with this nifty little mnemonic is that it makes it appear that multiplication should be done before division, and addition before subtraction.  But again, multiplication and division are equiprecedent:  they’re done at the same time, left to right; likewise addition and subtraction.

What about exponents?  This one’s a little tricky, but it comes down to this:  Exponentiation isn’t an operation:  it’s shorthand.  In particular, when you write 2^{3}, you are not actually performing an arithmetic operation; you’re using mathematical shorthand:  2^{3} = 2 \times 2 \times 2.

So consider:  3 \times 2^{3} \div 4.  You don’t do exponents first.  You do recognize that 2^{3} = 2 \times 2 \times 2, so this problem is really 3 \times 2 \times 2 \times 2 \div 4.  Now you can do the multiplication and division from left to right to get the final answer:  6.

What’s the logo?

abul_heptagon_small

The main logo for the site is shown above, and it’s my current personal favorite geometric construction.  This comes from Abu’l Wafa, a 10th century Persian geometer, and gives a quick-and-easy method of constructing a nearly regular heptagon:

  • Let ABC be an equilateral triangle inscribed in a circle.
  • Bisect BC at D.
  • CD is very nearly the side of a regular heptagon inscribed in the circle.

How close is it?  The green shows what happens when you mark six sides, equal in length to CD, with the seventh side joining the last vertex to your starting point.  The blue is a regular heptagon.  They’re almost indistinguishable.  (The inset shows that the true regular heptagon does deviate very slightly from the approximate regular heptagon)

I actually used this a few years ago, to set up a seven-sided tomato cage.  I’ll leave the details as an exercise for the reader…

Post 0

Welcome to the site!

I brew beer, throw axes, make bobbin lace, tell tales from classical mythology, and engage in card weaving, but on paper, I’m a mathematician who teaches at Brooklyn College, part of the CUNY system.  I’ve been teaching for mumblety-seven years, I’m a survivor of the Great Calculus War (and even fought a few battles), and recently discovered this thing called the internet…

A little while ago, I learned that WordPress supports \LaTeX.  If you don’t know what \LaTeX is, don’t worry…suffice it to say that it’s a way you can typeset mathematical formulas like \sqrt{8} or \frac{1}{3} or even \frac{d}{dx} \left(\sqrt[3]{x^{3} + 5x + 8}\right).   This means that it’s actually possible to do a real math blog, without having to use ASCII graphics or clever HTML hacks or inline GIFs.

So let’s try this and see where it goes.