Grade 4 · 4.OA.B.4

Prime and composite numbers

Some trays of seedlings can be planted in a rectangle of equal rows in several ways, and some only in one long row. Which numbers are which, and how can you tell?

You need

Factors and multiplesGrade 4

Unlocks

Prime factorizationMath 6 The sieve of EratosthenesMath 6 Fermat's little theoremDiscrete Mathematics and Proof There are infinitely many primesDiscrete Mathematics and Proof +1 more

Where you are 10 in Divisibility and primes

Number9

Divisibility and primes10

▴ 2 above Listing multiples Perfect, abundant, deficient and amicable numbers

Prime and composite numbers

Prime factorization Tests for three and nine ▾ Show all 10 (3 more)

Why this exists

Pranav is planting seedlings. He likes a neat bed: equal rows, every row the same length, no seedling left over. With 12 seedlings he has choices. He can plant 2 rows of 6, or 3 rows of 4, or one long row of 12.

With 13 seedlings he tries 2 rows and has one left over. He tries 3 rows and has one left over again. Every try fails except one long row of 13 (or the same row turned, 13 rows of one seedling each).

Figure 113 seedlings make one long row, but 2 rows or 3 rows leave one over. No rectangle except a single row works, so 13 is prime.

So whole numbers come in two kinds. Some split into equal rows in more than one way. Others refuse to split at all, except into one row. The second kind turn out to be the building blocks that every other whole number is made from, so they get a name of their own.

Definition

In Factors and multiples you listed every factor of a number by finding its factor pairs. Now count how many factors there are.

A prime number is a whole number greater than 1 that has exactly two factors: 1 and the number itself.

A composite number is a whole number greater than 1 that has more than two factors.

The number 1 is neither. Its only factor is 1, so it has just one factor. That is not two, so 1 is not prime, and it is not more than two, so 1 is not composite.

Number	Factors	Kind
1	1	neither
2	1, 2	prime
7	1, 7	prime
8	1, 2, 4, 8	composite
13	1, 13	prime
12	1, 2, 3, 4, 6, 12	composite

The same idea in pairs: every number n has the pair 1 \times n. A number greater than 1 is composite when it has some other factor pair as well, and prime when 1 \times n is its only pair.

Intuition

Part 1: one row, or more than one way

Picture the seedlings as an array, as in Arrays. A factor pair is a rectangle: the number of rows times the number in each row.

Figure 212 seedlings fill a rectangle in more than one way: 1 \times 12, 2 \times 6 and 3 \times 4, plus the same rectangles turned. So 12 is composite.

One long row always works. It is the pair 1 \times n, and every number has it. So a single row tells you nothing about the number. What matters is whether there is any other rectangle.

If there is, the number is composite. One more rectangle, such as 2 rows of 6 for 12, is enough to show it: 2 and 6 are factors besides 1 and 12.
If there is not, the number is prime. Its seedlings can only stand in one line, across the bed or down it.

A single seedling is different again. It is one row of one, and turning it changes nothing. There is only one way to plant it, and only one factor. That is why 1 sits outside both kinds.

Two is prime, and it is even. The factors of 2 are 1 and 2, exactly two. But every other even number has 2 as a factor too, so it has 1, 2 and itself: at least three factors. So every even number bigger than 2 is composite, and 2 is the only even prime.

Part 2: deciding prime or composite up to 100

To call a number composite, you need one factor pair other than 1 \times n. To call it prime, you need to know there is none. So the work is a search for a small factor.

Test small numbers in order: 2, 3, 4, and so on. A test is a division. If one leaves remainder 0, you have found a second factor pair, and the number is composite. You can stop right there.

You never need to test far. In any factor pair other than 1 \times n, one of the two numbers is the smaller one (or they are equal). That smaller number, times itself, is no more than the number. So once a test number times itself passes the number, stop: any factor pair would have shown up already. This is the same crossing point used in Factors and multiples.

Up to	Last test	Why
24	4	5 \times 5 = 25
48	6	7 \times 7 = 49
63	7	8 \times 8 = 64
99	9	10 \times 10 = 100

You only need the primes among the test numbers. If 4 divides a number, so does 2, since 4 = 2 \times 2; the test for 2 would already have found a factor. The same goes for 6, 8 and 10 (each is 2 times something) and for 9 (which is 3 \times 3). So below 100 the tests that can ever matter are 2, 3, 5 and 7. Some of them take one glance: Divisibility rules reads 2 and 5 off the last digit.

