- Author:
- Amanda Hager
- Subject:
- Mathematics
- Material Type:
- Lesson
- Level:
- Academic Lower Division
- Provider:
- University of Texas at Austin
- Tags:

- License:
- Creative Commons Attribution
- Language:
- English
- Media Formats:
- Text/HTML, Video

# Education Standards

# Sieve of Eratosthenes PDF

# 2.1 Prime numbers

## Overview

TCCNS Course | MATH 1332: Contemporary Mathematics |

UT Austin Course | M 302: Introduction to Mathematics |

# Introduction

**Suggested Resources and Preparation**

**Materials and Technology**

For the instructor: method of projecting videos

For the student: a four function calculator will be useful

**Prerequisite Assumptions**

Students need to be able to factor positive integers into a product of primes using a method of their choice. Review: Khan Academy.

Students should be able to quickly identify prime numbers less than 100. A Sieve of Eratosthenes demonstration or exploration may be helpful.

**Overview and Student Objectives**

**Lesson Length**

50 minutes

**Lesson Objectives**

Students will understand that:

- All positive numbers greater than 1 are either prime or composite.
- There are infinitely many composite numbers because we are able to construct infinitely large families of composite numbers.
- There are infinitely many prime numbers because it is impossible for there to be finitely many prime numbers.

Students will be able to:

- Use numeric examples in order to formulate conjectues.
- Prove the existence of infinitely many composite numbers by constructing families of composite numbers.
- Explain why it is insufficient to claim that there are infinitely many prime numbers because there are infinitely many numbers.
- Prove that certain properties of primes are always true using short algebraic arguments.
- Prove that certain properties of prime numbers are not always true using numeric counterexamples.

# Prime numbers

# Algebra review

One number *factors* another number if you can divide the numbers and get no remainder.

We typically teach American schoolchildren to factor numbers by using *factor trees.* All you have to do is experiment until you find one number that divides your number, and then show the number "branching out" into a product of the two numbers. For example, if we start with 360, you might notice that 360 is divisible by 10, so you show 36 and 10.

When you get to a prime number, circle it to save it. Then the final answer is

\(360=2\times2\times2\times3\times3\times5=2^3\times3^2\times5\)

This is not the only way to start! You could use 360 = 180 x 2, 360 = 120 x 3, or 360 = 4 x 90.

# Terms

- If a number greater than 1 can be expressed as a product of two smaller natural numbers (other than 1), then it is
.*composite* - If a number greater than 1 cannot be expressed as a product of two smaller natural numbers (other than 1), then it is
. In other words, every number is divisible by 1 and itself, but if the*prime**only*factors of a number are 1 and itself, then it is prime.

Video: Primes algebra review and definitions

# Are there infinitely many primes?

Primes get more spread out as we get bigger. At first they are close together:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...

But note that there is a gap of 1475 between the prime number 1425172824437699411 and the next prime number 1425172824437700867. That means every odd number between those two numbers is composite! What if the gap becomes infinitely big?

The reason there are infinitely many primes is NOT because there are infinitely many numbers. What if there are finitely many primes and infinitely many non-primes based off those primes?

# The proof

When we write formal math proofs, we write "Claim:" and state the fact we are trying to prove, and then we write "Proof:" and write our logical argument. I advise you take notes or save this proof somewhere; below it I include some text and video to help you make sense of it. It's only one paragraph but it's normal for it to take a looooong time to understand.

**Claim: **There are infinitely many prime numbers.

**Proof:** Let’s pretend the opposite statement is true, that there are *not* infinitely many primes. That means there are finitely many, which means there has to be a biggest one. Let’s name it *n*.

