# 301 - Topic 8 - Large Counterexample mod arithmetic

## 248 days ago by Professor301

John Travis

Mississippi College

November 2022

An interesting idea is to check a conditional proposition P(n) for a bunch of values of n and if true (or false) for all of those then you might presume that P(n) has the same truth value for all natural numbers n.  Of course, this is not a proof but just a hunch.

To see why this may be a bad approach (using your gut), consider the following statement;

$P(n): \exists n \in N \ni 2^n \equiv_n 3$

The cell below allows you to check this statement for several modestly sized values of n....that is, values of n for which you could do this by hand.  To check, we will instead compute $2^n - 3$ and see if the remainder is 0.  If so, then P(n) above is true.  If the remainder is not 0, then P(n) is false.

last_n = 20 for n in range(2,last_n): ans = Mod(2^n, n) - 3 pretty_print("n = "+str(n)) pretty_print(html("$(2^n - 3) \\text{ mod n } =$"+ str(ans)))
 $(2^n - 3) \text{ mod n } =$1$(2^n - 3) \text{ mod n } =$2$(2^n - 3) \text{ mod n } =$1$(2^n - 3) \text{ mod n } =$4$(2^n - 3) \text{ mod n } =$1$(2^n - 3) \text{ mod n } =$6$(2^n - 3) \text{ mod n } =$5$(2^n - 3) \text{ mod n } =$5$(2^n - 3) \text{ mod n } =$1$(2^n - 3) \text{ mod n } =$10$(2^n - 3) \text{ mod n } =$1$(2^n - 3) \text{ mod n } =$12$(2^n - 3) \text{ mod n } =$1$(2^n - 3) \text{ mod n } =$5$(2^n - 3) \text{ mod n } =$13$(2^n - 3) \text{ mod n } =$16$(2^n - 3) \text{ mod n } =$7$(2^n - 3) \text{ mod n } =$18 12141655110112151316718

Notice that none of these equals zero and thus for none of these values of n does the original P(n) become true.

Below, take a try by plugging in any value of n you want and see if you can find one where P(n) is true by seeing where the output is zero.

n = 34 ans = Mod(2^n, n) - 3 pretty_print("n = "+str(n)) pretty_print(html("$(2^n - 3) \\text{ mod n } =$"+ str(ans)))
 $(2^n - 3) \text{ mod n } =$1 1

However, it turns out that there is an n for which P(n) is true.  n = 4700063497 is the first one!

n = 4700063497 ans = Mod(2^n, n) - 3 pretty_print("n = "+str(n)) pretty_print(html("$(2^n - 3) \\text{ mod n } =$"+ str(ans)))
 $(2^n - 3) \text{ mod n } =$0 0