no goals
x y r r' : ℕ
⊢ ∀ {s t s' t' : ℤ}, Nat.P x y (r, s, t) → Nat.P x y (r', s', t') → Nat.P x y (xgcdAux r s t r' s' t')
induction r, r' using gcd.induction with
| H0 => simp
| H1 a b h IH =>
  intro s t s' t' p p'
  rw [xgcd_aux_rec h]; refine' IH _ p; dsimp [P] at *
  rw [Int.emod_def]; generalize (b / a : ℤ) = k
  rw [p, p', mul_sub, sub_add_eq_add_sub, mul_sub, add_mul, mul_comm k t, mul_comm k s,
    ← mul_assoc, ← mul_assoc, add_comm (x * s * k), ← add_sub_assoc, sub_sub]
no goals
case H0
x y n✝ : ℕ
⊢ ∀ {s t s' t' : ℤ}, Nat.P x y (0, s, t) → Nat.P x y (n✝, s', t') → Nat.P x y (xgcdAux 0 s t n✝ s' t')
simp
case H1
x y a b : ℕ
h : 0 < a
IH : ∀ {s t s' t' : ℤ}, Nat.P x y (b % a, s, t) → Nat.P x y (a, s', t') → Nat.P x y (xgcdAux (b % a) s t a s' t')
s t s' t' : ℤ
p : Nat.P x y (a, s, t)
p' : Nat.P x y (b, s', t')
⊢ Nat.P x y (xgcdAux a s t b s' t')
case H1
x y a b : ℕ
h : 0 < a
IH : ∀ {s t s' t' : ℤ}, Nat.P x y (b % a, s, t) → Nat.P x y (a, s', t') → Nat.P x y (xgcdAux (b % a) s t a s' t')
⊢ ∀ {s t s' t' : ℤ}, Nat.P x y (a, s, t) → Nat.P x y (b, s', t') → Nat.P x y (xgcdAux a s t b s' t')
intro s t s' t' p p'
case H1
x y a b : ℕ
h : 0 < a
IH : ∀ {s t s' t' : ℤ}, Nat.P x y (b % a, s, t) → Nat.P x y (a, s', t') → Nat.P x y (xgcdAux (b % a) s t a s' t')
s t s' t' : ℤ
p : Nat.P x y (a, s, t)
p' : Nat.P x y (b, s', t')
⊢ Nat.P x y (xgcdAux (b % a) (s' - ↑b / ↑a * s) (t' - ↑b / ↑a * t) a s t)
case H1
x y a b : ℕ
h : 0 < a
IH : ∀ {s t s' t' : ℤ}, Nat.P x y (b % a, s, t) → Nat.P x y (a, s', t') → Nat.P x y (xgcdAux (b % a) s t a s' t')
s t s' t' : ℤ
p : Nat.P x y (a, s, t)
p' : Nat.P x y (b, s', t')
⊢ Nat.P x y (xgcdAux a s t b s' t')
rw [xgcd_aux_rec h]
case H1
x y a b : ℕ
h : 0 < a
IH : ∀ {s t s' t' : ℤ}, Nat.P x y (b % a, s, t) → Nat.P x y (a, s', t') → Nat.P x y (xgcdAux (b % a) s t a s' t')
s t s' t' : ℤ
p : Nat.P x y (a, s, t)
p' : Nat.P x y (b, s', t')
⊢ Nat.P x y (b % a, s' - ↑b / ↑a * s, t' - ↑b / ↑a * t)
case H1
x y a b : ℕ
h : 0 < a
IH : ∀ {s t s' t' : ℤ}, Nat.P x y (b % a, s, t) → Nat.P x y (a, s', t') → Nat.P x y (xgcdAux (b % a) s t a s' t')
s t s' t' : ℤ
p : Nat.P x y (a, s, t)
p' : Nat.P x y (b, s', t')
⊢ Nat.P x y (xgcdAux (b % a) (s' - ↑b / ↑a * s) (t' - ↑b / ↑a * t) a s t)
refine' IH _ p
case H1
x y a b : ℕ
h : 0 < a
IH :
  ∀ {s t s' t' : ℤ},
    ↑b % ↑a = ↑x * s + ↑y * t →
      ↑a = ↑x * s' + ↑y * t' →
        ↑(xgcdAux (b % a) s t a s' t').fst =
          ↑x * (xgcdAux (b % a) s t a s' t').2.fst + ↑y * (xgcdAux (b % a) s t a s' t').2.snd
