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.<p># I. Exhaustive Walk Over Prime Congruence Classes<p>Theorem 1.<p>Let p be an odd prime with p ≠ 3. Define an affine map f: ℤ/pℤ → ℤ/pℤ by<p><pre><code> f(x) = 3x + 1 (mod p).
</code></pre>
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<p><pre><code> f(x) = 3(x + c)
</code></pre>
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.<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.<p>Proof.<p>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ℤ).<p>∎<p># II. Removal of Congruence Classes (Modulo 3)<p>Theorem 2.<p>For every integer n, we have<p><pre><code> 3n + 1 ≡ 1 (mod 3).
</code></pre>
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.<p>Proof.<p>For any n ∈ ℤ, note that 3n ≡ 0 (mod 3) and hence 3n+1 ≡ 1 (mod 3).<p>∎<p># III. Invariance Under Division by Powers of Two<p>Theorem 3.<p>Let p be any odd prime. Suppose A ∈ ℤ is given and p ∤ A. For any integer k ≥ 0, define<p><pre><code> A/2^k
</code></pre>
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<p><pre><code> A/2^k ≡ c · (2^k)⁻¹ (mod p),
</code></pre>
so any congruence property of A modulo p is preserved (up to multiplication by the invertible constant (2^k)⁻¹).<p>Proof.<p>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).<p>∎<p># IV. Monotonic Contraction of Allowed Congruence Classes<p>Theorem 4.<p>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<p><pre><code> R = ∏{p∈S} R_p
</code></pre>
which is a proper subset of<p><pre><code> X = ∏{p∈S} ℤ/pℤ.
</code></pre>
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.<p>Proof.<p>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.<p>∎<p># V. Forcing an Integer to be a Power of Two<p>Theorem 5.<p>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.<p>Proof.<p>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.
∎<p># Conclusion<p>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):<p>- 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.