Primes and Composites: Free Response

A factor of a number divides it with remainder $0$, and factors come in pairs: each one you find hands you its partner, since the two multiply back to the number. So the whole list can be built by testing only the small candidates and writing down both members of every pair as it appears.

For $68$, test candidates while the candidate multiplied by itself has not passed $68$:

$8 \times 8 = 64 \le 68, \qquad 9 \times 9 = 81 > 68,$

so $1$ through $8$ is the entire search. Of those, $1$ divides (partner $68$), $2$ divides because the number is even (partner $34$), and $4$ divides (partner $17$). The candidate $3$ fails the digit-sum test, since $6 + 8 = 14$, and $5$, $6$, $7$ and $8$ each leave a remainder. Collecting both members of every pair,

$68 = 1 \times 68 = 2 \times 34 = 4 \times 17,$

which gives the six distinct factors $1, 2, 4, 17, 34, 68$.

For $62$ the boundary sits lower:

$7 \times 7 = 49 \le 62, \qquad 8 \times 8 = 64 > 62,$

so the search is $1$ through $7$. Only $1$ (partner $62$) and $2$ (partner $31$) divide, giving

$62 = 1 \times 62 = 2 \times 31,$

and the four distinct factors $1, 2, 31, 62$.

Now read the counts against the definition. Six is more than two and four is more than two, so both numbers land in the same group. The two counts are quite different and the definition does not care: it asks only whether the count is exactly two or more than two, never how much more.

Run the quick tests in order before dividing anything. The number is odd, so $2$ is out, and it does not end in $0$ or $5$, so $5$ is out. That leaves the digit-sum rule for $3$:

$1 + 2 + 9 = 12,$

and $12$ is a multiple of $3$, so $3$ divides $129$. One division hands over the partner:

$129 \div 3 = 43, \qquad \text{so} \qquad 129 = 3 \times 43.$

Neither $3$ nor $43$ is $1$ or $129$, so the number has a factor beyond the two that every whole number greater than $1$ is forced to have. Its factor list therefore holds at least $1$, $3$, $43$ and $129$, which is more than two distinct factors, and more than two is the definition of composite.

That is why a single pair finishes the job. The definition does not ask how many extra factors there are or what they all are; it asks only whether the count gets past two. As soon as one extra factor is on the table the count is past two, so no further candidate has to be divided and no further factor has to be listed.

Compare what the two words are actually asking for.

Composite asks for more than two distinct factors, which is a claim that something exists: somewhere among the whole numbers there is a factor of the number that is neither $1$ nor the number itself. A claim that something exists is settled by producing it, once. In part B the pair

$129 = 3 \times 43$

does exactly that, and the search can stop there. Whether the number turns out to have four factors or forty makes no difference to the classification.

Prime asks for exactly two distinct factors, which is a claim that something does not exist: there is no factor besides $1$ and the number itself, anywhere. A claim that nothing of a certain kind exists is not settled by failed searches, however many. The next candidate you have not tried could still be the one that divides, so ten failed divisions and a hundred failed divisions carry the same weight, which is none, for as long as untested candidates remain.

What repairs it is a reason to stop: an argument that the candidates you did not test could not have worked. That is what the stopping rule supplies. Once a candidate multiplied by itself has passed the number, every remaining candidate is too large to be the smaller member of a factor pair, so the failed divisions turn into a finished search instead of an abandoned one. Only then do they establish that the number is prime.

Start where both definitions start, with the factor list. A factor of $1$ is a whole number that divides $1$ with remainder $0$. Only $1$ does: $1 \div 1 = 1$ exactly, and every whole number larger than $1$ is already bigger than $1$, so it must leave a remainder. The complete list is therefore

$\{1\},$

a list with one member.

Now hold that count against each definition in turn.

Prime requires exactly two distinct factors, $1$ and the number itself. For the number $1$, those two descriptions name the same number, so they collect into a single entry rather than two. One is not two, so $1$ is not prime.

Composite requires more than two distinct factors. One is fewer than two, not more, so $1$ is not composite either.

Nothing was chosen anywhere in that. Both definitions are conditions on a single count, the count is $1$, and $1$ satisfies neither condition. So $1$ sits outside both groups, and that is exactly why the classification is stated for whole numbers greater than $1$. There is a payoff further on as well: a building block that could be glued onto a product any number of times without changing it would not be much of a building block.

Take $n$ even and greater than $2$, with nothing else assumed about it.

