AFTD Auto-Formalizing Theoretical Domains

nat_xor_mod_two

theoremverified

For any natural numbers a and b, (a ^^^ b) % 2 = (a + b) % 2.

Statement

theorem nat_xor_mod_two (a b : ℕ) : (a ^^^ b) % 2 = (a + b) % 2
Source
step towards spider_two_leg_one_free
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • spider_mex_two_leg_one_freeGiven an explicit options list where every element has parity k % 2, the minimum excluded value is 1 - k % 2 (which is 1 when k is even,…

The proof, explained

The statement asserts that for any natural numbers $a$ and $b$, bitwise XOR modulo 2 agrees with addition modulo 2. This is identical to the Mathlib lemma `Nat.xor_mod_two_eq`, so the theorem is proved by applying that lemma directly.

  1. For any natural numbers $a$ and $b$, $(a \oplus b) \pmod 2 = (a + b) \pmod 2$.

    This is a direct application of the library lemma `Nat.xor_mod_two_eq`, which establishes that bitwise XOR modulo 2 coincides with addition modulo 2 for all natural numbers.

    line 2

    uses Nat.xor_mod_two_eq

    theorem nat_xor_mod_two (a b : ℕ) : (a ^^^ b) % 2 = (a + b) % 2 := Nat.xor_mod_two_eq
Nat.xor_mod_two_eq
For any two natural numbers $m$ and $n$, the bitwise XOR $(m \oplus n) \pmod 2$ is equal to $(m + n) \pmod 2$.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The bitwise XOR of natural numbers modulo 2 equals their sum modulo 2. -/theorem nat_xor_mod_two (a b : ℕ) : (a ^^^ b) % 2 = (a + b) % 2 := Nat.xor_mod_two_eq
See it in the graphDiscuss this resultChallenge it