Primes and Composites

In the Chinese book: 素数与合数

Sieve out multiples round by round; what is left is prime. Stop at √N.

📖 §1.2 of 《整除、同余与不定方程》M13 Prime Factor Analysis line

Try this

Sieving with $2$ crosses out a huge chunk. Then sieve with $3$ : among the numbers crossed out for the first time in this round, which is the smallest? What about sieving with $5$ and with $7$ ?
The smallest number crossed out for the first time is always $p^{2}$ . Why are the smaller multiples $2 p$ , $3 p$ , … already gone?
After sieving with $7$ , the button stops working. The next prime is $11$ , but $1 1^{2} = 121$ is already past $100$ .
Set $N$ to $150$ and sieve again. Which extra prime did you need this time? Why only that one?

An integer greater than $1$ whose only positive divisors are $1$ and itself is called a prime; otherwise it is called composite. $1$ is neither.

Predict first

To decide whether $223$ is prime by dividing by primes, what is the largest prime you need to try?

7

13

17

111

(half of it)

Choose an answer first; then you can see the result.

Why

“You only need to go up to $n$ ” rests on this small fact.

A composite n has a prime factor no bigger than √n

Step 1 / 5

A composite splits into two numbers
Let $n$ be composite. It has a divisor other than $1$ and $n$ , so $n = ab$ with $1 < a \leq b$ .

$n = a \cdot b, 1 < a \leq b$
The smaller one is not too big
Now take a prime factor of a
See it in the sieve
After four rounds

Do the primes ever run out?

Can the sieve go on forever? Or is there some point after which there are no more primes?

Predict first

Multiply the first six primes and add $1$ : $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031$ . Is it prime?

PrimeNot prime

Choose an answer first; then you can see the result.

Practice

Exercise 1Basic

List all the primes between $40$ and $60$ .

Exercise 2Basic

How many of the four numbers $91$ , $97$ , $119$ , $127$ are prime?

Exercise 3Advanced

$p$ is a prime such that $p + 10$ and $p + 14$ are also prime. Find $p$ .

Exercise 4Challenge

Find all positive integers $n$ such that $n^{2} - 8 n + 15$ is prime.

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Calling 1 a prime

1

is divisible only by

1

and itself, so

1

is prime.

What went wrong? Think first, then open

Diagnosis A prime must have exactly two different positive divisors, and $1$ has only one. More importantly: if $1$ counted as a prime, then $6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3$ , and factorization would no longer be unique.

The positive integers fall into three groups:

1

; the primes (greater than

1

, with only the two positive divisors

1

and itself); and the composites.

1

is a group of its own.

“1 is neither prime nor composite”

Exhibit

Trying only 2, 3 and 5

91

is odd, its digit sum

10

is not divisible by

3

, and it does not end in

0

5

, so

91

is prime.

What went wrong? Think first, then open

Diagnosis $91 \approx 9.5$ , and the primes up to that are $2, 3, 5, 7$ . The $7$ was never tried, and $91 = 7 \times 13$ .

To decide whether

n

is prime, try every prime up to

n

“Go all the way up to the square root, and skip none”

Exhibit

Thinking “product of primes plus 1” is always prime

2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031

is not divisible by the first six primes, so it is prime.

What went wrong? Think first, then open

Diagnosis $30031 = 59 \times 509$ . It is only guaranteed not to be divisible by $2, 3, 5, 7, 11, 13$ . Nobody promised it is not divisible by a bigger prime.

Euclid's argument only says that the prime factors of this number are not on the original list. That is already enough to show the list is incomplete.

“Claim only what your proof actually uses”