AFTD Auto-Formalizing Theoretical Domains

two_pow_four_ne_one_of_prime_ge_seven

theoremverified

For every prime $p \ge 7$, $2^4 \ne 1$ in $\mathbb{Z}/p\mathbb{Z}$.

Statement

theorem two_pow_four_ne_one_of_prime_ge_seven (p : ℕ) [Fact p.Prime] (hp : 7 ≤ p) :
    (2 : ZMod p) ^ 4 ≠ 1
Source
arXiv:2610.34758, Lemma 3.1
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any natural number $p$, if $p$ is prime and $7 \le p$, then $2^4 \neq 1$ in $\mathbb{Z}/p\mathbb{Z}$ (the ring of integers modulo $p$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

We argue by contradiction: suppose $2^4 = 1$ in $\mathbb{Z}/p\mathbb{Z}$. Subtracting 1 gives $15 = 2^4 - 1 = 0$ in $\mathbb{Z}/p\mathbb{Z}$, which implies that $p$ divides $15 = 3 \times 5$. By Euclid's lemma, the prime $p$ must divide 3 or 5, yielding $p \le 3$ or $p \le 5$, both of which contradict $p \ge 7$.

  1. Assuming $2^4 = 1$ in $\mathbb{Z}/p\mathbb{Z}$, we have $15 = 0$ in $\mathbb{Z}/p\mathbb{Z}$.

    We proceed by contradiction and assume $2^4 = 1$ in $\mathbb{Z}/p\mathbb{Z}$ (hypothesis $h$). We then compute $15 = 2^4 - 1 = 1 - 1 = 0$ in $\mathbb{Z}/p\mathbb{Z}$ using numeric evaluation, the assumption $h$, and the group identity `sub_self`.

    lines 4–8

    uses sub_self

      intro h
      have h1 : ((15 : ℕ) : ZMod p) = 0 := by
        calc ((15 : ℕ) : ZMod p) = (2 : ZMod p) ^ 4 - 1 := by norm_num
        _ = 1 - 1 := by rw [h]
        _ = 0 := sub_self 1
  2. The prime $p$ must divide 3 or divide 5.

    In $\mathbb{Z}/p\mathbb{Z}$, an integer casts to zero if and only if $p$ divides it (`ZMod.natCast_eq_zero_iff`), so $p \mid 15$. Unwrapping the primality of $p$ (`Fact.out`) and factoring $15 = 3 \times 5$, we obtain $p \mid 3 \times 5$. Since $p$ is prime, Euclid's lemma splits this into two alternatives: $p \mid 3$ or $p \mid 5$.

    lines 9–13

    uses ZMod.natCast_eq_zero_iff, Fact.out

      rw [ZMod.natCast_eq_zero_iff] at h1
      have hp_pr : p.Prime := Fact.out
      have h15 : 15 = 3 * 5 := by norm_num
      rw [h15] at h1
      rcases hp_pr.dvd_mul.mp h1 with h3 | h5
  3. The case $p \mid 3$ leads to a contradiction.

    If $p \mid 3$, then because $3 > 0$, any divisor $p$ satisfies $p \le 3$ (`Nat.le_of_dvd`). Linear integer arithmetic (`omega`) recognises that $p \le 3$ contradicts the initial hypothesis $p \ge 7$.

    lines 14–15

    uses Nat.le_of_dvd

      · have : p ≤ 3 := Nat.le_of_dvd (by norm_num) h3
        omega
  4. The case $p \mid 5$ leads to a contradiction, concluding the proof.

    If $p \mid 5$, then because $5 > 0$, we have $p \le 5$ (`Nat.le_of_dvd`). Linear integer arithmetic (`omega`) detects that $p \le 5$ contradicts $p \ge 7$, closing the final case.

    lines 16–17

    uses Nat.le_of_dvd

      · have : p ≤ 5 := Nat.le_of_dvd (by norm_num) h5
        omega
sub_self
Subtracting any element of an additive group from itself yields zero ($a - a = 0$).
ZMod.natCast_eq_zero_iff
A natural number $a$ maps to zero in $\mathbb{Z}/b\mathbb{Z}$ if and only if $b$ divides $a$.
Fact.out
Extracts the underlying mathematical proposition from a `Fact` typeclass wrapper.
Nat.le_of_dvd
If a natural number $m$ divides a strictly positive natural number $n$, then $m \le n$.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- In ZMod p for a prime p ≥ 7, 2^4 ≠ 1. -/theorem two_pow_four_ne_one_of_prime_ge_seven (p : ℕ) [Fact p.Prime] (hp : 7 ≤ p) :    (2 : ZMod p) ^ 4 ≠ 1 := by  intro h  have h1 : ((15 : ℕ) : ZMod p) = 0 := by    calc ((15 : ℕ) : ZMod p) = (2 : ZMod p) ^ 4 - 1 := by norm_num    _ = 1 - 1 := by rw [h]    _ = 0 := sub_self 1  rw [ZMod.natCast_eq_zero_iff] at h1  have hp_pr : p.Prime := Fact.out  have h15 : 15 = 3 * 5 := by norm_num  rw [h15] at h1  rcases hp_pr.dvd_mul.mp h1 with h3 | h5  · have : p ≤ 3 := Nat.le_of_dvd (by norm_num) h3    omega  · have : p ≤ 5 := Nat.le_of_dvd (by norm_num) h5    omega
See it in the graphDiscuss this resultChallenge it