# Proof: 641 divides 2^{32} + 1 exactly

- **Generated:** 2026-03-28
- **Verdict:** PROVED
- **Audit trail:** [proof_audit.md](proof_audit.md) | [proof.py](proof.py)

## Key Findings

- 2^32 + 1 = 4,294,967,297, and (2^32 + 1) mod 641 = 0, confirming 641 divides it exactly.
- Integer division yields 4,294,967,297 = 641 x 6,700,417 with zero remainder, independently confirming divisibility.
- Euler's algebraic decomposition (using 641 = 5^4 + 2^4 = 5 x 2^7 + 1) provides a third independent verification that 2^32 + 1 is congruent to 0 modulo 641.
- The complete prime factorization is 4,294,967,297 = 641 x 6,700,417 (both factors are prime).

## Claim Interpretation

**Natural language:** 641 divides 2^{32} + 1 exactly.

**Formal interpretation:** "Divides exactly" means 641 is a factor of 2^32 + 1, i.e., (2^32 + 1) mod 641 == 0. This is equivalent to showing 2^32 + 1 = 641 x k for some positive integer k. The number 2^32 + 1 = 4,294,967,297 is the fifth Fermat number (F_5), historically conjectured by Fermat to be prime. Euler disproved this by finding that 641 divides it.

*Source: proof.py JSON summary*

## Evidence Summary

| ID | Fact | Verified |
|----|------|----------|
| A1 | Direct modular arithmetic: (2^32 + 1) mod 641 | Computed: 0 (641 divides 2^32 + 1 with no remainder) |
| A2 | Integer division cross-check: 2^32 + 1 == 641 x quotient | Computed: True (641 x 6,700,417 = 4,294,967,297) |
| A3 | Algebraic decomposition via Euler's method | Computed: 2^32 mod 641 = 640, so (2^32 + 1) mod 641 = 0 |

*Source: proof.py JSON summary*

## Proof Logic

The proof establishes divisibility through three mathematically independent methods:

**Method 1 — Direct modular arithmetic (A1):** Python's arbitrary-precision integers compute (2^32 + 1) % 641 = 0 directly. Since the remainder is zero, 641 divides 2^32 + 1.

**Method 2 — Integer division reconstruction (A2):** Using `divmod(4294967297, 641)`, we obtain quotient 6,700,417 and remainder 0. Multiplying back: 641 x 6,700,417 = 4,294,967,297, which equals 2^32 + 1 exactly.

**Method 3 — Euler's algebraic decomposition (A3):** Euler's classical proof relies on two identities: 641 = 5^4 + 2^4 and 641 = 5 x 2^7 + 1. From the second identity, 5 x 2^7 is congruent to -1 (mod 641). Raising to the 4th power gives 5^4 x 2^28 congruent to 1 (mod 641). From the first identity, 5^4 is congruent to -2^4 (mod 641). Substituting: -2^4 x 2^28 = -2^32 is congruent to 1 (mod 641), so 2^32 is congruent to -1 (mod 641), meaning 2^32 + 1 is congruent to 0 (mod 641).

All three methods independently confirm the claim.

*Source: author analysis*

## Counter-Evidence Search

- **Precision/overflow concerns:** Python integers have arbitrary precision, so 2^32 + 1 = 4,294,967,297 is computed exactly. No risk of overflow or floating-point error.
- **Interpretation of "divides exactly":** In standard number theory, "641 divides 2^32 + 1 exactly" means the remainder is zero. The claim does not require 641 to be prime (though it is).
- **Smallest factor verification:** Trial division over all integers from 2 to 641 confirms that 641 is the smallest prime factor of 4,294,967,297. The cofactor 6,700,417 is also prime, giving the complete factorization.

*Source: proof.py JSON summary*

## Conclusion

**PROVED.** 641 divides 2^32 + 1 exactly. Direct computation shows (2^32 + 1) mod 641 = 0, confirmed independently by integer division (4,294,967,297 = 641 x 6,700,417) and by Euler's algebraic decomposition. The complete prime factorization of the fifth Fermat number is 4,294,967,297 = 641 x 6,700,417.

---

Generated by [proof-engine](https://github.com/yaniv-golan/proof-engine) v0.10.0 on 2026-03-28.