Looks can fool you. Numbers such as 51 and 57 are odd and do not end in 5, yet they are composite. The only way to know is to run the tests.

Results

Every whole number greater than 1 is either prime or composite, never both. The number 1 is neither.
A number greater than 1 is composite exactly when it has a factor pair other than 1 \times n. One such pair is enough.
2 is the only even prime. Every even number greater than 2 is composite.
The stopping rule. To test a number for primes, try test numbers in order, starting at 2, and stop once a test number times itself is more than the number. If no test leaves remainder 0, the number is prime.
Below 100, four tests settle it. A whole number from 2 to 100 that is not 2, 3, 5 or 7 is prime exactly when none of 2, 3, 5, 7 divides it.

Why it is true

Prime or composite, never both. A whole number n greater than 1 has 1 and n as factors, and these are two different numbers. So it has at least two factors. Either it has exactly two, and is prime, or it has more, and is composite. It cannot have exactly two and more than two at once. For n = 1 the “two different numbers” are the same number, so 1 has only one factor.

Two is the only even prime. An even number n is 2 times a whole number, so 2 is a factor. If n is bigger than 2, then 1, 2 and n are three different factors, so n is composite. That leaves 2 itself, with factors 1 and 2 only.

The stopping rule. Suppose n is composite, so n = a \times b with neither a nor b equal to 1. Call a the smaller of the two (or either, if they are equal). Then a \times a is no bigger than a \times b, which is n. So the smaller factor a always comes before the point where a test number times itself passes n. Testing every number up to that point must find it. If none of those tests works, there is no such pair, and n is prime.

Four tests below 100. For n up to 100, the smaller number a in a pair has a \times a \le 100, so a is at most 10. If a is 4, 6, 8 or 10, then a is 2 times a whole number, so n = a \times b is 2 times a whole number too, and 2 divides n. If a is 9, then 3 divides n the same way. So a composite number up to 100 always has one of 2, 3, 5, 7 as a factor.

Worked examples

Examples 1, 2 and 3 go with Part 1. Examples 4, 5, 6 and 7 go with Part 2.

Example 1

Twenty-nine seedlings and fifty-five seedlings

Sumaq has a tray of 29 seedlings and a tray of 55. For each, list the factors and say whether the number is prime or composite.

Solution

For 29, search for factor pairs. The pair 1 \times 29 is always there. Then: 29 \div 2 = 14 \text{ R } 1, 29 \div 3 = 9 \text{ R } 2, 29 \div 4 = 7 \text{ R } 1 and 29 \div 5 = 5 \text{ R } 4. The next test, 6, has 6 \times 6 = 36, which passes 29, so the pairs have crossed and the search is over. The factors are 1 and 29: exactly two. So 29 is prime. In the garden: the 29 seedlings go in one long row, and no other rectangle works.

For 55, the last digit is 5, so try 5: 55 \div 5 = 11. That gives the pair 5 \times 11, a rectangle of 5 rows of 11. Already 55 has the factors 1, 5, 11 and 55, more than two, so 55 is composite. (Testing on shows there are no others: the full list is 1, 5, 11, 55.)

Example 2

One seedling and two seedlings

Ulrikke has one seedling left in one tray and two in another. Is 1 prime? Is 2?

Solution

The factors of 1: the only pair is 1 \times 1, so the list is just 1. One factor. A prime needs exactly two, and a composite needs more than two, so 1 is neither. In the garden, one seedling is one row of one, and turning that row gives the same row, so there is only one way to plant it.

The factors of 2: the pair 1 \times 2, and nothing else, since a factor of 2 can be no bigger than 2. So the list is 1, 2: exactly two factors, and 2 is prime. Two seedlings make one row of 2 or two rows of 1, the same row turned. It is even, and it is still prime; it is the only even number that is.

Example 3

Which trays from 20 to 28 make a rectangle

Pranav has trays holding every number of seedlings from 20 to 28. Which ones can be planted in a rectangle with more than one row and more than one seedling in each row?

Solution

A rectangle like that is a factor pair other than 1 \times n. Find one for each number, if there is one.

Seedlings	A rectangle	Kind
20	2 \times 10	composite
21	3 \times 7	composite
22	2 \times 11	composite
23	none	prime
24	2 \times 12	composite
25	5 \times 5	composite
26	2 \times 13	composite
27	3 \times 9	composite
28	2 \times 14	composite

For 23: 23 \div 2 = 11 \text{ R } 1, 23 \div 3 = 7 \text{ R } 2 and 23 \div 4 = 5 \text{ R } 3, and 5 \times 5 = 25 passes 23, so there is no pair but 1 \times 23.

Every tray except the 23 makes a rectangle. The even ones, 20, 22, 24, 26, 28, all split into 2 rows, as Part 1 says every even number above 2 must. The tray of 25 makes a square, 5 rows of 5.

Example 4

Is 59 prime

Sumaq counts 59 seedlings. Is 59 prime or composite?

Solution

Find where to stop first. 7 \times 7 = 49 is less than 59, but 8 \times 8 = 64 passes it. So test the numbers up to 7, and only the primes among them matter: 2, 3, 5, 7.

2: 59 ends in 9, so it is odd. No.
3: 59 \div 3 = 19 \text{ R } 2. No.
5: 59 does not end in 0 or 5. No.
7: 59 \div 7 = 8 \text{ R } 3. No.

No test leaves remainder 0, and the stopping rule says any factor pair would have shown up by now. So 59 is prime: 59 seedlings go in one long row.

Example 5

Two that look prime

Ulrikke thinks 51 and 57 are both prime, because they are odd and do not end in 5. Is she right?

Solution

Being odd rules out 2, and the last digit rules out 5. That leaves 3 and 7 to test, and neither has been tried yet.

For 51: 51 \div 3 = 17, remainder 0. So 51 = 3 \times 17, a rectangle of 3 rows of 17. 51 is composite.

For 57: 57 \div 3 = 19, remainder 0. So 57 = 3 \times 19, and 57 is composite too.

She is not right. Each number passed two tests and failed the third. Looking odd and not ending in 5 only clears 2 and 5; the other tests still have to be run.

Example 6

The primes from 60 to 70

Pranav wants a tray that can only go in one long row. Which numbers from 60 to 70 could it hold?

Solution

He needs the primes from 60 to 70. Since 9 \times 9 = 81 passes 70, the tests are 2, 3, 5 and 7.

The even numbers 60, 62, 64, 66, 68, 70 are all composite, since each is bigger than 2 and has 2 as a factor. That leaves the odd numbers 61, 63, 65, 67, 69.

63 = 3 \times 21. Composite.
65 ends in 5: 65 = 5 \times 13. Composite.
69 = 3 \times 23. Composite.
61: 61 \div 3 = 20 \text{ R } 1, it does not end in 0 or 5, and 61 \div 7 = 8 \text{ R } 5. Prime.
67: 67 \div 3 = 22 \text{ R } 1, it does not end in 0 or 5, and 67 \div 7 = 9 \text{ R } 4. Prime.

The tray can hold 61 or 67 seedlings.

Example 7

Why four tests are enough

Ulrikke picks a whole number from 2 to 100. She divides it by 2, by 3, by 5 and by 7, and each division leaves a remainder. Explain why her number must be prime. Then check the idea on 71.

Solution

Suppose her number were composite. Then it would have a factor pair a \times b where neither number is 1. Let a be the smaller of the two. Then a \times a is no more than her number, which is at most 100, and 10 \times 10 = 100, so a is one of 2 to 10.

If a were 2, 3, 5 or 7, that division would have left remainder 0. It did not.
If a were 4, 6, 8 or 10, then a is 2 times a whole number, so the number a \times b is 2 times a whole number too, and dividing by 2 would have left remainder 0. It did not.
If a were 9 = 3 \times 3, dividing by 3 would have left remainder 0. It did not.

Every choice of a is ruled out, so no such pair exists and her number is prime. (Her number cannot be 2, 3, 5 or 7 itself, since each of those divides itself with remainder 0.)

Check on 71: it is odd, 71 \div 3 = 23 \text{ R } 2, it does not end in 0 or 5, and 71 \div 7 = 10 \text{ R } 1. All four leave a remainder, so 71 is prime, as the argument says.

Boundaries

