13.9.16

Trapped In Finite Fields Part 2

In my previous entry I attempted to show why the Collatz Conjecture is true for any integer s by suggesting that s gets trapped in a finite field for a lack of a better phrase to describe this process.

In particular, I imagine it gets trapped into a portion of the ((n+1)/2)th row of the exponentiation table of Zn where n is some odd integer.  

The ((n+1)/2)th row of the exponentiation table of Zn, where n is some odd integer, is the 2nd row of the exponentiation table of Zn in reverse order, which means that the last few elements of it are consecutive powers of 2 in descending order. Furthermore, dividing any even element in this row by 2 produces the next element in the row and there are elements k,l in that row not necessarily distinct such that 3*k+1 = (l*((n+1)/2) mod n).

Most of this I haven't proven yet. So here are a few examples to (hopefully) better illustrate what I mean:

Example: Let n = 35. It can be verified that row 18 is equivalent to row 2 in reverse order, and so it ends in consecutive powers of 2 in descending order. Furthermore, dividing any even element in this row by 2 produces the next element in the row and there are elements k = 22, l = 29 in that row not necessarily distinct such that 3*22+1 (mod 35) = 29*18 (mod 35)




It may sound a bit counterintuitive that n is an odd integer because if n is even then it is divisible by 2 and so it would seem that it would fall right into the algorithm behind the Collatz conjecture.

However, this does not appear to be the case. I conjecture this to be the key to solving this problem.

Example: the exponentiation tables for n = 6 and n = 10 are given below:

Neither the (n/2)th nor the ((n/2)+1)th row ever reach consecutive powers of 2. In both of these cases n is a product of 2 and an odd integer, and in both cases  (n/2)i = (n/2) mod n and ((n/2)+1)i = ((n/2)+1) mod n for all i < n.

In general I claim the following:

Claim: If n is an even integer then for all i such that 1 < i < n
(n/2)i = (n/2) mod n if n  = 2m for some odd integer m
(n/2)i = 0 mod n  if n  = 2rm for some odd integer m and some integer r

Claim: If n is an even then for all i such that 0 < i < n
(n/2)i * 2i = 0 mod n 

In contrast:

Claim: If n is an odd integer and r is the order of 2 mod n then for all i such that 1 < i < r
((n+1)/2)i * 2i = 1 mod n

Below I attach a tool for finding all powers of k mod n for any integer n.