A Number That Passed the Test

Timur is checking whether the number 341 is prime. In a book he found a way: raise two to the power one less than the number under check and look at the division remainder. He computes the remainder of 2³⁴⁰ divided by 341. It comes out as one.

“Prime,” says Timur.

Dana writes in the margin:

341 = 11 × 31.

“And what do we do with that?”

Timur rechecks the remainder. All correct: one. Dana’s product is correct too. They will have to revisit how Timur reached his conclusion.

What the theorem promises

A prime is a natural number above one with only two positive divisors: one and itself. If a number above one has other positive divisors, it is composite.

Timur’s check rests on Fermat’s little theorem. First take it apart on small numbers. Take the prime 7 and base 2 — the number to raise. The exponent is one less than seven, that is six:

2⁶ = 64 = 9 × 7 + 1.

Sixty-four holds nine sevens, with one left over. That is the division remainder.

The theorem states: if p is prime, and an integer a is not divisible by p, then a to the power p − 1 leaves remainder 1 on division by p. Our example fits it: seven is prime, two is not divisible by seven, the remainder is one.

In the check we pick a base above one but below the number under check. If that number is prime, the theorem’s condition holds and the remainder must equal 1.

The direction here is fixed: knowing the number is prime, we can predict the remainder. Concluding from the remainder that the number is prime takes a separate ground.

A right remainder, a wrong conclusion

For 341 Timur’s result can be checked without writing out the huge number 2³⁴⁰. It suffices to notice:

2¹⁰ = 1024 = 3 × 341 + 1.

So 2¹⁰ leaves remainder 1 on division by 341. When numbers, each one more than some multiple of 341, are multiplied, the product leaves remainder 1 too. And 2³⁴⁰ is a product of thirty-four factors of 2¹⁰. The remainder truly is one.

At this point Timur took an extra step: “Primes pass the check. My number passed it. So it is prime.”

The theorem allows no such move. It resembles the reasoning “if it rained, the road is wet; the road is wet — so it rained”. But the road may have been watered. One same observation fits different explanations.

Dana’s note shows this with no analogies. Eleven exceeds one, is less than 341, and divides it with no remainder. So 341 is composite. That conclusion needs only the equality 11 × 31 = 341. No need to separately prove both factors prime.

The base-2 check is passed, and the number is composite. These facts do not contradict each other. They refute the attempt to reverse the theorem, not the theorem itself: it never claimed a composite number could never yield remainder 1.

What another base changes

“Maybe two is unlucky?” Timur asks.

Try three. The remainder of 3³⁴⁰ divided by 341 is 56. No one this time.

Had 341 been prime, with the picked base the theorem would have had to yield remainder 1. A different number came out. So 341 is not prime. That is one more proof of compositeness, needing no knowledge of the factors 11 and 31.

Now the difference between the check’s two outcomes shows. With its conditions met, a remainder other than 1 lets us reject primality. Remainder 1 establishes a narrower fact: the number passed the test for the given base. That is not enough to decide whether it is prime or composite.

It would be wrong to say a passed check reported nothing at all. We learned a property of the number for sure. The mistake starts when that property is taken for another, stronger one.

And switching bases does not always help. For example, 561 = 3 × 11 × 17 passes the Fermat test for every base coprime to 561. “Coprime” means the two numbers share no positive divisor but one.

So trying only such bases will never expose 561’s compositeness. The hedge cannot be dropped: three, for instance, itself divides 561, and with base 3 no one results. There are other primality checks besides. The Fermat test’s limit does not become a limit of all arithmetic.

Checking the check itself

So far we took the remainders to be computed right. But that too needs establishing. For large powers it is handy to count step by step, keeping only the remainder after each multiplication. On division by 341 such remainders lie between 0 and 340, though intermediate products may run larger.

A long entry invites mistakes. Write, say, that the remainder for 2⁵ is 33, though 2⁵ = 32. Later steps may look neat and still rest on a wrong link. One plausible answer at the end is not enough to count the whole calculation correct.

But checking arithmetic is only one task. There is also checking the reasoning’s completeness. We need to make sure it starts from true initial data and reaches exactly the power whose remainder we want to know. Several correct lines by themselves do not guarantee that.

A skipped line need not mean a mistake: the author may have cut an obvious move. What matters is whether that move can be grounded. Our short computation through 2¹⁰ is complete, though it does not write out every intermediate power. And a long table of remainders may hold a gap that keeps the conclusion from being checked.

Such work can be handed to a program, if it checks both the moves’ rightness and that the whole chain leads to the stated result. The mere absence of errors found does not yet mean the check is complete.

Finally, even a flawless remainder computation will not fix Timur’s logical mistake. Checking the calculation and establishing what follows from it are two separate tasks.

What we learned about the number

Timur crosses out the word “prime” and writes: “Passed the Fermat test for base 2.”

“Now that is right,” says Dana.

Beside it stays her entry: 341 = 11 × 31. It answers the question Timur asked at the start: the number is composite.

We got several exact results. The base-2 remainder is 1. The base-3 remainder is 56. The number has the divisor 11. Each result has its ground, and we need to understand which claim it lets us make.

This chapter ends the third part. The formula needed conditions, the geometrical theorem the right conclusion direction, and the numerical check an understanding of what its result means. In all three cases a pretty answer was too little: we had to trace why it follows from what is given.

Next we turn to claims that must be revised as new information arrives. What exactly changes then: the object itself, the conditions, or our understanding?