301 - Large Counterexample mod arithmetic

11 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))) 
       
1
2
1
4
1
6
5
5
1
10
1
12
1
5
13
16
7
18
                                
                            
1
2
1
4
1
6
5
5
1
10
1
12
1
5
13
16
7
18
                                

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))) 
       
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))) 
       
0
                                
                            
0