Here are the basic claims that lead to the p-word, all proven with high-school math, validated by AI. Please, someone, find the error. I need to get some sleep.
# I. Exhaustive Walk Over Prime Congruence Classes
Theorem 1.
Let p be an odd prime with p ≠ 3. Define an affine map f: ℤ/pℤ → ℤ/pℤ by
f(x) = 3x + 1 (mod p).
Since gcd(3, p) = 1, f is an invertible affine transformation. In particular, f is a permutation of ℤ/pℤ. Moreover, if we write f in the form
f(x) = 3(x + c)
with the unique constant c = 1/3 (interpreted in ℤ/pℤ) (i.e. by solving 3x + 1 = 3(x + c)), it follows that f is conjugate to the multiplication-by-3 map on ℤ/pℤ and hence its cycle structure is completely determined by the order of 3 modulo p.
In particular, for any starting value α ∈ ℤ/pℤ not equal to the unique fixed point, the orbit {α, f(α), f²(α), …} is a (cyclic) subgroup of ℤ/pℤ and hence "exhausts" its cycle.
Proof.
Since 3 is invertible modulo p, the affine map f is invertible and thus a permutation. A standard fact about maps of the form f(x)=ax+b on a finite field is that they are conjugate to the linear map x ↦ a·x. (One may define y=x + b⁄(1−a) so that f becomes y ↦ a·y.) Consequently, the cycle structure of f is the same as the cycle structure of the multiplication-by-3 map, whose nonzero orbits are cyclic of length equal to the multiplicative order of 3 modulo p; the fixed point of f is the unique solution of x=3x+1, viz. x = −(1)/(2) (in ℤ/pℤ).
∎
# II. Removal of Congruence Classes (Modulo 3)
Theorem 2.
For every integer n, we have
3n + 1 ≡ 1 (mod 3).
Thus, if one defines L(n)=3n+1 (the “linear part” of the Collatz map), then for every n ∈ ℤ we have L(n) ∈ {1} (mod 3); in other words, the mapping L “eliminates” the residue classes 0 and 2 modulo 3.
Proof.
For any n ∈ ℤ, note that 3n ≡ 0 (mod 3) and hence 3n+1 ≡ 1 (mod 3).
∎
# III. Invariance Under Division by Powers of Two
Theorem 3.
Let p be any odd prime. Suppose A ∈ ℤ is given and p ∤ A. For any integer k ≥ 0, define
A/2^k
to be the unique element of ℤ/pℤ equal to A · (2^k)⁻¹, where (2^k)⁻¹ is the multiplicative inverse of 2^k modulo p. Then the operation “division by 2^k” is an automorphism of ℤ/pℤ. In particular, if A ≡ c (mod p) then
A/2^k ≡ c · (2^k)⁻¹ (mod p),
so any congruence property of A modulo p is preserved (up to multiplication by the invertible constant (2^k)⁻¹).
Proof.
Because p is odd, 2 is invertible modulo p. Hence, for any k the number 2^k is invertible mod p and division by it is well defined as multiplication by (2^k)⁻¹. Therefore, if A ≡ c (mod p), then A/2^k ≡ c · (2^k)⁻¹ (mod p).
∎
# IV. Monotonic Contraction of Allowed Congruence Classes
Theorem 4.
Let S be a finite set of odd primes, and suppose that for each p ∈ S the iterative process (applying L(n)=3n+1, possibly followed by division by the maximal power of 2) “eliminates” one or more congruence classes modulo p from the set of permitted residues in the long‐term evolution of the sequence. That is, assume that after one iteration the residue of n modulo p lies in a subset R_p ⊂ ℤ/pℤ with |R_p| < p. Then any n is forced to lie in the set of residue vectors
R = ∏{p∈S} R_p
which is a proper subset of
X = ∏{p∈S} ℤ/pℤ.
In particular, by the Chinese remainder theorem the total number of residue combinations the future value of n may assume is at most ∏{p∈S} |R_p|, strictly less than ∏{p∈S} p. Thus, under successive iterations the set of “admissible” residue vectors (that is, the overall modular configuration of n) is contracted.
Proof.
For each odd prime p in S, the hypothesis is that after an iteration n is forced to lie in a subset R_p ⊂ ℤ/pℤ with |R_p| < p. Then by the Chinese remainder theorem, any integer n is determined modulo M = ∏{p∈S} p by its vector of residues (n_p){p∈S} ∈ X. Since the process restricts n_p to lie in R_p for each p, the number of possible residue vectors is at most ∏_{p∈S} |R_p|, which is strictly less than M.
∎
# V. Forcing an Integer to be a Power of Two
Theorem 5.
Suppose that, under an iterative process derived from the Collatz rule, every odd prime p (or all p in an infinite set) forces the residue of n to be a fixed value—say, 1 modulo p; i.e., n ≡ 1 (mod p) for all such p. Then for every finite set S of odd primes we have n ≡ 1 (mod M), where M = ∏_{p∈S} p. Since this holds for every finite S, it follows that if n > 1 had any odd prime divisor, then for some p dividing n we would have n ≡ 0 (mod p), a contradiction. Hence n is not divisible by any odd prime and must be a power of 2.
Proof.
Assume that for every odd prime p (or for every p in an infinite set P) the iterative process forces n ≡ 1 (mod p). Then for any finite set S ⊆ P, by the Chinese remainder theorem n ≡ 1 (mod ∏_{p∈S} p). If n were divisible by an odd prime q, then taking S such that q ∈ S would force n ≡ 1 (mod q), contradicting n ≡ 0 (mod q). Thus n is not divisible by any odd prime, which implies that n is a power of 2.
∎
# Conclusion
The above theorems rigorously formalize the following modular observations about the linear part of the Collatz iteration (and its interaction with division by powers of two):
- For every odd prime p ≠ 3, the map L(n)=3n+1 acts as a permutation of ℤ/pℤ that exhaustively cycles through the residues (up to its natural cycle structure).
- In particular, modulo 3 we have L(n) ≡ 1 for all n, so the non-1 residue classes are eliminated.
- Division by any power of two (applied after the linear step) preserves congruence information modulo any odd prime.
- If an iterative process restricts the allowable residues for n modulo a collection S of odd primes, then the Chinese remainder theorem implies that the set of possible values for n (modulo ∏_{p∈S} p) is strictly reduced.
- Finally, if this process eliminates all “nontrivial” residue classes for all odd primes, then n must be congruent to 1 modulo every odd prime, forcing n to be a power of two.