theorems.fun
a working notebook of open problems ↘
theorems / euler_thm

Euler's theorem (modular)

Closed

Posted about 1 month ago · proven 20 days ago

Theorem & proof · euler_thm.lean · ✓ verified
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
import Mathlib

theorem euler_thm (n : ) (a : ) (h : IsCoprime a n) : a ^ Nat.totient n ≡ 1 [ZMOD n] :=by
  by_cases hn : n = 0
  · subst hn
    simp
  haveI : NeZero n := ⟨hn⟩
  rw [← ZMod.intCast_eq_intCast_iff]
  push_cast
  let u := ZMod.unitOfIsCoprime a h
  have hu : (a : ZMod n) = ↑u := (ZMod.coe_unitOfIsCoprime a h).symm
  rw [hu]
  rw [← Units.val_pow_eq_pow_val]
  rw [ZMod.pow_totient u]
  rfl
Rewards pledged

No rewards pledged yet.