Sometimes we need to show that a claim is false. This can be done by finding a **counterexample**. Consider any claim of the form: . To show that the claim is false, we need to find a value of for which is true and is false.

That is, we need to prove the negation of the above claim: . Finding any that supports the negation of the original claim is sufficient to disprove it.

**Example**

Disprove the following claim.

**Claim**:

**Counterexample**: We need to show that

A good idea is to try typical edge values, such as 1.

Let .

When , .

Thus disproving the original claim.

Of course, it is unusual to disprove a claim on the first attempt. If an inspection of the problem and some back-of-the-envelope calculations do not pan out, you may want to write a program to search for a counterexample.

A **Fermat Number** is a number of the form: **f(x) = **. Fermat numbers were first studied by mathematician Pierre de Fermat, who conjectured that all Fermat numbers are prime. Let’s try to disprove his conjecture claim.

**Claim**:

**Counterexample**: We need to show that

A good idea is to try typical edge cases such as and .

Prime? |
||
---|---|---|

0 |
3 |
✔ |

1 |
5 |
✔ |

That didn’t work, so let’s write a program to systematically try all values of *x* to see if there is break in the pattern.

First, we need a way to determine if is prime. Let’s write a method that returns the first prime divisor of a given number *m*. If the first prime divisor of the number *m* equals *m*, then the number *m* is prime.

public static BigInteger primeDivisor(BigInteger n ) { // All primes are greater than 1 if ( n.compareTo( BigInteger.ONE ) <= 0 ) return BigInteger.valueOf( -1L ); // 2 is the only even prime if ( n.mod( BigInteger.valueOf( 2L ) ) .compareTo( BigInteger.ZERO ) == 0 ) return BigInteger.valueOf( 2L ); // Check for divisibility for( BigInteger i = BigInteger.valueOf( 3L ); i.pow( 2 ).compareTo( n ) <= 0; i = i.add( BigInteger.valueOf( 2L ) ) ) { // Does i divide n? if ( n.mod( i ).compareTo(BigInteger.ZERO) == 0 ) return i; // n is not prime } return n; // n is prime }

We use BigInteger values because the value of will get large very quickly and exceed the maximum number that can be stored in a long

**The BigInteger Data Type**

The BigInteger class is used for mathematical operations which involve very large numbers that are outside the limit of all available primitive data types. For integers, this means numbers smaller than -9223372036854775808 or larger than 9223372036854775807, which are Long.MIN_VALUE and Long.MAX_VALUE, respectively.

*x*starting with 0. Well, not all values of

*x*. We will stop when x is 30 to avoid integer overflow. Placing such a boundary on the search is pragmatic and recognizes that we may not be able to identify a counterexample with our available computing resources.

// Print the header row System.out.printf("%2s %-10s prime?%n", "x", "f(x)" ); // stop at x = 30 to prevent integer overflow for( int x = 0; x <= 30; x++ ) { BigInteger result = BigInteger.valueOf( 2L ) .pow( (int) Math.pow( 2, x ) ) .add( BigInteger.ONE); System.out.printf("%2d %-10s ", x, result ); BigInteger divisor = primeDivisor( result ); if ( divisor != result ) { // result is not prime System.out.printf("No: Divisible by %d%n", divisor ); break; } // result is prime System.out.println( "Yes" ); }

Prime? |
||
---|---|---|

0 |
3 |
Yes |

1 |
5 |
Yes |

2 |
17 |
Yes |

3 |
257 |
Yes |

4 |
65537 |
Yes |

5 |
4294967297 |
No! Divisible by 641 |

When , is not prime. Thus disproving the original claim.

We are in good company. The conjecture was originally refuted by Leonhard Euler in 1732, but he had to do the calculations by hand.