Identifier
F:nat-totient-prime-pow
Proof route
kernel-lean
External status
proved
Axiom footprint
Empty

Recorded description

For every prime p and every k >= 1, totient(p^k) = p^k - p^(k-1). Stated at k = j+1 so the exponent is syntactically a successor. Primality is necessary: the identity fails at 42 composite (c,k) pairs with c < 30 and k <= 3, the smallest being c = 4, k = 1, where totient(4) = 2 while 4 - 1 = 3.

Formal statement
theorem Nat.totient_prime_pow : ((x0 : AxNat) -> ((x1 : AxNat) -> ((x2 : And (AxNat.le (AxNat.succ (AxNat.succ AxNat.zero)) x0) (((x2 : AxNat) -> ((x3 : AxNat.dvd x2 x0) -> Or (Eq.{1} AxNat x2 (AxNat.succ AxNat.zero)) (Eq.{1} AxNat x2 x0))))) -> Eq.{1} AxNat (AxNat.totient (AxNat.pow x0 (AxNat.succ x1))) (AxNat.sub (AxNat.pow x0 (AxNat.succ x1)) (AxNat.pow x0 x1)))))

Dependencies

The graph shows direct ledger edges. Follow a node to open its artifact page.

Direct dependencies appear to the left. The current fact is in the center. Facts that depend directly on it appear to the right. Multiplying a modulus by one of [generated] kernel theorem Nat. Mathlib v4.30 source propositio Subtraction undoes addition on <= on the naturals is transitiv Multiplication on the naturals [generated] kernel theorem Nat. [generated] kernel theorem Nat. Current fact
9 direct dependencies 0 direct dependents Graph shows the first 8 on each side.

Evidence

kernel-Nat.totient_prime_pow

Kind
kernel-term
Status
checked

Supports: totient(p^(j+1)) = p^(j+1) - p^j under primality, with the whole rendered type pinned.

Checker command
test "$(cargo run -q -p axeyum-lean-kernel --example nat_theorem_inventory -- totient_prime_pow 2>/dev/null | tr '\t' ' ' | grep -Fc 'Nat.totient_prime_pow 5 ((x0 : AxNat) -> ((x1 : AxNat) -> ((x2 : And (AxNat.le (AxNat.succ (AxNat.succ AxNat.zero)) x0) (((x2 : AxNat) -> ((x3 : AxNat.dvd x2 x0) -> Or (Eq.{1} AxNat x2 (AxNat.succ AxNat.zero)) (Eq.{1} AxNat x2 x0))))) -> Eq.{1} AxNat (AxNat.totient (AxNat.pow x0 (AxNat.succ x1))) (AxNat.sub (AxNat.pow x0 (AxNat.succ x1)) (AxNat.pow x0 x1)))))')" -ge 1
Evidence notes

The grep pins the WHOLE rendered type, not the name. The kernel re-derives the type from the proof term and so refuses a FALSE theorem, but it cannot notice a statement that is weaker or transposed, and this one has both kinds of neighbour. `nat_theorem_inventory` exits non-zero for a name that does not exist, and `grep -Fc` consumes the whole pipe with the count then tested, rather than `grep -q`, which would SIGPIPE the producer under pipefail. Measured 2026-08-30: `nat_theorem_inventory` consumes only ONE name argument -- given two names in either order it reports on the LAST one only -- so exactly one is passed here. The primality hypothesis is quoted verbatim in its inline spelling (`2 <= p` and the divisor dichotomy) because this prelude has no `Prime` predicate to name, and because dropping or weakening it makes the statement FALSE rather than merely weaker -- the Rust test pins that with a composite base-4 control where the two sides compute to 2 and 3 and are asserted NOT def_eq. The exponent is pinned as `AxNat.succ x1` on the left and `x1` on the right: writing both as `x1` would be the k = 0 case, which is false (totient(1) = 1, not 1 - 1 = 0).

instances-Nat.totient_prime_pow

Kind
exhaustive-enumeration
Status
checked

Supports: The identity holds at every prime p < 30 and 1 <= k <= 4 with p^k <= 2000, and FAILS at 42 composite bases, so primality is necessary rather than convenient.

Checker command
python3 scripts/tests/check-totient-prime-power-numerics.py
Evidence notes

Thirty-four checks, each negative control asserted to GENUINELY fail. Checks 5 and 5N are this fact's; 5M pins the multiplicative form the induction actually builds and 5S the closing Nat.sub step, and 6/6N pin the prime step totient(p*x) = eps(x)*totient(x) that the three remaining ml430 totient mirrors need. The kernel-side instantiation is `totient_prime_pow_computes_at_two_cubed_and_three_squared_with_a_composite_control` (nat_prelude_tests.rs): 2^3 and 3^2 with every value required to COMPUTE, plus the composite base-4 control. Magnitudes are held at 8, 9 and 4 deliberately -- prelude numerals are unary, so a test at 2^10 would cost more than the prelude build.

footprint-nat-prelude

Kind
exhaustive-enumeration
Status
checked

Supports: axiom_footprint: [] -- the Nat prelude's trusted surface is empty, which bounds this theorem.

Checker command
cargo run -q -p axeyum-lean-kernel --example nat_axiom_inventory -- --require-axiom-free nat
Evidence notes

`--require-axiom-free` exits non-zero when the named prelude's trusted surface (Axiom + Opaque + Quotient -- counting `Axiom` alone would not suffice, since `Opaque` has no proof body and `Quotient` admits `Quot.sound`) is non-empty, and errors rather than passing silently for a prelude the run never built. A declaration cannot depend on a trusted declaration the environment does not contain, so an empty nat surface bounds every declaration in it, including this one. This is a whole-prelude bound, not a per-declaration measurement.

Provenance

{
  "date": "2026-08-30",
  "established_by": "axeyum-lean-kernel nat_prelude::totient_prime_pow (totient-prime-power lane)",
  "source": "statement and proof authored here; the counting law it rests on is F:nat-totient-mul-of-dvd, landed in the same lane",
  "prior_art": [
    {
      "who": "Leonhard Euler",
      "what": "the totient of a prime power",
      "year": 1763,
      "attribution": "standard textbook attribution; this lane did not consult the primary source"
    }
  ]
}