Being even is precisely what the divisibility rule for $2$ detects: the last digit is $0$, $2$, $4$, $6$ or $8$, and $2$ divides the number. So $2$ is a factor of $n$.

Every whole number greater than $1$ already carries $1$ and itself on its factor list, so the list of $n$ contains $1$, $n$ and $2$. The question is whether that is genuinely three entries, or whether $2$ has been counted twice under another name.

It has not. The factor $2$ is not $1$, since $2 \ne 1$. And $2$ is not $n$, since $n$ was taken greater than $2$. The three entries are distinct, so

$\text{count of distinct factors of } n \ge 3.$

More than two distinct factors is the definition of composite, so every even $n$ greater than $2$ is composite and none of them is prime. Since $2$ itself has exactly the two factors $1$ and $2$, it is prime, and it is the only even number that can be.

Notice what the argument never did. It never used the size of $n$, never carried out a division, and never looked at a particular number, so it settles every even number past $2$ in one stroke: $94$, $488$ and an even number a hundred digits long are all covered by the same three lines. That is the difference between checking examples and establishing a statement about all of them.

The student's first sentence is true, and part B is the reason: every even number past $2$ is composite, so the primes past $2$ all have to be odd. The trouble is in the second sentence, where that statement gets read backwards.

"Every prime greater than $2$ is odd" and "every odd number greater than $1$ is prime" are different claims. The first says the primes sit inside the odd numbers. The second says the odd numbers sit inside the primes. Turning a statement around like this produces its converse, and a converse is a new claim that has to be tested on its own account; it never comes free with the original.

So test it. Take $119$. It is odd, so the student's rule calls it prime. But

$119 = 7 \times 17,$

so besides $1$ and $119$ the factor list also holds $7$ and $17$. That is more than two distinct factors, which makes $119$ composite, and one number like this is enough to retire the rule for good.

What does being odd actually buy, then? Exactly one thing: an odd number has no factor of $2$. That clears a single candidate divisor, the very first one, and says nothing whatever about $3$, $5$, $7$, $11$ and the rest, which is why the testing carries on past $2$ instead of stopping there. Odd is a filter, not a verdict.

An arrangement of $r$ rows holding $c$ seedlings each uses $r \times c$ seedlings altogether, so the grower is asking for a factor pair of $319$ in which neither member is $1$. That is the same search as looking for a factor other than $1$ and the batch size.

Run the quick tests first. The batch size is odd, so $2$ is out. Its digit sum is $3 + 1 + 9 = 13$, not a multiple of $3$, so $3$ is out. It does not end in $0$ or $5$, so $5$ is out. That leaves division. Trying $7$,

$319 \div 7 = 45 \text{ remainder } 4,$

so $7$ is out too. Trying $11$,

$319 \div 11 = 29 \text{ exactly}, \qquad \text{so} \qquad 319 = 11 \times 29.$

Neither member of that pair is $1$, so it describes a usable tray: $11$ rows with $29$ seedlings in each. Turning the tray a quarter turn gives $29$ rows of $11$, which is the same pair read the other way round. Either way every row is full and nothing is left over.

Search the same way. The batch size is odd, so $2$ fails. Its digit sum is $1 + 3 + 7 = 11$, not a multiple of $3$, so $3$ fails. It does not end in $0$ or $5$, so $5$ fails. That leaves two divisions:

$137 \div 7 = 19 \text{ remainder } 4, \qquad 137 \div 11 = 12 \text{ remainder } 5.$

The next candidate is $13$, and here the stopping rule decides. Test candidates only while the candidate multiplied by itself has not passed the number:

$11 \times 11 = 121 \le 137, \qquad 13 \times 13 = 169 > 137.$

The first comparison says $11$ was still obliged; the second says $13$ may be skipped, and so may every candidate above it. Five candidates in all, three of them settled at a glance, and the search is complete rather than abandoned.

Nothing divides $137$ except $1$ and $137$, so there is no factor pair with both members above $1$. Every tray for this batch is a single row of $137$, or $137$ rows with one seedling in each, and both are what the grower ruled out. This batch cannot be set out as asked.

A claim of the form "exactly when" is two claims, and both have to be argued. Checking one and assuming the other is how a plausible rule turns out to be half right.

First direction: composite gives a tray. Let $n$ be composite. By definition it has more than two distinct factors, so beyond $1$ and $n$ there is some factor $d$ with

$1 < d < n.$

