kernel-Nat.isPrime_eq_true_of_prime
- Kind
- kernel-term
- Status
- checked
Supports: prime_condition n implies Nat.isPrime n = true
test "$(cargo run -q -p axeyum-lean-kernel --example nat_theorem_inventory -- 'Nat.isPrime_eq_true_of_prime' 2>/dev/null | grep -xFc 'Nat.isPrime_eq_true_of_prime 4 ((x0 : AxNat) -> ((x1 : And (AxNat.le (AxNat.succ (AxNat.succ AxNat.zero)) x0) (((x1 : AxNat) -> ((x2 : AxNat.dvd x1 x0) -> Or (Eq.{1} AxNat x1 (AxNat.succ AxNat.zero)) (Eq.{1} AxNat x1 x0))))) -> Eq.{1} Bool (AxNat.isPrime x0) Bool.true))')" -ge 1 Evidence notes
`Nat.isPrime n` unfolds to `beq (countRange (fun j => beq (n % (j+1)) 0) n) 2` -- a divisor COUNT, not a trial division. The proof shows that count is exactly two for a prime: `1 | n` supplies the index 0, `Nat.mod_self` supplies the index n-1, and every index between is refuted by primality's own divisor clause (`c = 1` by `succ_ne_zero`, `c = n` by `lt_irrefl` against the range hypothesis). The count is assembled by peeling the last index with `countRange_succ_of_true` and the first with `countRange_split` at 1, leaving `countRange_eq_zero_of_all_false` for the middle: 2 = 1 + 0 + 1. The rendered type is matched in full because the weakening that matters here is invisible to a name check: `Nat.isPrime` is universe- and argument-compatible with any `AxNat -> Bool`, so a checker that read only the name would be satisfied by a theorem about a different predicate entirely.