---

Step * 1 2 1 of Lemma gcd-properties


1. k : ℕ
2. a : ℤ
3. b : ℤ
4. b ≠ 0
5. |b| ≤ k
6. |a rem b| < |b|
7. c : ℤ
8. (c * gcd(b;a rem b)) = b ∈ ℤ
9. d : ℤ
10. (d * gcd(b;a rem b)) = (a rem b) ∈ ℤ
11. s : ℤ
12. t : ℤ
13. gcd(b;a rem b) = ((s * b) + (t * (a rem b))) ∈ ℤ
⊢ (∃c:ℤ. ((c * gcd(b;a rem b)) = a ∈ ℤ))
∧ (∃d:ℤ. ((d * gcd(b;a rem b)) = b ∈ ℤ))
∧ (∃s,t:ℤ. (gcd(b;a rem b) = ((s * a) + (t * b)) ∈ ℤ))
BY
{ (Assert gcd(b;a rem b) = ((s * b) + (t * (a - (a ÷ b) * b))) ∈ ℤ BY
         (InstLemma `div_rem_sum` [⌜a⌝;⌜b⌝]⋅ THEN Auto)) }

1
1. k : ℕ
2. a : ℤ
3. b : ℤ
4. b ≠ 0
5. |b| ≤ k
6. |a rem b| < |b|
7. c : ℤ
8. (c * gcd(b;a rem b)) = b ∈ ℤ
9. d : ℤ
10. (d * gcd(b;a rem b)) = (a rem b) ∈ ℤ
11. s : ℤ
12. t : ℤ
13. gcd(b;a rem b) = ((s * b) + (t * (a rem b))) ∈ ℤ
14. gcd(b;a rem b) = ((s * b) + (t * (a - (a ÷ b) * b))) ∈ ℤ
⊢ (∃c:ℤ. ((c * gcd(b;a rem b)) = a ∈ ℤ))
∧ (∃d:ℤ. ((d * gcd(b;a rem b)) = b ∈ ℤ))
∧ (∃s,t:ℤ. (gcd(b;a rem b) = ((s * a) + (t * b)) ∈ ℤ))

---

Latex:

---

Latex:

1.  k  :  \mBbbN{}
2.  a  :  \mBbbZ{}
3.  b  :  \mBbbZ{}
4.  b  \mneq{}  0
5.  |b|  \mleq{}  k
6.  |a  rem  b|  <  |b|
7.  c  :  \mBbbZ{}
8.  (c  *  gcd(b;a  rem  b))  =  b
9.  d  :  \mBbbZ{}
10.  (d  *  gcd(b;a  rem  b))  =  (a  rem  b)
11.  s  :  \mBbbZ{}
12.  t  :  \mBbbZ{}
13.  gcd(b;a  rem  b)  =  ((s  *  b)  +  (t  *  (a  rem  b)))
\mvdash{}  (\mexists{}c:\mBbbZ{}.  ((c  *  gcd(b;a  rem  b))  =  a))
\mwedge{}  (\mexists{}d:\mBbbZ{}.  ((d  *  gcd(b;a  rem  b))  =  b))
\mwedge{}  (\mexists{}s,t:\mBbbZ{}.  (gcd(b;a  rem  b)  =  ((s  *  a)  +  (t  *  b))))


By

---

Latex:
(Assert  gcd(b;a  rem  b)  =  ((s  *  b)  +  (t  *  (a  -  (a  \mdiv{}  b)  *  b)))  BY
              (InstLemma  `div\_rem\_sum`  [\mkleeneopen{}a\mkleeneclose{};\mkleeneopen{}b\mkleeneclose{}]\mcdot{}  THEN  Auto))

---

Home Index