Now let’s make this really huge number *M* = *n*! + 1. (Why? You'll see, just roll with it). We don’t know if *M* is prime or composite, but we do know that it is bigger than *n*.

If *M* is prime, well now we have a prime that is bigger than the biggest prime *n*. That is a contradiction.

If *M* is composite, then it has a bunch of prime factors, and I claim that all of these are bigger than *n*. The logic goes like this:

- First of all,
*n*! is divisible by every single number between 2 and*n*. - That means when you divide
*n*! by any number between 2 and*n*you get a remainder of 0. - That means when you divide
*n*! + 1 by any number between 2 and*n*, you get a remainder of 1. (Try it! Notice how 120/5 = 24, but 121/5 = 24 R 1). - That means that
*n*! + 1 is not divisible by any number between 2 and*n*, but it was supposed to be divisible by something. *M*must be divisible by primes that are bigger than*n*.

Either way, we have proved there’s a bigger prime than *n*. This is a contradiction to the part where *n* was supposed to be the biggest prime.

So we conclude there is no biggest prime. There are infinitely many primes.

These two videos give a mini-lecture covering the above proof.

Video: Proof of infinitely many primes 1

Video: Proof of infinitely many primes 2

# Extra stories and trivia

These examples are "for fun" and are not represented on your homework.

## Primes help you not get your identity stolen

Every time you visit a site that starts with "https:" you are relying on asymmetric encryption to keep people from spying on you. One kind of asymmetric encryption is the RSA algorithm, which relies on giant prime numbers to work. The secret is that it's kind of easy to find gigantic prime numbers, it's really easy to multiply two gigantic prime numbers together, but it's practically impossible to factor the product back apart unless you know the primes.

Speaking of primes being hard, there are some outstanding questions regarding primes that everybody can understand, but nobody can solve.

## Twin Primes Question

For example, are there infinitely many pairs of prime numbers that differ from one another by two? Examples: 3&5, 5&7, 11&13, 17&19, 29&31, 41 & 43 are twin primes. Nobody knows the answer!

## The Goldbach Question

Can every positive, even number greater than 2 be written as the sum of two primes? Examples:

4 = 2 + 2

6 = 3+3

8 = 5+3

10 = 5+5

12 = 5+7

14 = 7+7

16 = 13+3

18 = 13+5

20 = 13+7

22 = 11+11

Nobody knows the answer!

# Quiz Questions

Question | Answer |

1 | 1 |

2 | 2 |

3 | 1 |

4 | 1 |

5 | 1 |

6 | 1 |

7 | 1 |

# Question 1

Can 10 be written as the product of two smaller natural numbers?

*Natural numbers *are whole numbers that are 1 and up, so 1, 2, 3, 4, 5, ...

- Yes
- No

# Question 2

Can 13 be written as the product of two smaller natural numbers?

- Yes
- No

# Question 3

What is the correct prime factorization of 180?

- 2*2*3*3*5
- 4*5*9
- 1*180
- 2*90

# Question 4

Which of the following is divisible by 2, 3, 4, and 5?

- 2*3*4*5
- 2*3*9
- 2*3*4
- 2+3+4+5

# Question 5

Which of the following will have remainder 1 when divided by 2, 3, 4, or 5?

- \(2\times3\times4\times5+1\)
- \(2\times3\times4+5\)
- \(2\times3\times4\times5\)
- \(2+3+4+5+1\)

# Question 6

Which of the following will have remainder 1 when divided by any number 100 or less?

- \(2\times3\times4\times5\times\dots\times99\times100+1\)
- \(2+3+4+5+...+99+100\)
- \(2\times3\times4\times5\times\dots\times99\times100\)

# Question 7

Looking at the number \(2\times3\times4\times5\times\dots\times999\times1000+1\), what will the remainder be when dividing by a number between 2 and 1000?

- 1
- 0
- Could be any number between 1 and 1000

# Question 8

Let \(M=1\times2\times3\times4\times5\times\dots\times999\times1000+1\). Is M necessarily prime?

- Yes
- No

# Homework Questions

# Question 2.1.1

\(98=2\cdot7^2\\ 137=137\\ 480=2^5\cdot3\cdot5\\ 1056=2^5\cdot3\cdot11\)

# Question 2.1.2

- Even
- \(n+1\geq4\)
- \(n+1 \) must be composite.
- If n is 1, then \(n+1=2\), which is the only even prime.

# Question 2.1.3

\(2!+1=3, 3!+1=7, 4!+1=25=5^2\), so the answer must be 4.

# Question 2.1.4

A prime multiplied by a prime is never prime, since it's necessarily divisible by those two primes.

# Question 2.1.5

A non-prime divided by a non-prime is sometimes prime. Sometimes it's composite. Sometimes it's not even an integer. Examples: 8/4, 16/4, 6/4.

This question isn't asking students to prove exactly when you get a prime or a non-prime. It suffices for them to give one example of each (proving that the quotient isn't always prime and it isn't always non-prime either).

# Question 2.1.6

A prime divided by a prime is either equal to 1 (not prime) or it is equal to a non-integer (since the quotient's numerator and denominator have no factors in common). Therefore it is never prime.

Question 2.1.7

There are many families of numbers that are inifinitely big and all non-prime. Common responses include:

- All even numbers greater than 2.
- All prime numbers plus 1 (except 2).
- All squares of natural numbers.

Question 2.1.8

Mindset question. Responses will vary.

# Question 2.1.1

Express the following numbers into a product of primes: 98, 137, 480, 1056.

# Question 2.1.2

If \(n\) is an odd number greater than or equal to 3, can *\(n+1\)* ever be prime? Do these steps:

- If \(n\) is odd, then is \(n+1\) even or odd?
- If \(n\) is greater than or equal to 3, then what can you say about \(n+1\)?
- Combine the results of parts 1 and 2 to make a conclusion about whether or not \(n+1\)is prime.
- What happens when
*n*is equal to 1?

# Question 2.1.3

Use a calculator to find *\(n!+1\)* for *\(n\)* ranging from 1 to 10. Then look up the prime factorizations of all ten of those numbers (Google knows, and so does Wolfram Alpha). What is the smallest natural number *\(n\)* for which *\(n!+1\)* is not prime?

# Question 2.1.4

Does a prime multiplied by a prime always, sometimes, or never result in a prime? Prove your response (don't just provide examples).

# Question 2.1.5

Does a non-prime divided by a non-prime always, sometimes, or never result in a prime?

# Question 2.1.6

Does a prime divided by a prime always, sometimes, or never result in a prime?

Question 2.1.7

Prove that there are infinitely many numbers that are non-prime.

# Question 2.1.8

When doing academic work, when do you feel it’s OK to make a mistake, or show that you don’t know something or how to do something?