{"id":267,"date":"2018-03-12T23:14:19","date_gmt":"2018-03-12T23:14:19","guid":{"rendered":"http:\/\/loop.cs.mtu.edu\/?p=267"},"modified":"2023-10-31T00:21:52","modified_gmt":"2023-10-31T00:21:52","slug":"disproof-by-counter-example","status":"publish","type":"post","link":"https:\/\/loop.cs.mtu.edu\/index.php\/2018\/03\/12\/disproof-by-counter-example\/","title":{"rendered":"Disproof by Counter Example"},"content":{"rendered":"
\n

Sometimes we need to show that a claim is false. This can be done by finding a counterexample<\/strong>. Consider any claim of the form:\u00a0. To show that the claim is false, we need to find a value of\u00a0\"x\\in\u00a0for which\u00a0\"P_x\"\u00a0is true and\u00a0\"Q_x\"\u00a0is false.<\/p>\n

That is, we need to prove the negation of the above claim:\u00a0\"\\exists. Finding any\u00a0\"x\"\u00a0that supports the negation of the original claim is sufficient to disprove it. <\/p>\n<\/div>\n

\n

Example<\/strong><\/p>\n

Disprove the following claim.<\/p>\n

Claim<\/strong>: \"\\forall<\/p>\n

Counterexample<\/strong>:\u00a0We need to show that \"\\exists<\/p>\n

A good idea is to try typical edge values, such as 1.<\/p>\n

Let\u00a0\"x=y=1\".<\/p>\n

\"\\begin{array}{lcr}<\/p>\n

When \"x=y=1\",\u00a0\"(x+y)^{2}.
\nThus disproving the original claim.<\/p>\n<\/div>\n

\n

 <\/p>\n

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.<\/p>\n

A Fermat Number<\/strong> is a number of the form:\u00a0f(x) = \"2^{2^{x}<\/strong>. Fermat numbers were first studied by mathematician Pierre de Fermat, who conjectured\u00a0that all Fermat numbers are prime. Let’s try to disprove his conjecture claim.<\/p>\n

Claim<\/strong>: \"\\forall<\/p>\n

Counterexample<\/strong>:\u00a0We need to show that \"\\exists<\/p>\n

A good idea is to try typical edge cases such as \"x=0\"\u00a0and\u00a0\"x=1\".<\/p>\n\n\n\n\n\n
\"x\"<\/strong><\/th>\n\"2^{2^{x}<\/strong><\/th>\nPrime?<\/strong><\/th>\n<\/tr>\n
0<\/strong><\/td>\n3<\/strong><\/td>\n✔<\/strong><\/td>\n<\/tr>\n
1<\/strong><\/td>\n5<\/strong><\/td>\n✔<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

That didn’t work, so let’s write a program to systematically try all values of x<\/em> to see if there is break in the pattern.<\/p>\n

First, we need a way to determine if\u00a0\"2^{2^{x} is prime. Let’s write a method that returns the first prime divisor of a given number m<\/i>. If the first prime divisor of the number m<\/i> equals\u00a0m<\/i>, then the number m<\/i> is prime.<\/p>\n

public static BigInteger primeDivisor(BigInteger n ) {\n   \/\/ All primes are greater than 1 \n   if ( n.compareTo( BigInteger.ONE ) <= 0 )\n      return BigInteger.valueOf( -1L );\n   \/\/ 2 is the only even prime\n   if ( n.mod( BigInteger.valueOf( 2L ) )\n         .compareTo( BigInteger.ZERO ) == 0 ) \n      return BigInteger.valueOf( 2L ); \n   \/\/ Check for divisibility\n   for( BigInteger i = BigInteger.valueOf( 3L ); \n        i.pow( 2 ).compareTo( n ) <= 0; \n        i = i.add( BigInteger.valueOf( 2L ) ) ) {\n      \/\/ Does i divide n?\n      if ( n.mod( i ).compareTo(BigInteger.ZERO) == 0 ) \n         return i; \/\/ n is not prime\n    }\n    return n; \/\/ n is prime\n}<\/pre>\n
We use BigInteger<\/span> values because the value of \"2^{2^{x} will get large very quickly and exceed the maximum number that can be stored in a long<\/span><\/p>\n
The BigInteger Data Type<\/strong>
\nThe 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\u00a09223372036854775807, which are Long.MIN_VALUE and Long.MAX_VALUE, respectively.<\/div>\n
 <\/p>\n
Now we write code to exhaustively try all values of\u00a0x<\/em> starting with 0. Well, not all values of x<\/em>. 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.<\/div>\n
<\/div>\n
Let’s write the code to display each x and f(x) and indicate if f(x) is prime in a table.<\/div>\n<\/div>\n
\n
\/\/ Print the header row\nSystem.out.printf(\"%2s %-10s prime?%n\", \"x\", \"f(x)\" );\n\/\/ stop at x = 30 to prevent integer overflow\nfor( int x = 0; x <= 30; x++ ) {\n   BigInteger result = \n       BigInteger.valueOf( 2L )\n                 .pow( (int) Math.pow( 2, x ) )\n                 .add( BigInteger.ONE);\n   System.out.printf(\"%2d %-10s \", x, result );\n   BigInteger divisor = primeDivisor( result );\n   if ( divisor != result ) {\n      \/\/ result is not prime\n      System.out.printf(\"No: Divisible by %d%n\", divisor );\n      break;\n   }\n   \/\/ result is prime\n   System.out.println( \"Yes\" );\n}<\/pre>\n<\/div>\n
<\/div>\n
The table generated by the above code is presented below.<\/div>\n
<\/div>\n
\n\n\n\n\n\n\n\n\n\n
\"x\"<\/strong><\/th>\n\"2^{2^{x}<\/strong><\/th>\nPrime?<\/strong><\/th>\n<\/tr>\n
0<\/strong><\/td>\n3<\/strong><\/td>\nYes<\/b><\/td>\n<\/tr>\n
1<\/strong><\/td>\n5<\/strong><\/td>\nYes<\/b><\/td>\n<\/tr>\n
2<\/strong><\/td>\n17<\/strong><\/td>\nYes<\/b><\/td>\n<\/tr>\n
3<\/strong><\/td>\n257<\/strong><\/td>\nYes<\/b><\/td>\n<\/tr>\n
4<\/strong><\/td>\n65537<\/strong><\/td>\nYes<\/b><\/td>\n<\/tr>\n
5<\/strong><\/td>\n4294967297<\/strong><\/td>\nNo! Divisible by 641<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
When \"x=5\",\u00a0\"2^{2^{x}\u00a0is not prime. Thus disproving the original claim.<\/p>\n
We are in good company. The\u00a0conjecture was originally refuted by Leonhard Euler in 1732, but he had to do the calculations by hand.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Sometimes we need to show that a claim is false. This can be done by finding a counterexample. Consider any claim of the form:\u00a0. To show that the claim is false, we need to find a value of\u00a0\u00a0for which\u00a0\u00a0is true and\u00a0\u00a0is false. That is, we need to prove the negation of the above claim:\u00a0. Finding … <\/p>\n
Continue reading “Disproof by Counter Example”<\/span><\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[29],"class_list":["post-267","post","type-post","status-publish","format-standard","hentry","category-intermediate","tag-math"],"_links":{"self":[{"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/posts\/267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/comments?post=267"}],"version-history":[{"count":11,"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/posts\/267\/revisions"}],"predecessor-version":[{"id":357,"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/posts\/267\/revisions\/357"}],"wp:attachment":[{"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/media?parent=267"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/categories?post=267"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/loop.cs.mtu.edu\/index.php\/wp-json\/wp\/v2\/tags?post=267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}