NUMBER THEORY I --- PRIMES

A class from Washington School visited a neighboring cannery warehouse. The manager told the class that there were 11,368 cans of juice in the inventory and that the cans were packed in boxes of 6 or 24 depending on the size of the can. One of the students thought for a moment and announced that there was a mistake in the inventory. Is Sam’s statement correct? Why or why not?

DEFINITION: natural number is a counting number. N = {1, 2, 3, 4, 5, 6, . . . }

The natural number will be either prime or composite. A prime number is a natural number having two distinct divisors: itself and the number 1. Every composite number may be expressed as a product of prime numbers.

DEFINITION of DIVISIBILITY: The natural number a is divisible by the natural number b if there exists a natural number k such that a = bk. We can write this as: b ∣ a

DIVISIBILITY TESTS for the NATURAL NUMBERS:

Divisible
by / Test
2 / Number ends in 0, 2, 4, 6, or 8
3 / Sum of the digits is divisible by 3
4 / Last two digits form a number divisible by 4
5 / Number ends in 0 or 5
6 / Number is divisible by both 2 and 3
8 / Last three digits form a number divisible by 8
9 / Sum of the digits is divisible by 9
10 / Last digit is 0
12 / Number is divisible by both 3 and 4

Additional tests for divisibility:

  • Divisibility by 7 ---- Double the last digit of the given number, and subtract this value from the

given number withthe last digit omitted. Repeat this process as many times

as necessary until it is clear that thenumber obtained is divisible by 7. If the

final number obtained is divisible by 7, then the given number is also

divisible by 7.

  • Divisibility by 11 ---- Starting at the left of the given number, add together every other digit. Add

together the remaining digits. Subtract the smaller of the two numbers

from the larger. If the final number is divisible by 11, then the given number

isalso divisible by 11.

Choose any six digit number consisting of three digits, followed by the same three digits in the same order. (467,467 for example).

Divide the number by 13, then the result by 11, and the final result by 7.

What do you notice? Why do you think this happens?

PRIMES: can be thought of as the building blocks of the integers. There’s

only one way to write each positive integer as a sum of 1s, there’s also only one way to write

each positive integer as a product of primes (Fundamental Theorem of Arithmetic).

  1. How can 48 be built from primes? In what sense is there only one way? How can you organize your work in general to find the prime factors of moderately large numbers like 2006?
  1. What are all the divisors of 48? 120? 2006? How many different ways can you organize those answers?
  1. How many divisors does each of those numbers have?
  1. List two primes that are consecutive natural numbers. Can there be any others?
  1. Can there be three primes that are consecutive natural numbers? Explain.
  1. How many primes are there?

Euclid proved the given any finite list of primes, there exists a prime not on the list.

Let 2, 3, 5, 7, . . . , p be a list of all the primes less than or equal to p. We will show that there

existsa prime not on the list.

Consider the product: 2 ∙ 3 ∙ 5 ∙ 7 ∙ . . . ∙ p

Notice that every prime in our list divides that product. However, if we add 1 to the product,

thatis, form the number N = (2 ∙ 3 ∙ 5 ∙ 7 ∙ . . . ∙ p) + 1, then none of the primes in the list will

divide N. Notice that whether N is composite or prime, some q must divide N. Because no prime

in our list divides N, q is not one of the primes in our list. Consequently, q > p. Therefore, there

exists a prime greater than p.

  1. Explain why no prime in our list will divide N.
  2. Explain why some prime must divide N.
  3. Someone discovered a prime that has 65,050 digits. How does the preceding argument show us that there exists an even larger prime?
  4. Does the argument show us that there are infinitely many primes? Why or why not?
  5. Let M = 2 ∙ 3 ∙ 5 ∙ 7 ∙ 11 ∙ 13 ∙ 17 ∙ 19 + 1. Without multiplying, explain why some prime greater than 19 will divide M.
  1. Consider the following exercises:
  1. Is 221 prime? If not, what are its factors?

b. What’s the largest divisor you need to check to be sure that 397 is prime?

How doyou know it’s the largest?

  1. Is 8171 prime, or not? How do you know for sure?
  1. List all the primes from 1 through 500.

DISTRIBUTION of PRIMES: (what fraction of numbers are prime? How big are the gaps?)

4. You might have noticed that the gaps between primes tend to get bigger as you go along.

Fill in the blanks to get one measure of how much bigger they are getting on average.

  • Between 1 and ______there are 10 primes.
  • Between 100 and ______there are 10 primes.
  • Between 400 and ______there are 10 primes.
  • The longest run of consecutive composite numbers between 1 and 100 starts with ______

and ends with ______and is ______long.

  • The longest run of consecutive composite numbers between 401 and 500 starts with ______

and ends with ______and is ______long.

[By the way, there’s a great opportunity to teach about fencepost errors in these last two!

If boats leave every 15 minutes, how many leave from 9am to 5pm? 37, not 36! How

many numbers are there from 27 through 33? 7, not 6!]

5.Do the gaps between primes get longer and longer, or is there eventually a record-size

gap that never gets beaten?

Factorials give a great clue about this problem. A factorial, like 7!, means to multiply all

the integers from 7 down to 1. So, 7! is7 × 6 × 5 × 4 × 3 × 2 × 1, which is the important

part, or 5040, which isn’t very important at all.

  • The number 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 + 2 is composite – not prime. How can

you be sure? Well, if you can find a factor that’s not 1 or the number itself, it must be

prime.

  • Is 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 + 3 composite?
  • Based on your answers to the previous two problems, there must be at least how many

composite numbers in a row, starting from 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 + 2?

  • Name a number which you can be sure is in a string of at least 99 composite numbers

in a row.

  • Name a number which you can be sure is in a string of at least 999 composite numbers

in a row.

  • Explain how you can be sure that any record number of composites in a row eventually

gets broken.

6. Primes are a lot more dense toward the beginning of the list, as we saw in the lastproblem. At the

beginning of the list, in fact, there are three odd numbers in a row (3, 5,7) which are all prime!

  1. Does that ever happen again in your list?
  1. Can it ever happen later on, maybe beyond 500? Why or why not?

You can find pairs of primes in your list: two odd numbers in a row which are bothprime. These are

called “twin primes”, like 17 and 19, or 41 and 43.

  1. List all the twin primes less than 500.
  1. In part (b) you explained why there can’t be any more triple primes besides 3, 5, 7:

there’s only one triple prime. You also know Euclid’s proof that there are infinitely

many primes. How about twin primes? How many sets are there?

ADDING PRIMES:

Primes are made for multiplying. As long as you’re multiplying and factoring, primes are the

way to go. Once you start adding, things get hard. So hard, in fact, that the solution to some

parts of this problem are not yet known even after hundreds of years of work by the best

mathematicians. But some parts, you can do in just a few minutes!

7. Let’s see what numbers we can make by adding up two primes.

2 + 2 = 4 2 + 3 = 5 3 + 3 = 6 2 + 5 = 7 3 + 5 = 8 2 + 7 = 9

and so on. It seems like every number is either prime, or we can make it by adding up

two primes. For example, 39 is 37 + 2, while17 can’t be made by adding two primes, but it is

prime itself.

  1. Make all the composite numbers less than 20 by adding two primes.
  1. Find a number that’s not prime, and is not the sum of two primes.

Hint: there’s one inthe 20s!

  1. Is there such a number in the 30s? In the 50s?
  1. Find a pattern in these numbers. Hint: look at the size of the “gaps” between primes.

Explain, based on your answer, exactly how you can tell whether an odd composite

number is the sum of two primes or not.

  1. The examples in b, c, and the discussion in part d probably all led you to odd numbers.

Can you find an even number which is not prime, and not the sum of two primes?

Squares:

8. A perfect square, or square number, is what you get when you multiply a whole number

by itself.

  • Just for practice, write down the first 10 perfect squares.
  • List all the primes up to 100. For each one, determine whether it can be made by

adding up two perfect squares or not. For example, 5 = 4 + 1, but 7 cannot be written as

the sum of two perfect squares. For the numbers that can be written as the sum of two

perfect squares, keep track of which squares you used.

  • Find a pattern that tells you which primes can be written as the sum of two squares.

Hint: look at where they land in the big sieve. How do they line up?

  • [Warning: really hard!] Explain why all the possible ones really are possible. That is,

how do you know the pattern you’ve observed keeps working forever?

Prime-generating formulas : (Mersenne and Euler)

9. Mathematicians have long sought formulas that generate prime numbers, only prime

numbers, and ideally every prime number. Here are two formulas that are a few centuries

old, that turn out to be quite interesting prime-generating mechanisms even if they don’t

work quite as the mathematicians originally hoped.

  • One famous formula involves the numbers that are one less than the powers of 2.

Tobegin, 21 – 1 = 1, a unit, not prime. Then 22 – 1 = 3, which is prime. 23 – 1 = 7, which is

prime. But 24 – 1 = ______, which is ______.

  • That formula has a lot better chance of working if the exponent is prime. Try 25 – 1,

27 – 1, and so on. Are all of those primes? How long does the pattern work?

  • Another famous pattern, for which my favorite mathematician, Euler, gets the credit, is:

start with any number, square it, subtract your original number, and then add 41.

Inother words, n2 – n + 41. When n = 1, we get 1 squared is 1, minus the original 1

leaves0, adding 41 gives 41. When n = 2, we get 2 squared is 4, minus the original 2 leaves 2,

plus 41 makes 43. How long can we use this pattern to produce new prime numbers?

Interesting facts/conjectures:

  1. More than 2000 years, Euclid proved that there exists no largest prime.
  2. A 17th century monk, Mersenne found that number of the form 2n – 1 are primes when n is a prime.
  3. In 1772, Euler devised a formula n2 – n + 41 which yields a prime for all natural numbers n up to 40, but fails for 41.
  4. In 1879, Escott devised a formula n2 – 79n + 1601 which yields a prime for all natural numbers up to 79, but fails for 80.
  5. In 1742, Goldbach conjectured in a letter to Euler that every even number greater than or equal to 6 can be expressed as a sum of two primes, and every odd number greater than or equal to 9 can be represented as the sum of three odd primes.
  6. Another conjecture is that there are infinitely many pairs of twin primes of the form p and p + 2.

Links that you may be interested in looking at: