---

Step * 1 1 1 2 2 1 2 1 of Lemma chinese-remainder1


1. r : ℤ
2. s : {s':ℤ| CoPrime(r,s')} 
3. a : ℤ
4. b : ℤ
5. g : ℕ
6. a1 : ℤ
7. b1 : ℤ
8. x : ℤ
9. y : ℤ
10. r = a1 ∈ ℤ
11. s = b1 ∈ ℤ
12. ((x * r) + (y * s)) = 1 ∈ ℤ
13. g = 1 ∈ ℤ
14. ¬(r = 0 ∈ ℤ)
15. ¬(s = 0 ∈ ℤ)
16. r * s ≠ 0
17. ((a * y * s) + (b * x * r))
= (((((a * y * s) + (b * x * r)) ÷ r * s) * r * s) + ((a * y * s) + (b * x * r) rem r * s))
∈ ℤ
⊢ ((a * y * s) + (b * x * r) rem r * s) ≡ a mod r
BY
{ (Assert ((a * y * s) + (b * x * r)) ≡ a mod r BY
         ((Subst' (y * s) = (1 - x * r) ∈ ℤ 0 THEN Auto')
          THEN SimplifyEqMod
          THEN Auto
          THEN (RW IntNormC 0 THEN Auto)
          THEN RelRST
          THEN Auto)) }

1
1. r : ℤ
2. s : {s':ℤ| CoPrime(r,s')} 
3. a : ℤ
4. b : ℤ
5. g : ℕ
6. a1 : ℤ
7. b1 : ℤ
8. x : ℤ
9. y : ℤ
10. r = a1 ∈ ℤ
11. s = b1 ∈ ℤ
12. ((x * r) + (y * s)) = 1 ∈ ℤ
13. g = 1 ∈ ℤ
14. ¬(r = 0 ∈ ℤ)
15. ¬(s = 0 ∈ ℤ)
16. r * s ≠ 0
17. ((a * y * s) + (b * x * r))
= (((((a * y * s) + (b * x * r)) ÷ r * s) * r * s) + ((a * y * s) + (b * x * r) rem r * s))
∈ ℤ
18. ((a * y * s) + (b * x * r)) ≡ a mod r
⊢ ((a * y * s) + (b * x * r) rem r * s) ≡ a mod r

---

Latex:

---

Latex:

1.  r  :  \mBbbZ{}
2.  s  :  \{s':\mBbbZ{}|  CoPrime(r,s')\} 
3.  a  :  \mBbbZ{}
4.  b  :  \mBbbZ{}
5.  g  :  \mBbbN{}
6.  a1  :  \mBbbZ{}
7.  b1  :  \mBbbZ{}
8.  x  :  \mBbbZ{}
9.  y  :  \mBbbZ{}
10.  r  =  a1
11.  s  =  b1
12.  ((x  *  r)  +  (y  *  s))  =  1
13.  g  =  1
14.  \mneg{}(r  =  0)
15.  \mneg{}(s  =  0)
16.  r  *  s  \mneq{}  0
17.  ((a  *  y  *  s)  +  (b  *  x  *  r))
=  (((((a  *  y  *  s)  +  (b  *  x  *  r))  \mdiv{}  r  *  s)  *  r  *  s)  +  ((a  *  y  *  s)  +  (b  *  x  *  r)  rem  r  *  s))
\mvdash{}  ((a  *  y  *  s)  +  (b  *  x  *  r)  rem  r  *  s)  \mequiv{}  a  mod  r


By

---

Latex:
(Assert  ((a  *  y  *  s)  +  (b  *  x  *  r))  \mequiv{}  a  mod  r  BY
              ((Subst'  (y  *  s)  =  (1  -  x  *  r)  0  THEN  Auto')
                THEN  SimplifyEqMod
                THEN  Auto
                THEN  (RW  IntNormC  0  THEN  Auto)
                THEN  RelRST
                THEN  Auto))

---

Home Index