Dividing gives its partner $c = n \div d$, so that $n = d \times c$. That partner is above $1$ as well, because if $c$ were $1$ then $n = d$, and $d$ was taken strictly below $n$. So $d$ rows of $c$ seedlings is a legal tray, with more than one row and more than one seedling in each.

Second direction: a tray gives composite. Suppose the grower has laid out $r$ rows of $c$ seedlings, with $r > 1$ and $c > 1$ and every seedling used. Then $n = r \times c$, so $r$ is a factor of $n$. It is not $1$, since $r > 1$. It is not $n$ either: if $r$ were $n$ then $c$ would have to be $1$, and $c$ was taken above $1$. So $r$ is a third distinct factor beside $1$ and $n$, and $n$ is composite.

Both directions hold, so the claim is correct as stated, and the two batches above are the two cases in action. The word "exactly" is what makes the second argument necessary. Had only the first direction been checked, the rule would have looked fine on every example anyone tried, and it would still have been an unproved guess in precisely the direction the grower cares about: the direction that says when a batch cannot be arranged.

The rule is to keep testing candidate divisors $d$ while $d \times d$ has not passed the number, and to stop as soon as it has. So locate the boundary before dividing anything:

$13 \times 13 = 169 \le 173, \qquad 17 \times 17 = 289 > 173.$

The first comparison says $13$ is still inside the range and has to be tested. The second says $17$ is outside it and may be skipped, and so may every candidate above $17$. The obliged list is therefore

$2, \quad 3, \quad 5, \quad 7, \quad 11, \quad 13,$

six candidates. Three of them cost nothing at all: $173$ is odd, its digit sum $1 + 7 + 3 = 11$ is not a multiple of $3$, and it does not end in $0$ or $5$. Only three divisions are actually needed, and none of them comes out clean:

$173 \div 7 = 24 \text{ r } 5, \qquad 173 \div 11 = 15 \text{ r } 8, \qquad 173 \div 13 = 13 \text{ r } 4.$

Now the comparison asked for. Testing every whole number from $2$ up to $172$ would be $171$ divisions. The rule replaces those $171$ with six candidates, of which three are settled by a glance at the digits. That is the difference between a method that can be worked on paper and one that cannot, and every bit of it is bought by the argument in part B.

Call a candidate $d$ inside the boundary when $d \times d$ has not passed the number $n$, and outside it when $d \times d > n$. The rule tests everything inside and skips everything outside, so the whole question is whether anything can hide outside.

Start from what a factor is. If $d$ divides $n$, the division leaves a whole number $e$ with

$n = d \times e,$

so factors never arrive alone: each comes with a partner, and finding either one finds the other.

Now take any factor pair of $n$, call the smaller member $d$ and the larger $e$, so that $d \le e$. Multiplying both sides of $d \le e$ by $d$ keeps the comparison the right way round, because $d$ is a positive whole number:

$d \times d \le d \times e = n.$

So the smaller member of every factor pair is inside the boundary. Always, with no cases left to check. Read the other way round, the same line says the two members cannot both be outside it, since their product would then overshoot $n$.

Put that to work. Suppose $n$ has a factor $f$ other than $1$ and $n$, and let $g = n \div f$ be its partner. That partner is above $1$, because if $g$ were $1$ then $n = f$, and $f$ is not $n$. Neither member is $n$ either, since if one of them were $n$ the other would have to be $1$. So the pair $f$ and $g$ has both members strictly between $1$ and $n$. Call the smaller of the two $d$. Then $d$ is a factor of $n$ that is neither $1$ nor $n$, and by the line above it is inside the boundary, so trial division meets it before the stop.

Turn that around and the rule falls out. If every candidate inside the boundary has been tested and none divided $n$, then $n$ has no factor other than $1$ and itself at all, so it is prime. The candidates outside the boundary need no testing, because a factor found out there would have a partner inside, and that partner has already been tried and rejected.

Read the rule off exactly as it is stated: keep testing candidates $d$ while $d \times d$ has not passed $n$, and stop only once $d \times d$ passes $n$, which means strictly greater. The student has quietly replaced "greater than" with "greater than or equal to". At almost every number that substitution makes no difference at all, and at this one it makes the whole difference.

Do the multiplication the student skipped:

$23 \times 23 = 529.$

That is not greater than $529$; it lands on it. So the stopping condition was never met, $23$ was still an obliged candidate, and the search was abandoned one candidate early. Testing it,

$529 \div 23 = 23 \text{ exactly}, \qquad \text{so} \qquad 529 = 23 \times 23.$

The number therefore carries $23$ on its factor list besides $1$ and $529$: three distinct factors, more than two, so $529$ is composite.

