# Aerospace Micro-Lesson #74

## Prime Numbers

Prime numbers, which have no factors besides themselves and one, have long been curiosities in mathematics. In ancient times, Eratosthenes figured out a way to find them and Euclid proved that there are infinitely many of them. In recent decades, they have moved from being mathematicians’ toys to having serious applications in the making of unbreakable codes.

Next Generation Science Standards (NGSS):

• Disciplinary: Engineering, Technology, and Applications of Science
• Crosscutting Concept: Patterns
• Science & Engineering Practice: Constructing Explanations and Designing Solutions

Common Core State Standards (CCSS): Math:

• Standard for Mathematical Practice: Reason abstractly and quantitatively.

CCSS.MATH.CONTENT.2.OA.C.3
Determine whether a group of objects (up to 20) has an odd or even number of members, e.g., by pairing objects or counting them by 2s; write an equation to express an even number as a sum of two equal addends.

It will be difficult to introduce the concept of prime numbers to children who have not yet learned multiplication. One possibility, if you should want to try, is to point out that some numbers of things can be arranged into rectangles and not have any of them left over.  For example, six chips can be arranged into a rectangle of two by three and fifteen chips can be arranged into a rectangle of three by five. Some numbers can be arranged into rectangles in more than one way; for example, twelve chips can be arranged into rectangles of two by six and three by four. Other numbers cannot be arranged into rectangles at all; these last numbers are called “prime numbers.” This might be a fun activity to try with Skittles or Goldfish crackers to manipulate into the rectangles (and then eat, of course). The class could create a chart listing the prime numbers that are discovered during the activity.

CCSS.MATH.CONTENT.4.OA.B.4
Find all factor pairs for a whole number in the range 1-100. Recognize that a whole number is a multiple of each of its factors. Determine whether a given whole number in the range 1-100 is a multiple of a given one-digit number. Determine whether a given whole number in the range 1-100 is prime or composite.

The rectangles mentioned in the K-2 lesson are similar to the arrays used by students working with multiplication and division. If a number is a prime, the only array possible is made of 1 row, because there is no other way to arrange the array into two or more rows of equal length.  Have students experiment with creating arrays to show different ways to arrange the desks in the classroom, the number of students in the class, or to represent their age.  Which arrays can be laid out in more than one row? Which cannot be made into multiple rows of equal length and must be an array of a single row?

Once students have memorized their multiplication facts, have them explore the use of division to identify prime numbers. First, they could eliminate all the numbers divisible by 2, then by 3, 4, and on up. What is the largest prime number they can discover?

Another option to explore is to have students search for numbers that are the sum of two prime numbers - and the sum is also a prime. For example, 2 + 3 = 5 and all three are prime numbers, but 3 + 5 = 8 and 8 is not a prime. What are the two primes with the highest values they can find that will create a prime number sum?

CCSS.MATH.CONTENT.7.NS.A.3
Solve real-world and mathematical problems involving the four operations with rational numbers.

How many prime numbers are there? The ancient Greek mathematician Euclid proved that there are infinitely many of them, that there is no “largest prime” above which all numbers can be factored into other numbers. (His proof is rather elementary:  assume that there is a largest prime number, multiply all the prime numbers together, and add one to the product. The resulting number cannot be divided by any of the prime numbers because it will leave a remainder of one, so it must be prime itself. This contradiction means that the original assumption is false.)

On the other hand, it looks like there are far fewer prime numbers than there are counting numbers.  Half the numbers are divisible by two; a third of the remaining numbers are divisible by three.  As the numbers increase, there are more and more prime numbers which can be their factors. As one considers more and more numbers, the fraction which are prime continues to drop.

This is a paradox: there appear to be far fewer prime numbers than there are counting numbers, but there are infinitely many of both of them. In fact, in spite of the appearance of there being many more counting numbers than prime numbers, there are just as many of one as there are of the other. The “acid test” for there being as many of one as of the other is being able to make a one-to-one correspondence between the two sets of numbers: for each prime number there is a counting number and for each counting number there is a prime number. If you make a list of prime numbers in ascending order, you can find the position of any prime number on that list. The first number on the list is two, the second number is three, the third number is five, the fourth number is seven, the tenth number is 29, and so on. This proves that there are just as many prime numbers as there are counting numbers. You may want to give the students a little time to try to wrap their minds around that. If they can’t, don’t worry; this is what makes it a paradox.

CCSS.MATH.CONTENT.HSA.APR.B.3
Identify zeros of polynomials when suitable factorizations are available, and use the zeros to construct a rough graph of the function defined by the polynomial.

When one works with prime and composite numbers, one usually thinks only of positive numbers, but the concept can be extended to negative numbers. Rather than a prime number being a single number like five and being only divisible by itself and one, we must think of “families” of numbers, where +5 and –5 belong to a single family and +6 and –6 belong to another family. We must also include –1 with +1 as being neither prime nor composite; your writer’s term for these numbers is “generators.” (Please note that the terms “families” and “generators” are your writer’s own; there may be official terms that real mathematicians use.)  A prime number is only divisible by numbers in its family and by generators; thus +5 is divisible only by itself, –5, +1, and –1.

If one considers complex numbers—numbers of the form “A + B i”, where “i × i = –1,” one finds an extension of prime numbers to “Gaussian primes.” A Gaussian prime is a complex number with integer parts (meaning that “A” and “B” in the expression “A + B i” are both whole numbers) which is not the product of any other two complex numbers with integer parts.  In this extension, our “generators” become +1, +i, –1, and –i.  Each “family” of numbers now contains four members.  Thus, for example, “1 + 2 i” is a Gaussian prime but “3 + 4 i” is not because “3 + 4 i = ( 2 + i ) × ( 2 + i ).”  More strikingly, the regular prime numbers 2 and 13 are not Gaussian primes because “2 = ( 1 + i ) × ( 1 – i )” and “13 = ( 3 + 2 i ) × ( 3 – 2 i ).” Alternatively, one can say that “13 = ( 2 + 3 i ) × ( 2 – 3 i ).”  One may ask whether this violates the Prime Factorization Theorem, but it does not; the complex numbers “3 + 2 i” and “2 – 3 i” belong to the same “family” of numbers because “3 + 2 i = i × ( 2 – 3 i ).”  Similarly, “2 + 3 i = i × ( 3 – 2 i ).”

Another direction which one can go with prime numbers is Fermat’s Little Theorem (not to be confused with Fermat’s Last Theorem). Fermat’s Little Theorem states that if a number “P” is prime, then for any counting number “a” (less than “P”) the equation “aP mod P = a.” One can prove Fermat’s Little Theorem rather easily using mathematical induction and the Binomial Theorem. One should be careful as to what Fermat’s Little Theorem proves and does not prove. It does not prove that a number is prime; it can, however, prove that a number is composite (that it has factors other than itself and one).  For example, if one selects “P = 7” and “a = 3”, one gets “37 mod 7 = 2187 mod 7 = 3.” On the other hand, if one selects “P = 9” and “a = 2,” one gets “29 mod 9 = 512 mod 9 = 8.” Because our formula did not give “9” as a result, we have proven that nine is a composite number.  (A composite number for which the formula holds is called a “pseudoprime.”)

There is an interesting wrinkle with Fermat’s Little Theorem. If one writes down a 100-digit number and puts it through the formula (which is a fairly straightforward, if cumbersome, process if one expresses it as a binary number), one can prove using Fermat’s Little Theorem with “a = 2” that it is a composite number. The theorem, however, does not give the slightest hint as to what its factors are.

Sixty Years Ago in the Space Race: