-- Mathlib/Data/ZMod/Units.lean
theorem unitsMap_surjective [hm : NeZero m] (h : n ∣ m) :
    Function.Surjective (unitsMap h)

Proof state:
case pos
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
⊢ False

Tactic:
have h := Nat.dvd_sub' hp hpx

Result:
case pos
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h : p ∣ x + ps.prod id * n - x
⊢ False

Proof state:
case pos.inl
n m : ℕ
hm : NeZero m
h✝¹ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h✝ : p ∣ ps.prod id * n
h : p ∣ ps.prod id
⊢ False

Tactic:
have ⟨q, hq, hq'⟩ := (pp.prime.dvd_finset_prod_iff id).mp h

Result:
case pos.inl
n m : ℕ
hm : NeZero m
h✝¹ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h✝ : p ∣ ps.prod id * n
h : p ∣ ps.prod id
q : ℕ
hq : q ∈ ps
hq' : p ∣ id q
⊢ False

Proof state:
case pos
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h : p ∣ x + ps.prod id * n - x
⊢ False

Tactic:
rw [add_comm, Nat.add_sub_cancel] at h

Result:
case pos
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h : p ∣ ps.prod id * n
⊢ False

Proof state:
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
⊢ ∃ k, (x + k * n).Coprime m

Tactic:
use ps.prod id

Result:
case h
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
⊢ (x + ps.prod id * n).Coprime m

Proof state:
case h
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
⊢ (x + ps.prod id * n).Coprime m

Tactic:
apply Nat.coprime_of_dvd

Result:
case h.H
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
⊢ ∀ (k : ℕ), Nat.Prime k → k ∣ x + ps.prod id * n → ¬k ∣ m

Proof state:
case neg
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : ¬p ∣ x
pps : p ∈ ps
h : p ∣ x
⊢ False

Tactic:
contradiction

Result:
no goals

Proof state:
case pos
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h : p ∣ ps.prod id * n
⊢ False

Tactic:
rcases pp.dvd_mul.mp h with h | h

Result:
case pos.inl
n m : ℕ
hm : NeZero m
h✝¹ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h✝ : p ∣ ps.prod id * n
h : p ∣ ps.prod id
⊢ False

case pos.inr
n m : ℕ
hm : NeZero m
h✝¹ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : p ∣ x
h✝ : p ∣ ps.prod id * n
h : p ∣ n
⊢ False

Proof state:
n m : ℕ
hm : NeZero m
h : n ∣ m
this✝ : ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m
x : (ZMod n)ˣ
k : ℕ
hk : ((↑x).val + k * n).Coprime m
this : NeZero n
⊢ ↑((unitsMap h) (unitOfCoprime ((↑x).val + k * n) hk)) = ↑x

Tactic:
simp [unitsMap_def, - castHom_apply]

Result:
no goals

Proof state:
n m : ℕ
hm : NeZero m
h : n ∣ m
⊢ ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m

Tactic:
intro x hx

Result:
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
⊢ ∃ k, (x + k * n).Coprime m

Proof state:
n m : ℕ
hm : NeZero m
h : n ∣ m
⊢ Function.Surjective ⇑(unitsMap h)

Tactic:
suffices ∀ x : ℕ, x.Coprime n → ∃ k : ℕ, (x + k * n).Coprime m by
  intro x
  have ⟨k, hk⟩ := this x.val.val (val_coe_unit_coprime x)
  refine ⟨unitOfCoprime _ hk, Units.ext ?_⟩
  have : NeZero n := ⟨fun hn ↦ hm.out (eq_zero_of_zero_dvd (hn ▸ h))⟩
  simp [unitsMap_def, - castHom_apply]

Result:
n m : ℕ
hm : NeZero m
h : n ∣ m
⊢ ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m

Proof state:
case neg
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : ¬p ∣ x
pps : p ∈ ps
⊢ False

Tactic:
have h := Nat.dvd_sub' hp ((Finset.dvd_prod_of_mem id pps).mul_right n)

Result:
case neg
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : ¬p ∣ x
pps : p ∈ ps
h : p ∣ x + ps.prod id * n - (∏ i ∈ ps, id i) * n
⊢ False

Proof state:
n m : ℕ
hm : NeZero m
h : n ∣ m
this : ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m
x : (ZMod n)ˣ
k : ℕ
hk : ((↑x).val + k * n).Coprime m
⊢ ∃ a, (unitsMap h) a = x

Tactic:
refine ⟨unitOfCoprime _ hk, Units.ext ?_⟩

Result:
n m : ℕ
hm : NeZero m
h : n ∣ m
this : ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m
x : (ZMod n)ˣ
k : ℕ
hk : ((↑x).val + k * n).Coprime m
⊢ ↑((unitsMap h) (unitOfCoprime ((↑x).val + k * n) hk)) = ↑x

Proof state:
n m : ℕ
hm : NeZero m
h : n ∣ m
this : ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m
x : (ZMod n)ˣ
⊢ ∃ a, (unitsMap h) a = x

Tactic:
have ⟨k, hk⟩ := this x.val.val (val_coe_unit_coprime x)

Result:
n m : ℕ
hm : NeZero m
h : n ∣ m
this : ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m
x : (ZMod n)ˣ
k : ℕ
hk : ((↑x).val + k * n).Coprime m
⊢ ∃ a, (unitsMap h) a = x

Proof state:
case neg
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : ¬p ∣ x
pps : p ∈ ps
h : p ∣ x + ps.prod id * n - (∏ i ∈ ps, id i) * n
⊢ False

Tactic:
rw [Nat.add_sub_cancel] at h

Result:
case neg
n m : ℕ
hm : NeZero m
h✝ : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : ¬p ∣ x
pps : p ∈ ps
h : p ∣ x
⊢ False

Proof state:
case neg
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : ¬p ∣ x
⊢ False

Tactic:
have pps : p ∈ ps := Finset.mem_filter.mpr ⟨Nat.mem_primeFactors.mpr ⟨pp, hpn, hm.out⟩, hpx⟩

Result:
case neg
n m : ℕ
hm : NeZero m
h : n ∣ m
x : ℕ
hx : x.Coprime n
ps : Finset ℕ := Finset.filter (fun p => ¬p ∣ x) m.primeFactors
p : ℕ
pp : Nat.Prime p
hp : p ∣ x + ps.prod id * n
hpn : p ∣ m
hpx : ¬p ∣ x
pps : p ∈ ps
⊢ False

Proof state:
n m : ℕ
hm : NeZero m
h : n ∣ m
this : ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m
x : (ZMod n)ˣ
k : ℕ
hk : ((↑x).val + k * n).Coprime m
⊢ ↑((unitsMap h) (unitOfCoprime ((↑x).val + k * n) hk)) = ↑x

Tactic:
have : NeZero n := ⟨fun hn ↦ hm.out (eq_zero_of_zero_dvd (hn ▸ h))⟩

Result:
n m : ℕ
hm : NeZero m
h : n ∣ m
this✝ : ∀ (x : ℕ), x.Coprime n → ∃ k, (x + k * n).Coprime m
x : (ZMod n)ˣ
k : ℕ
hk : ((↑x).val + k * n).Coprime m
this : NeZero n
⊢ ↑((unitsMap h) (unitOfCoprime ((↑x).val + k * n) hk)) = ↑x