Engaging students: Finding prime factorizations

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Brendan Gunnoe. His topic, from Pre-Algebra: finding prime factorizations.

green line

How can prime factorization be used in curriculum?

The teacher starts the class by asking students how they would find the least common multiple and greatest common divisor for two numbers. For the LCM, the most basic answer is listing the multiples of both denominators until they share a common multiple. For GCD, the most basic answer is listing out the factors of both numerator and denominator and finding the largest one in common.

Both processes can be made faster when using prime factorization, especially for larger numbers. First, do the process of prime factorization for both numbers. Then, for each prime, take the highest power on the lists and multiply everything together.

For example, take 12 and 45.

12 = 2^2 \times 3^1

45 =3^2 \times 5^1

\lcm(12,45) = 2^2 \times 3^2 \times 5^1 = 180

The process for finding the GCF is similar. Start off by doing the prime factorization for both numbers. Then, for each shared prime factor, take the smallest power and multiply everything together.

For example, take 12 and 30.

12 = 2^2 \times 3^1

30 =2^1 \times 3^1 \times 5^1

\gcd(12,45) = 2^1 \times 3^1 = 6

This process generalizes very easily for any amount of input numbers.

GCF and LCM are incredibly important when working with fractions and are used when reducing and adding fractions. Because fractions have loads of misconceptions associated with them, giving students another way to understand fractions can be very beneficial.

green line

Technology

Have you ever wondered why we use 60 seconds in a minute and 60 minutes in an hour? Or why there is 24 hours in a day? What about why there is 360 degrees in a circle? One explanation is because these numbers can be divided evenly by loads of smaller numbers that we use often. In other words, these numbers have lots of factors in them. These kinds of numbers are called highly composite numbers.

A great video showcasing highly composite numbers is Numberphile’s video “5040 and other Anti-Prime Numbers,” hosted by Dr. James Grimes. This video is extremely dense with informative as Dr. Grimes explains what a highly composite number is, shows properties of these numbers, explains why they have these properties, and gives examples of how highly composite numbers are used both in math and in real life. Dr. Grimes also gives a few historical uses of highly composite numbers, which answer some of the questions listed above.

Prime factorization is the foundation of highly composite numbers. Highly composite numbers can be an interesting and exciting application of prime factorization.

green line

Application

Semiprime numbers were also used in the making of the Arecibo message. Because the message is composed of 1679 bits, there is only four ways of decomposing the message into a rectangle. All possible decompositions of 1679 into a rectangle are 1×1679, 73×23, 23×73 and 1679×1. If decoded correctly, then the message forms a picture which contains loads of information about the solar system and life on Earth.

For a way to make semiprime numbers into an engaging activity for students, the teacher could have students create their own mini version of the Arecibo message and show them off in class. Students can be made into groups and each group get assigned a certain semiprime. Then, each group gets to decide what information goes in their mini message and draw their message onto a sheet of poster paper with a grid on it. Finally, they present their message to the class, representing the students sending their message off into space for extraterrestrial life to decode.

References:

https://topdrawer.aamt.edu.au/Fractions/Misunderstandings

https://www.youtube.com/watch?v=2JM2oImb9Qg

https://en.wikipedia.org/wiki/Semiprime

https://en.wikipedia.org/wiki/Arecibo_message

Factorization of 2021

Is 8,675,309 prime?

This semester, to remind today’s college students of the greatness of the 1980s: I made my class answer the following question on an exam:

Jenny wants to find out if 8,675,309 is prime. In a few sentences, describe an efficient procedure she could use to answer this question.

Amazingly, it turns out that 8,675,309 is a prime number, though I seriously doubt that Tommy Tutone had this fact in mind when he wrote the classic 80s song. To my great disappointment, nobody noticed (or at least admitted to noticing) the cultural significance of this number on the exam.

Naturally, I didn’t expect my students to actually determine this on a timed exam, and I put the following elaboration on the exam:

Although Jenny has a calculator, answering this question would take more than 80 minutes. So don’t try to find out if it’s prime or not! Instead, describe a procedure for answering the question and provide enough details so that Jenny could follow your directions. Since Jenny will need a lot of time, your procedure should be efficient, or as quick as possible (even if it takes hours).

Your answer should include directions for making a certain large list of prime numbers. Be sure to describe the boundaries of this list and how this list can be made efficiently. Hint: We described an algorithm for making such lists of prime numbers in class. (Again, do not actually construct this list.)

I thought it was reasonable to expect them to describe a process for making this determination on a timed exam.  Cultural allusions aside, I thought this was a good way of checking that they conceptually understood certain facts about prime numbers that we had discussed in class:

  • First, to check if 8,675,309 is prime, it suffices to check if any of positive prime numbers less than or equal to \sqrt{8,675,309} \approx 2,945.387\dots are factors of 8,675,309.
  • To make this list of prime numbers, the sieve of Eratosthenes can be employed. Notice that \sqrt{2,945} \approx 54.271\dots, and the largest prime number less than this number is 53. Therefore, to make this list of prime numbers, one could write down the numbers between 2 and 2,945 and then eliminate the nontrivial multiples of the prime numbers 2, 3, 5, 7, 11, \dots 53.
  • If none of the resulting prime numbers are factors of 8,675,309, then we can conclude that 8,675,309 is prime.

I was happy that most of my class got this answer either entirely correct or mostly correct… and I was also glad that nobody suggested the efficient one-sentence procedure “Google Is 8,675,309 prime?.”

211

Set a digital clock to display in 24-hour (military) time. Each day, it will show you 211 prime numbers starting with 00:02 (2 minutes after midnight) and ending with 23:57 (3 minutes before the next midnight.)

Oh, and 211 is also prime, so 02:11 would be one of the 211 prime times you observe each day.

No automatic alt text available.

Source: https://www.facebook.com/PointlessMathFact/photos/a.959625970716963.1073741828.958620490817511/1427111183968437/?type=3&theater

24601

Source: https://www.facebook.com/MathWithBadDrawings/photos/a.822582787758549/1999420776741405/?type=3&theater

Repunit prime

In the United States, today is abbreviated 10/31. Define the nth repunit number as

R_n = \frac{10^n-1}{9} = 1111\dots1,

a base-10 number consisting of n consecutive 1s. For example,

R_1 = 1

R_2 = 11

R_3 = 111

R_4 = 1,111,

and so on.

It turns out that R_{1031} is the largest known prime repunit number.

Source: http://mathworld.wolfram.com/Repunit.html

Engaging students: Finding prime factorizations

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Brittnee Lein. Her topic, from Pre-Algebra: finding prime factorizations.

green line

• How has this topic appeared in the news?

Prime factorization is key to protecting many aspects of modern convenience. The Fundamental Theorem of Arithmetic states that every number can be broken down into a sum of two prime numbers. For relatively small numbers, this is no big deal; but for very large numbers, not even computers can easily break these down. Many online security systems rely on this principle. For example, if you shop online and enter your credit card information, websites protect that information from hackers through a process of encryption.

Something for students to think about in the classroom: Can you come up with any formula to break down numbers into their prime factors?

Answer: No! That’s why encryption is considered a secure form of cryptography. To this date, there is no confirmed algorithm for prime factorization.

Prime factorization is a classic example of a problem in the NP class. An NP class problem can be thought of as a problem whose solution is easily verified once it is found but not necessarily easily or quickly solved by either humans or computers. The P vs. NP problem is one that has perplexed computer scientists and mathematicians since it was first formulated in 1971. Most recently, a German scientist Norbert Blum has claimed to solve the P vs. NP problem in this article: https://motherboard.vice.com/en_us/article/evvp34/p-vs-np-alleged-solution-nortbert-blum

Also in recent years, A Texas student has been featured on Dallas County Community Colleges Blog for his work to find an algorithm for prime numbers: http://blog.dcccd.edu/2015/07/%E2%80%8Btexas-math-student-strives-to-solve-the-unsolvable/

green line

• How could you as a teacher create an activity or project that involves your topic?

An activity for inquiry based learning of prime numbers and prime factorization utilizes pop cubes. Students will start out with a single color-coded cube representative of the number two (the first prime), they will then move up the list of natural numbers with each prime number having its own color of cube. The composite numbers will have the same colors as their prime factors. The idea is that students will visually see that prime numbers are only divisible by themselves (each being a lone cube) and that composite numbers are simply composed of primes (multiple cubes). A good point of discussion is the meaning of the word “composite’. You could ask students what they think the word ‘composite’ means and what word it reminds them of. This leads into the idea that every composite number is composed of prime numbers. This idea comes from online vlogger Thom Gibson and the RL Moore Inquiry Based Learning Conference. Below is a picture demonstrating the cube idea:

This foundational idea can be segued into The Fundamental Theorem of Arithmetic and then into prime factorization.
One of the most practical real-world applications of prime factorization is encryption. This activity I found makes use of prime factorization in a way that is interesting and different from simply making factor trees. This worksheet would be a good assessment and challenge for students and mimics a real –world application.

https://www.tes.com/teaching-resource/prime-factors-cryptography-6145275

green line

• How does this topic extend what your students should have learned in previous courses?

 

Though not actually ‘reducing’ the value of a number, prime factorization is the equivalency of numbers broken down into their smallest parts and then multiplied together. The idea of reducing numbers goes all the way back to elementary school when students are learning about fractions. Subconsciously they use a similar process to prime factorization when reducing fractions to simplest form. When reducing fractions to simplest form, the numerators and denominators themselves may not both necessarily be prime, but when put into simplest form, they are relatively prime. Being able to pick out factors of numbers –another relatively early grade school concept (going back to multiplication and division) — plays a huge deal in both fractions and prime factorization.

Euler and 1,000,009

Here’s a tale of one the great mathematicians of all time that I heard for the first time this year: the great mathematician published a mistake… which, when it occurs today, is highly professionally embarrassing to modern mathematicians. From Mathematics in Ancient Greece:

In a paper published in the year 1774, [Leonhard] Euler listed [1,000,009] as prime. In a subsequent paper Euler corrected his error and gave the prime factors of the integer, adding that one time he had been under the impression that the integer in question admitted of the unique partition

1,000,009 = 1000^2 + 3^2

but that he had since discovered a second partition, namely

1,000,009 = 235^2 + 972^2,

which revealed the composite character of the number.

See Wikipedia and/or Mathworld for the details of how this allowed Euler to factor 1,000,009.

Factoring Mersenne “primes”

I love hearing and telling tales of legendary mathematicians. Today’s tale comes from Frank Nelson Cole and definitely comes from the era before calculators or computers. From Wikipedia:

On October 31, 1903, Cole famously made a presentation to a meeting of the American Mathematical Society where he identified the factors of the Mersenne number 267 − 1, or M67. Édouard Lucas had demonstrated in 1876 that M67 must have factors (i.e., is not prime), but he was unable to determine what those factors were. During Cole’s so-called “lecture”, he approached the chalkboard and in complete silence proceeded to calculate the value of M67, with the result being 147,573,952,589,676,412,927. Cole then moved to the other side of the board and wrote 193,707,721 × 761,838,257,287, and worked through the tedious calculations by hand. Upon completing the multiplication and demonstrating that the result equaled M67, Cole returned to his seat, not having uttered a word during the hour-long presentation. His audience greeted the presentation with a standing ovation. Cole later admitted that finding the factors had taken “three years of Sundays.”

A nice article on recent progress on solving the twin prime conjecture

The twin prime conjecture (see here, here and here for more information) asserts that there are infinitely many primes that have a difference of 2. For example:

3 and 5 are twin primes;

5 and 7 are twin primes;

11 and 13 are twin primes;

17 and 19 are twin primes;

29 and 31 are twin primes; etc.

While most mathematicians believe the twin prime conjecture is correct, an explicit proof has not been found. Indeed, this has been one of the most popular unsolved problems in mathematics — not necessarily because it’s important, but for the curiosity that a conjecture so simply stated has eluded conquest by the world’s best mathematicians.

Still, research continues, and some major progress has been made in the past few years. (I like sharing this story with my students to convince them that not everything that can be known about mathematics has been figure out yet — a misconception encouraged by the structure of the secondary curriculum — and that research continues to this day.) Specifically, it was recently shown that, for some integer N that is less than 70 million, there are infinitely many pairs of primes that differ by N.

http://video.newyorker.com/watch/annals-of-ideas-yitang-zhang-s-discovery-2015-01-28

http://www.newyorker.com/magazine/2015/02/02/pursuit-beauty

For more on recent progress: