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:

 

 

 

 

 

 

15-square puzzle

From the category “This Is Completely Useless”: here’s what a 15-square puzzle looks like when you arrange the tiles in order of how many factors they have.

puzzle15