Only whole numbers greater than 1 are sorted. The number 1 has one factor and is neither prime nor composite. The number 0 is left out as well: every whole number from 1 up divides 0, so 0 has no end to its factors and fits neither definition.
Factors must be whole numbers. \displaystyle 13 = 2 \times 6\frac{1}{2}, but 2 is not a factor of 13: 13 \div 2 = 6 \text{ R } 1. Half a seedling does not make a row.
“Passes” means “is more than”. For 25 the tests cannot stop at 4: 5 \times 5 = 25 is equal to the number, not more, so 5 must still be tested, and it divides. Stopping before that would call a composite number prime.
The four tests 2, 3, 5, 7 are for numbers up to 100. For bigger numbers the stopping point moves on, and more primes must be tested. For example, 11 \times 17 = 187 passes all four tests and is still composite.
One factor pair proves composite; only a finished search proves prime. Finding 3 \times 17 settles 51 at once. Calling a number prime needs every test up to the stopping point.

Where this goes next

Once you can test one number, The sieve of Eratosthenes finds all the primes up to a chosen number at once, by crossing out multiples (the lists of Listing multiples). A composite number can be broken into factors, and those factors broken again, until only primes are left: that is Prime factorization. However the breaking is done, the same primes come out, which is Every number has exactly one prime factorization. Primes never run out, however far you count, and There are infinitely many primes shows why.

Exercises

Exercises 1 to 11 go with Part 1, and 12 to 21 with Part 2. The reasoning group draws on both.

Part 1: one row, or more than one way

List the factors of 46. Is 46 prime or composite?
List the factors of 45. Is 45 prime or composite?
List the factors of 31. Is 31 prime or composite?
List the factors of 48. How many are there, and is 48 prime or composite?
Sumaq plants 38 seedlings in 2 rows of 19. What does that one rectangle tell you about 38?
Pranav has 43 seedlings. Show that the only way to plant them in equal rows is one long row (or that row turned). What kind of number is 43?
Sort each number as prime, composite or neither: 1, 9, 11, 15, 19.
List every prime number from 1 to 20.
Find every whole number less than 30 that has exactly 3 factors.
Ulrikke says, “1 is prime, because its only factors are 1 and itself.” What is wrong with her reasoning?
A tray of seedlings can be planted in exactly 3 equal rows with none left over. Could the number of seedlings be prime? If so, what must it be?

Part 2: deciding prime or composite up to 100

Is 53 prime? Say where you can stop testing.
Is 93 prime or composite?
Is 79 prime? Say which tests you need.
Is 95 prime or composite?
Find all the primes from 40 to 50.
Is 73 prime? Say which tests you need.
Pranav says 86 might be prime, because 3 and 5 do not divide it. Is he right?
Which numbers from 90 to 100 are prime?
Sumaq wants a tray with between 80 and 90 seedlings that can only be planted in one long row. Which numbers could she choose?
Ulrikke tests 49 with 2, 3 and 5. None divides it, and she says 49 is prime, since “5 \times 5 is close to 49”. Is she right? Where should she have stopped?

Reasoning

Explain why 2 is the only even prime.
Explain, using arrays of seedlings, why a prime number of seedlings can only be planted as one row or that row turned.
Pranav says that to decide whether a number up to 100 is prime, there is no need to test 4, 6, 8 or 9. Explain why he is right.
Sumaq says, “If a number ends in 1, 3, 7 or 9, it is prime.” Show she is wrong, and explain what the last digit can and cannot tell you.

Answers

