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

Chinese remainder theorem (coprime moduli)

Closed

Posted about 1 month ago · proven 20 days ago

Theorem & proof · crt.lean · ✓ verified
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
import Mathlib

theorem crt {m n : } (h : Nat.Coprime m n) (a b : ) :  x : , x ≡ a [ZMOD m]  x ≡ b [ZMOD n] :=by
  by_cases hm : m = 0
  · subst hm
    have hn : n = 1 := by rwa [Nat.Coprime, Nat.gcd_zero_left] at h
    subst hn
    use a
    exact ⟨rfl, Int.modEq_one⟩
  by_cases hn : n = 0
  · subst hn
    have hm' : m = 1 := by rwa [Nat.Coprime, Nat.gcd_zero_right] at h
    subst hm'
    use b
    exact ⟨Int.modEq_one, rfl⟩
  haveI : NeZero m := ⟨hm⟩
  haveI : NeZero n := ⟨hn⟩
  haveI : NeZero (m * n) := ⟨mul_ne_zero hm hn⟩
  let z : ZMod m × ZMod n := (a, b)
  let x_zmod := (ZMod.chineseRemainder h).symm z
  use (x_zmod.val : )
  have h_eq := RingEquiv.apply_symm_apply (ZMod.chineseRemainder h) z
  constructor
  · rw [← ZMod.intCast_eq_intCast_iff]
    simp only [Int.cast_natCast]
    rw [← ZMod.cast_eq_val]
    have h_fst := congr_arg Prod.fst h_eq
    have h_proj : (ZMod.chineseRemainder h x_zmod).1 = (ZMod.cast x_zmod : ZMod m) := by
      simp [ZMod.chineseRemainder]
    have h_fst_simp : (ZMod.cast x_zmod : ZMod m) = (a : ZMod m) := by
      rw [← h_proj]
      exact h_fst
    exact h_fst_simp
  · rw [← ZMod.intCast_eq_intCast_iff]
    simp only [Int.cast_natCast]
    rw [← ZMod.cast_eq_val]
    have h_snd := congr_arg Prod.snd h_eq
    have h_proj : (ZMod.chineseRemainder h x_zmod).2 = (ZMod.cast x_zmod : ZMod n) := by
      simp [ZMod.chineseRemainder]
    have h_snd_simp : (ZMod.cast x_zmod : ZMod n) = (b : ZMod n) := by
      rw [← h_proj]
      exact h_snd
    exact h_snd_simp
Rewards pledged

No rewards pledged yet.