Step * 1 2 of Lemma gcd-properties


1. : ℕ
2. ∀k:ℕk. ∀a,b:ℤ.
     ((|b| ≤ k)
      ((∃c:ℤ((c gcd(a;b)) a ∈ ℤ))
        ∧ (∃d:ℤ((d gcd(a;b)) b ∈ ℤ))
        ∧ (∃s,t:ℤ(gcd(a;b) ((s a) (t b)) ∈ ℤ))))
3. : ℤ
4. : ℤ
5. b ≠ 0
6. |b| ≤ k
⊢ (∃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
((InstLemma `rem_bounds_z` [⌜a⌝;⌜b⌝]⋅ THENA Auto)
   THEN (InstHyp [⌜1⌝;⌜b⌝;⌜rem b⌝2⋅ THENA Auto)
   THEN ExRepD
   THEN Thin 2) }

1
1. : ℕ
2. : ℤ
3. : ℤ
4. b ≠ 0
5. |b| ≤ k
6. |a rem b| < |b|
7. : ℤ
8. (c gcd(b;a rem b)) b ∈ ℤ
9. : ℤ
10. (d gcd(b;a rem b)) (a rem b) ∈ ℤ
11. : ℤ
12. : ℤ
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)) ∈ ℤ))


Latex:


Latex:

1.  k  :  \mBbbN{}
2.  \mforall{}k:\mBbbN{}k.  \mforall{}a,b:\mBbbZ{}.
          ((|b|  \mleq{}  k)
          {}\mRightarrow{}  ((\mexists{}c:\mBbbZ{}.  ((c  *  gcd(a;b))  =  a))
                \mwedge{}  (\mexists{}d:\mBbbZ{}.  ((d  *  gcd(a;b))  =  b))
                \mwedge{}  (\mexists{}s,t:\mBbbZ{}.  (gcd(a;b)  =  ((s  *  a)  +  (t  *  b))))))
3.  a  :  \mBbbZ{}
4.  b  :  \mBbbZ{}
5.  b  \mneq{}  0
6.  |b|  \mleq{}  k
\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:
((InstLemma  `rem\_bounds\_z`  [\mkleeneopen{}a\mkleeneclose{};\mkleeneopen{}b\mkleeneclose{}]\mcdot{}  THENA  Auto)
  THEN  (InstHyp  [\mkleeneopen{}k  -  1\mkleeneclose{};\mkleeneopen{}b\mkleeneclose{};\mkleeneopen{}a  rem  b\mkleeneclose{}]  2\mcdot{}  THENA  Auto)
  THEN  ExRepD
  THEN  Thin  2)




Home Index