---

Step * of Lemma trial-division_wf

∀[n:ℕ+]. ∀[L:{2...} List].  (trial-division(n;L) ∈ ∃n1:ℤ [(n1 < n ∧ (2 ≤ n1) ∧ (n1 | n))] + Top)
BY
{ ((InductionOnList THEN Auto)
   THEN Unfold `trial-division` 0
   THEN Reduce 0
   THEN Try (Fold `trial-division` 0)
   THEN Try (Complete (Auto))
   THEN GenConclAtAddr [2;1]
   THEN D -2
   THEN Reduce 0
   THEN Try (Complete (Auto))
   THEN AutoSplit
   THEN (CallByValueReduce 0 THENA Auto)
   THEN (RWO "better-gcd-gcd" 0 THENA Auto)
   THEN AutoSplit
   THEN Auto
   THEN MemTypeCD
   THEN Auto) }

1
1. n : ℕ+
2. u : {2...}
3. v : {2...} List
4. trial-division(n;v) ∈ ∃n1:ℤ [(n1 < n ∧ (2 ≤ n1) ∧ (n1 | n))] + Top
5. y : Top
6. trial-division(n;v) = (inr y ) ∈ (∃n1:ℤ [(n1 < n ∧ (2 ≤ n1) ∧ (n1 | n))] + Top)
7. u < n
8. 1 < gcd(u;n)
⊢ gcd(u;n) < n

---

Latex:

---

Latex:
\mforall{}[n:\mBbbN{}\msupplus{}].  \mforall{}[L:\{2...\}  List].    (trial-division(n;L)  \mmember{}  \mexists{}n1:\mBbbZ{}  [(n1  <  n  \mwedge{}  (2  \mleq{}  n1)  \mwedge{}  (n1  |  n))]  +  Top)


By

---

Latex:
((InductionOnList  THEN  Auto)
  THEN  Unfold  `trial-division`  0
  THEN  Reduce  0
  THEN  Try  (Fold  `trial-division`  0)
  THEN  Try  (Complete  (Auto))
  THEN  GenConclAtAddr  [2;1]
  THEN  D  -2
  THEN  Reduce  0
  THEN  Try  (Complete  (Auto))
  THEN  AutoSplit
  THEN  (CallByValueReduce  0  THENA  Auto)
  THEN  (RWO  "better-gcd-gcd"  0  THENA  Auto)
  THEN  AutoSplit
  THEN  Auto
  THEN  MemTypeCD
  THEN  Auto)

---

Home Index