Claims and counterexamples

The idea

A statement or claim made without proof or verification is a conjecture; a case for which the conjecture is false is a counterexample, and finding one disproves the conjecture.

Anshu’s claim

After looking at a few prime factorisations, Anshu says: “The larger a number is, the longer its prime factorisation will be.”

For example, 6 = 2 × 3 has two primes, and the bigger number 12 = 2 × 2 × 3 has three.

What do you think of Anshu’s claim?

• It is always true
• It is sometimes false
• We cannot tell without more tests

Test the claim

Pick two numbers. The bigger one should have the longer factorisation. Test some pairs and look for one where it does not.

A conjecture and a counterexample

Anshu’s claim is true for pairs like 6 and 12, 8 and 16, 12 and 24. But look at these two:

121 is bigger than 96, but its factorisation is shorter. The claim is false.

A statement or claim made without proof or verification is a conjecture. A case for which the conjecture is false is a counterexample. Finding one counterexample disproves the conjecture. Many cases that agree do not prove it.

• Number | Prime factorisation | Primes
• 96 | 2 × 2 × 2 × 2 × 2 × 3 | 6
• 121 | 11 × 11 | 2

Notes

A statement made without proof or verification is a conjecture. A case where it is false is a counterexample, and finding one disproves the conjecture.

Check yourself

Claim: “every number that is divisible by 3 is odd.” Which number is a counterexample?

Claim: “every prime number is odd.” It is true for 3, 5, 7, 11, 13, … Find the counterexample: which prime number is even?

Answer: 2

2 is a prime (its only factors are 1 and 2) and it is even. So the claim is false.

Ria tests a claim on 50 different cases and it holds every time. What can she say?

Claim: “every number divisible by 6 is divisible by 12.” What is the smallest counterexample?

Answer: 6

6 is divisible by 6 but not by 12. So 6 is a counterexample, and the claim is false.

• 5. 5 is not divisible by 3, so the claim says nothing about it.
• 6 — correct. Yes! 6 is divisible by 3 but it is even, so the claim fails for 6.
• 9. 9 is divisible by 3 and odd. It agrees with the claim, so it is not a counterexample.
• Her claim is a conjecture, still unproved. One counterexample could still be out there. — correct. Yes! Many agreeing cases do not prove it. Only a proof, or one counterexample, settles it.
• Her claim is now proved.. Fifty cases are still only fifty cases. There may be a case that breaks the claim.
• Her claim must be false.. Not necessarily. It may be true; she just has not proved it.