s t s' t' : ℤ
p : ↑a = ↑x * s + ↑y * t
p' : ↑b = ↑x * s' + ↑y * t'
⊢ ↑b % ↑a = ↑x * (s' - ↑b / ↑a * s) + ↑y * (t' - ↑b / ↑a * t)
case H1
x y a b : ℕ
h : 0 < a
IH : ∀ {s t s' t' : ℤ}, Nat.P x y (b % a, s, t) → Nat.P x y (a, s', t') → Nat.P x y (xgcdAux (b % a) s t a s' t')
s t s' t' : ℤ
p : Nat.P x y (a, s, t)
p' : Nat.P x y (b, s', t')
⊢ Nat.P x y (b % a, s' - ↑b / ↑a * s, t' - ↑b / ↑a * t)
dsimp [P] at *
case H1
x y a b : ℕ
h : 0 < a
IH :
  ∀ {s t s' t' : ℤ},
    ↑b % ↑a = ↑x * s + ↑y * t →
      ↑a = ↑x * s' + ↑y * t' →
        ↑(xgcdAux (b % a) s t a s' t').fst =
          ↑x * (xgcdAux (b % a) s t a s' t').2.fst + ↑y * (xgcdAux (b % a) s t a s' t').2.snd
s t s' t' : ℤ
p : ↑a = ↑x * s + ↑y * t
p' : ↑b = ↑x * s' + ↑y * t'
⊢ ↑b - ↑a * (↑b / ↑a) = ↑x * (s' - ↑b / ↑a * s) + ↑y * (t' - ↑b / ↑a * t)
case H1
x y a b : ℕ
h : 0 < a
IH :
  ∀ {s t s' t' : ℤ},
    ↑b % ↑a = ↑x * s + ↑y * t →
      ↑a = ↑x * s' + ↑y * t' →
        ↑(xgcdAux (b % a) s t a s' t').fst =
          ↑x * (xgcdAux (b % a) s t a s' t').2.fst + ↑y * (xgcdAux (b % a) s t a s' t').2.snd
s t s' t' : ℤ
p : ↑a = ↑x * s + ↑y * t
p' : ↑b = ↑x * s' + ↑y * t'
⊢ ↑b % ↑a = ↑x * (s' - ↑b / ↑a * s) + ↑y * (t' - ↑b / ↑a * t)
rw [Int.emod_def]
case H1
x y a b : ℕ
h : 0 < a
IH :
  ∀ {s t s' t' : ℤ},
    ↑b % ↑a = ↑x * s + ↑y * t →
      ↑a = ↑x * s' + ↑y * t' →
        ↑(xgcdAux (b % a) s t a s' t').fst =
          ↑x * (xgcdAux (b % a) s t a s' t').2.fst + ↑y * (xgcdAux (b % a) s t a s' t').2.snd
s t s' t' : ℤ
p : ↑a = ↑x * s + ↑y * t
p' : ↑b = ↑x * s' + ↑y * t'
k : ℤ
⊢ ↑b - ↑a * k = ↑x * (s' - k * s) + ↑y * (t' - k * t)
case H1
x y a b : ℕ
h : 0 < a
IH :
  ∀ {s t s' t' : ℤ},
    ↑b % ↑a = ↑x * s + ↑y * t →
      ↑a = ↑x * s' + ↑y * t' →
        ↑(xgcdAux (b % a) s t a s' t').fst =
          ↑x * (xgcdAux (b % a) s t a s' t').2.fst + ↑y * (xgcdAux (b % a) s t a s' t').2.snd
s t s' t' : ℤ
p : ↑a = ↑x * s + ↑y * t
p' : ↑b = ↑x * s' + ↑y * t'
⊢ ↑b - ↑a * (↑b / ↑a) = ↑x * (s' - ↑b / ↑a * s) + ↑y * (t' - ↑b / ↑a * t)
generalize (b / a : ℤ) = k
no goals
case H1
x y a b : ℕ
h : 0 < a
IH :
  ∀ {s t s' t' : ℤ},
    ↑b % ↑a = ↑x * s + ↑y * t →
      ↑a = ↑x * s' + ↑y * t' →
        ↑(xgcdAux (b % a) s t a s' t').fst =
          ↑x * (xgcdAux (b % a) s t a s' t').2.fst + ↑y * (xgcdAux (b % a) s t a s' t').2.snd
s t s' t' : ℤ
p : ↑a = ↑x * s + ↑y * t
p' : ↑b = ↑x * s' + ↑y * t'
k : ℤ
⊢ ↑b - ↑a * k = ↑x * (s' - k * s) + ↑y * (t' - k * t)
rw [p, p', mul_sub, sub_add_eq_add_sub, mul_sub, add_mul, mul_comm k t, mul_comm k s,
  ← mul_assoc, ← mul_assoc, add_comm (x * s * k), ← add_sub_assoc, sub_sub]