It is worth seeing why the boundary case is the dangerous one rather than a technicality. Part B showed that the smaller member $d$ of a factor pair always satisfies $d \times d \le n$. Equality there happens exactly when the pair has two equal members, and the numbers whose only extra factor sits precisely on the boundary are the primes multiplied by themselves, of which this is one. Stop at "greater than or equal to" and that whole family is misreported as prime, every single time. The student's eight divisions were all correct; the ninth was the one that mattered.

Write $2$ through $60$ and take the passes in order.

The smallest number not crossed out is $2$, so circle it and cross out $4, 6, 8, \ldots, 60$: every even number above $2$ goes. The smallest survivor is now $3$; circle it and cross out its larger multiples, of which $9, 15, 21, 27, 33, 39, 45, 51$ and $57$ were still standing. The next survivor is $5$; circle it and cross out $25$, $35$ and $55$, since $10, 20, 30, 40, 50$ and $60$ went with the even numbers and $15$ and $45$ went with the multiples of $3$. The next survivor is $7$; circle it and cross out $49$, the only multiple of $7$ in range that has escaped so far.

The next survivor is $11$, and

$11 \times 11 = 121 > 60,$

so the crossing out is finished and everything still standing is prime. Circle those survivors as well, which is the last step of the method, and read the circles off in order,

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59.$

That is seventeen primes up to $60$.

The passes are made by the circled numbers in turn, and the stopping rule is what decides how many are needed.

Here is why they are allowed to stop. Suppose every circled number up to $p$ has had its pass, and suppose $p \times p$ has passed the limit. Take a number $n$ still standing, and suppose it were composite. Let $d$ be the smallest factor of $n$ above $1$. Its partner $n \div d$ is a factor above $1$ as well, and $d$ is the smallest of those, so $d$ is no larger than its partner and therefore $d \times d \le n$. That $d$ is itself prime, because a factor of $d$ other than $1$ and $d$ would divide $n$ as well and would be smaller than $d$, and $d$ was the smallest such factor of $n$. Could $d$ be one of the numbers whose pass has already run? No: such a pass crosses out every larger multiple of its own number, and $n$ is a larger multiple of $d$, so $n$ would be gone. Every pass so far was made by a number at or below $p$, so $d > p$. Now the two facts collide:

$d \times d \le n \le \text{limit} < p \times p,$

which forces $d < p$. So nothing left standing can be composite, and the passes are finished.

For the limit $60$:

$7 \times 7 = 49 \le 60, \qquad 11 \times 11 = 121 > 60.$

So the passes with $2$, $3$, $5$ and $7$ are all required, and the pass with $11$ is not. It would cross out nothing new, because the smallest multiple of $11$ that escapes every earlier pass is $11 \times 11 = 121$, which is off the end of the list.

For a limit of $130$ the same comparison moves along one place:

$11 \times 11 = 121 \le 130, \qquad 13 \times 13 = 169 > 130.$

Now the pass with $11$ is required, since $121$ is on the longer list and no earlier pass touches it, while the pass with $13$ is still unnecessary. Each time the limit reaches a circled number multiplied by itself, exactly one more pass joins the work.

After the passes with $2$, $3$ and $5$, everything still standing has no factor of $2$, $3$ or $5$. The student reads that as "nothing composite is left", but the stopping rule says the work is not over:

$7 \times 7 = 49 \le 60,$

and the rule licenses a stop only once the circled number multiplied by itself has passed the limit. Since $49$ has not passed $60$, the pass with $7$ is still owed.

What would that pass remove? The multiples of $7$ up to $60$ are $14, 21, 28, 35, 42, 49$ and $56$, and all but one has already gone: $14$, $28$, $42$ and $56$ with the multiples of $2$, $21$ with the multiples of $3$, and $35$ with the multiples of $5$. What survives is

$49 = 7 \times 7,$

so the student's list wrongly keeps exactly one number, and it is composite.

Why exactly one, and not two or five? A composite that survives the passes with $2$, $3$ and $5$ has no factor of $2$, $3$ or $5$, so the smaller member of its factor pair is $7$ or more, and its partner is at least as large again. The smallest numbers of that shape are

$7 \times 7 = 49 \qquad \text{and then} \qquad 7 \times 11 = 77.$

The second is already past $60$, so under this limit there is room for one such number and no more. Push the limit up and that count changes, which is exactly why the number of passes has to be worked out from the limit rather than remembered from the last time.