1, 2, 23, 46. Composite: 46 = 2 \times 23 is a pair other than 1 \times 46.
1, 3, 5, 9, 15, 45. Composite, from the pairs 3 \times 15 and 5 \times 9.
1, 31. Prime: 2, 3, 4, 5 all leave remainders (31 \div 4 = 7 \text{ R } 3, for example), and 6 \times 6 = 36 passes 31.
1, 2, 3, 4, 6, 8, 12, 16, 24, 48: ten factors, from 1 \times 48, 2 \times 24, 3 \times 16, 4 \times 12, 6 \times 8. Composite.
38 is composite. The rectangle shows 38 = 2 \times 19, so 2 and 19 are factors besides 1 and 38.
43 \div 2 = 21 \text{ R } 1, 43 \div 3 = 14 \text{ R } 1, 43 \div 4 = 10 \text{ R } 3, 43 \div 5 = 8 \text{ R } 3, 43 \div 6 = 7 \text{ R } 1, and 7 \times 7 = 49 passes 43. The only pair is 1 \times 43, so 43 is prime.
1 is neither; 11 and 19 are prime; 9 = 3 \times 3 and 15 = 3 \times 5 are composite.
2, 3, 5, 7, 11, 13, 17, 19: eight primes. Every other number from 4 to 20 has a pair such as 2 \times 2, 3 \times 3 or 3 \times 5.
4, 9 and 25. Their factors are 1, 2, 4 and 1, 3, 9 and 1, 5, 25. Each is a prime times itself; the next one, 7 \times 7 = 49, is past 30.
“1 and itself” are the same number when the number is 1, so 1 has only one factor. A prime must have exactly two different factors.
Yes, but only 3: 3 rows of 1. Any other number of seedlings in 3 equal rows has 3 as a factor besides 1 and itself, so it is composite.
Prime. Stop after 7, since 8 \times 8 = 64 passes 53. It is odd, 53 \div 3 = 17 \text{ R } 2, it does not end in 0 or 5, and 53 \div 7 = 7 \text{ R } 4.
Composite: 93 = 3 \times 31.
Prime. Tests 2, 3, 5, 7, since 9 \times 9 = 81 passes 79. It is odd, 79 \div 3 = 26 \text{ R } 1, it does not end in 0 or 5, and 79 \div 7 = 11 \text{ R } 2.
Composite: it ends in 5, and 95 = 5 \times 19.
41, 43, 47. The even numbers are out, 45 = 5 \times 9 and 49 = 7 \times 7. For the other three, 7 \times 7 = 49 passes them, so 2, 3, 5 are enough, and none divides (41 \div 3 = 13 \text{ R } 2, 43 \div 3 = 14 \text{ R } 1, 47 \div 3 = 15 \text{ R } 2).
Prime. Tests 2, 3, 5, 7, since 9 \times 9 = 81 passes 73. It is odd, 73 \div 3 = 24 \text{ R } 1, it does not end in 0 or 5, and 73 \div 7 = 10 \text{ R } 3.
No. 86 is even and bigger than 2, so it is composite: 86 = 2 \times 43.
Only 97. The evens are out, 91 = 7 \times 13, 93 = 3 \times 31, 95 = 5 \times 19 and 99 = 9 \times 11. For 97: odd, 97 \div 3 = 32 \text{ R } 1, no 0 or 5 at the end, and 97 \div 7 = 13 \text{ R } 6.
83 or 89, the primes from 80 to 90. The others: 81 = 9 \times 9, 85 = 5 \times 17, 87 = 3 \times 29, and the evens. For 83, 83 \div 3 = 27 \text{ R } 2 and 83 \div 7 = 11 \text{ R } 6; for 89, 89 \div 3 = 29 \text{ R } 2 and 89 \div 7 = 12 \text{ R } 5.
No. 5 \times 5 = 25 does not pass 49, and neither does 6 \times 6 = 36 or 7 \times 7 = 49, which only equals it. She must test 7, and 49 = 7 \times 7, so 49 is composite. The first place she may stop is 8, since 8 \times 8 = 64 passes 49.
Every even number is 2 times a whole number, so 2 is a factor of it. For an even number bigger than 2, the numbers 1, 2 and the number itself are three different factors, so it is composite. Only 2 is left, and its factors are just 1 and 2.
Any rectangle of seedlings with r rows and c in each row gives the factor pair r \times c. A prime has only the factors 1 and itself, so the only pairs are 1 \times n and n \times 1: one row of all the seedlings, or that row turned to stand one seedling per row.
Each of those numbers is a product of smaller primes: 4 = 2 \times 2, 6 = 2 \times 3, 8 = 2 \times 2 \times 2, 9 = 3 \times 3. If 4, 6 or 8 divided the number, then 2 would too, and if 9 divided it, 3 would too. So the tests for 2 and 3 would already have found a factor.
21 = 3 \times 7 ends in 1 and 49 = 7 \times 7 ends in 9, yet both are composite. The last digit settles only the tests for 2 and 5: a number ending in 0, 2, 4, 6, 8 has 2 as a factor, and one ending in 0 or 5 has 5. It says nothing about 3 or 7.