helm/software/matita/library/Z/sigma_p.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
   8 (*      ||A||       E.Tassi, S.Zacchiroli                                 *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU Lesser General Public License Version 2.1         *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "Z/times.ma".
  16 include "nat/primes.ma".
  17 include "nat/ord.ma".
  18 include "nat/generic_iter_p.ma".
  19
  20 (* sigma_p in Z is a specialization of iter_p_gen *)
  21 definition sigma_p: nat \to (nat \to bool) \to (nat \to Z) \to Z \def
  22 \lambda n, p, g. (iter_p_gen n p Z g OZ Zplus).
  23
  24 theorem symmetricZPlus: symmetric Z Zplus.
  25 change with (\forall a,b:Z. (Zplus a b) = (Zplus b a)).
  26 intros.
  27 rewrite > sym_Zplus.
  28 reflexivity.
  29 qed.
  30
  31 theorem true_to_sigma_p_Sn:
  32 \forall n:nat. \forall p:nat \to bool. \forall g:nat \to Z.
  33 p n = true \to sigma_p (S n) p g =
  34 (g n)+(sigma_p n p g).
  35 intros.
  36 unfold sigma_p.
  37 apply true_to_iter_p_gen_Sn.
  38 assumption.
  39 qed.
  40
  41 theorem false_to_sigma_p_Sn:
  42 \forall n:nat. \forall p:nat \to bool. \forall g:nat \to Z.
  43 p n = false \to sigma_p (S n) p g = sigma_p n p g.
  44 intros.
  45 unfold sigma_p.
  46 apply false_to_iter_p_gen_Sn.
  47 assumption.
  48 qed.
  49
  50 theorem eq_sigma_p: \forall p1,p2:nat \to bool.
  51 \forall g1,g2: nat \to Z.\forall n.
  52 (\forall x.  x < n \to p1 x = p2 x) \to
  53 (\forall x.  x < n \to g1 x = g2 x) \to
  54 sigma_p n p1 g1 = sigma_p n p2 g2.
  55 intros.
  56 unfold sigma_p.
  57 apply eq_iter_p_gen;
  58   assumption.
  59 qed.
  60
  61 theorem eq_sigma_p1: \forall p1,p2:nat \to bool.
  62 \forall g1,g2: nat \to Z.\forall n.
  63 (\forall x.  x < n \to p1 x = p2 x) \to
  64 (\forall x.  x < n \to p1 x = true \to g1 x = g2 x) \to
  65 sigma_p n p1 g1 = sigma_p n p2 g2.
  66 intros.
  67 unfold sigma_p.
  68 apply eq_iter_p_gen1;
  69   assumption.
  70 qed.
  71
  72 theorem sigma_p_false:
  73 \forall g: nat \to Z.\forall n.sigma_p n (\lambda x.false) g = O.
  74 intros.
  75 unfold sigma_p.
  76 apply iter_p_gen_false.
  77 qed.
  78
  79 theorem sigma_p_plus: \forall n,k:nat.\forall p:nat \to bool.
  80 \forall g: nat \to Z.
  81 sigma_p (k+n) p g
  82 = sigma_p k (\lambda x.p (x+n)) (\lambda x.g (x+n)) + sigma_p n p g.
  83 intros.
  84 unfold sigma_p.
  85 apply (iter_p_gen_plusA Z n k p g OZ Zplus)
  86 [ apply symmetricZPlus.
  87 | intros.
  88   apply cic:/matita/Z/plus/Zplus_z_OZ.con
  89 | apply associative_Zplus
  90 ]
  91 qed.
  92
  93 theorem false_to_eq_sigma_p: \forall n,m:nat.n \le m \to
  94 \forall p:nat \to bool.
  95 \forall g: nat \to Z. (\forall i:nat. n \le i \to i < m \to
  96 p i = false) \to sigma_p m p g = sigma_p n p g.
  97 intros.
  98 unfold sigma_p.
  99 apply (false_to_eq_iter_p_gen);
 100   assumption.
 101 qed.
 102
 103 theorem sigma_p2 :
 104 \forall n,m:nat.
 105 \forall p1,p2:nat \to bool.
 106 \forall g: nat \to nat \to Z.
 107 sigma_p (n*m)
 108   (\lambda x.andb (p1 (div x m)) (p2 (mod x m)))
 109   (\lambda x.g (div x m) (mod x m)) =
 110 sigma_p n p1
 111   (\lambda x.sigma_p m p2 (g x)).
 112 intros.
 113 unfold sigma_p.
 114 apply (iter_p_gen2 n m p1 p2 Z g OZ Zplus)
 115 [ apply symmetricZPlus
 116 | apply associative_Zplus
 117 | intros.
 118   apply Zplus_z_OZ
 119 ]
 120 qed.
 121
 122 (* a stronger, dependent version, required e.g. for dirichlet product *)
 123
 124 theorem sigma_p2' :
 125 \forall n,m:nat.
 126 \forall p1:nat \to bool.
 127 \forall p2:nat \to nat \to bool.
 128 \forall g: nat \to nat \to Z.
 129 sigma_p (n*m)
 130   (\lambda x.andb (p1 (div x m)) (p2 (div x m) (mod x m)))
 131   (\lambda x.g (div x m) (mod x m)) =
 132 sigma_p n p1
 133   (\lambda x.sigma_p m (p2 x) (g x)).
 134 intros.
 135 unfold sigma_p.
 136 apply (iter_p_gen2' n m p1 p2 Z g OZ Zplus)
 137 [ apply symmetricZPlus
 138 | apply associative_Zplus
 139 | intros.
 140   apply Zplus_z_OZ
 141 ]
 142 qed.
 143
 144 lemma sigma_p_gi: \forall g: nat \to Z.
 145 \forall n,i.\forall p:nat \to bool.i < n \to p i = true \to
 146 sigma_p n p g = g i + sigma_p n (\lambda x. andb (p x) (notb (eqb x i))) g.
 147 intros.
 148 unfold sigma_p.
 149 apply (iter_p_gen_gi)
 150 [ apply symmetricZPlus
 151 | apply associative_Zplus
 152 | intros.
 153   apply Zplus_z_OZ
 154 | assumption
 155 | assumption
 156 ]
 157 qed.
 158
 159 theorem eq_sigma_p_gh:
 160 \forall g: nat \to Z.
 161 \forall h,h1: nat \to nat.\forall n,n1.
 162 \forall p1,p2:nat \to bool.
 163 (\forall i. i < n \to p1 i = true \to p2 (h i) = true) \to
 164 (\forall i. i < n \to p1 i = true \to h1 (h i) = i) \to
 165 (\forall i. i < n \to p1 i = true \to h i < n1) \to
 166 (\forall j. j < n1 \to p2 j = true \to p1 (h1 j) = true) \to
 167 (\forall j. j < n1 \to p2 j = true \to h (h1 j) = j) \to
 168 (\forall j. j < n1 \to p2 j = true \to h1 j < n) \to
 169 sigma_p n p1 (\lambda x.g(h x)) = sigma_p n1 p2 g.
 170 intros.
 171 unfold sigma_p.
 172 apply (eq_iter_p_gen_gh Z OZ Zplus ? ? ? g h h1 n n1 p1 p2)
 173 [ apply symmetricZPlus
 174 | apply associative_Zplus
 175 | intros.
 176   apply Zplus_z_OZ
 177 | assumption
 178 | assumption
 179 | assumption
 180 | assumption
 181 | assumption
 182 | assumption
 183 ]
 184 qed.
 185
 186
 187 theorem divides_exp_to_lt_ord:\forall n,m,j,p. O < n \to prime p \to
 188 p \ndivides n \to j \divides n*(exp p m) \to ord j p < S m.
 189 intros.
 190 cut (m = ord (n*(exp p m)) p)
 191   [apply le_S_S.
 192    rewrite > Hcut.
 193    apply divides_to_le_ord
 194     [elim (le_to_or_lt_eq ? ? (le_O_n j))
 195       [assumption
 196       |apply False_ind.
 197        apply (lt_to_not_eq ? ? H).
 198        elim H3.
 199        rewrite < H4 in H5.simplify in H5.
 200        elim (times_O_to_O ? ? H5)
 201         [apply sym_eq.assumption
 202         |apply False_ind.
 203          apply (not_le_Sn_n O).
 204          rewrite < H6 in \vdash (? ? %).
 205          apply lt_O_exp.
 206          elim H1.apply lt_to_le.assumption
 207         ]
 208       ]
 209     |rewrite > (times_n_O O).
 210      apply lt_times
 211       [assumption|apply lt_O_exp.apply (prime_to_lt_O ? H1)]
 212     |assumption
 213     |assumption
 214     ]
 215   |unfold ord.
 216    rewrite > (p_ord_exp1 p ? m n)
 217     [reflexivity
 218     |apply (prime_to_lt_O ? H1)
 219     |assumption
 220     |apply sym_times
 221     ]
 222   ]
 223 qed.
 224
 225 theorem divides_exp_to_divides_ord_rem:\forall n,m,j,p. O < n \to prime p \to
 226 p \ndivides n \to j \divides n*(exp p m) \to ord_rem j p \divides n.
 227 intros.
 228 cut (O < j)
 229   [cut (n = ord_rem (n*(exp p m)) p)
 230     [rewrite > Hcut1.
 231      apply divides_to_divides_ord_rem
 232       [assumption
 233       |rewrite > (times_n_O O).
 234        apply lt_times
 235         [assumption|apply lt_O_exp.apply (prime_to_lt_O ? H1)]
 236       |assumption
 237       |assumption
 238       ]
 239     |unfold ord_rem.
 240      rewrite > (p_ord_exp1 p ? m n)
 241       [reflexivity
 242       |apply (prime_to_lt_O ? H1)
 243       |assumption
 244       |apply sym_times
 245       ]
 246     ]
 247   |elim (le_to_or_lt_eq ? ? (le_O_n j))
 248     [assumption
 249     |apply False_ind.
 250      apply (lt_to_not_eq ? ? H).
 251      elim H3.
 252      rewrite < H4 in H5.simplify in H5.
 253      elim (times_O_to_O ? ? H5)
 254       [apply sym_eq.assumption
 255       |apply False_ind.
 256        apply (not_le_Sn_n O).
 257        rewrite < H6 in \vdash (? ? %).
 258        apply lt_O_exp.
 259        elim H1.apply lt_to_le.assumption
 260       ]
 261     ]
 262   ]
 263 qed.
 264
 265
 266 theorem sigma_p_divides_b:
 267 \forall n,m,p:nat.O < n \to prime p \to Not (divides p n) \to
 268 \forall g: nat \to Z.
 269 sigma_p (S (n*(exp p m))) (\lambda x.divides_b x (n*(exp p m))) g =
 270 sigma_p (S n) (\lambda x.divides_b x n)
 271   (\lambda x.sigma_p (S m) (\lambda y.true) (\lambda y.g (x*(exp p y)))).
 272 intros.
 273 unfold sigma_p.
 274 apply (iter_p_gen_divides Z OZ Zplus n m p ? ? ? g)
 275 [ assumption
 276 | assumption
 277 | assumption
 278 | apply symmetricZPlus
 279 | apply associative_Zplus
 280 | intros.
 281   apply Zplus_z_OZ
 282 ]
 283 qed.
 284
 285
 286 (* sigma_p and Ztimes *)
 287 lemma Ztimes_sigma_pl: \forall z:Z.\forall n:nat.\forall p. \forall f.
 288 z * (sigma_p n p f) = sigma_p n p (\lambda i.z*(f i)).
 289 intros.
 290 apply (distributive_times_plus_iter_p_gen Z Zplus OZ Ztimes n z p f)
 291 [ apply symmetricZPlus
 292 | apply associative_Zplus
 293 | intros.
 294   apply Zplus_z_OZ
 295 | apply symmetric_Ztimes
 296 | apply distributive_Ztimes_Zplus
 297 | intros.
 298   rewrite > (Ztimes_z_OZ a).
 299   reflexivity
 300 ]
 301 qed.
 302
 303 lemma Ztimes_sigma_pr: \forall z:Z.\forall n:nat.\forall p. \forall f.
 304 (sigma_p n p f) * z = sigma_p n p (\lambda i.(f i)*z).
 305 intros.
 306 rewrite < sym_Ztimes.
 307 rewrite > Ztimes_sigma_pl.
 308 apply eq_sigma_p
 309   [intros.reflexivity
 310   |intros.apply sym_Ztimes
 311   ]
 312 qed.
 313
 314
 315 theorem sigma_p_knm:
 316 \forall g: nat \to Z.
 317 \forall h2:nat \to nat \to nat.
 318 \forall h11,h12:nat \to nat.
 319 \forall k,n,m.
 320 \forall p1,p21:nat \to bool.
 321 \forall p22:nat \to nat \to bool.
 322 (\forall x. x < k \to p1 x = true \to
 323 p21 (h11 x) = true \land p22 (h11 x) (h12 x) = true
 324 \land h2 (h11 x) (h12 x) = x
 325 \land (h11 x) < n \land (h12 x) < m) \to
 326 (\forall i,j. i < n \to j < m \to p21 i = true \to p22 i j = true \to
 327 p1 (h2 i j) = true \land
 328 h11 (h2 i j) = i \land h12 (h2 i j) = j
 329 \land h2 i j < k) \to
 330 sigma_p k p1 g=
 331 sigma_p n p21 (\lambda x:nat.sigma_p m (p22 x) (\lambda y. g (h2 x y))).
 332 intros.
 333 unfold sigma_p.
 334 unfold sigma_p in \vdash (? ? ? (? ? ? ? (\lambda x:?.%) ? ?)).
 335 apply iter_p_gen_knm
 336   [ apply symmetricZPlus
 337   |apply associative_Zplus
 338   | intro.
 339     apply (Zplus_z_OZ a)
 340   | exact h11
 341   | exact h12
 342   | assumption
 343   | assumption
 344   ]
 345 qed.
 346
 347
 348 theorem sigma_p2_eq:
 349 \forall g: nat \to nat \to Z.
 350 \forall h11,h12,h21,h22: nat \to nat \to nat.
 351 \forall n1,m1,n2,m2.
 352 \forall p11,p21:nat \to bool.
 353 \forall p12,p22:nat \to nat \to bool.
 354 (\forall i,j. i < n2 \to j < m2 \to p21 i = true \to p22 i j = true \to
 355 p11 (h11 i j) = true \land p12 (h11 i j) (h12 i j) = true
 356 \land h21 (h11 i j) (h12 i j) = i \land h22 (h11 i j) (h12 i j) = j
 357 \land h11 i j < n1 \land h12 i j < m1) \to
 358 (\forall i,j. i < n1 \to j < m1 \to p11 i = true \to p12 i j = true \to
 359 p21 (h21 i j) = true \land p22 (h21 i j) (h22 i j) = true
 360 \land h11 (h21 i j) (h22 i j) = i \land h12 (h21 i j) (h22 i j) = j
 361 \land (h21 i j) < n2 \land (h22 i j) < m2) \to
 362 sigma_p n1 p11 (\lambda x:nat .sigma_p m1 (p12 x) (\lambda y. g x y)) =
 363 sigma_p n2 p21 (\lambda x:nat .sigma_p m2 (p22 x) (\lambda y. g (h11 x y) (h12 x y))).
 364 intros.
 365 unfold sigma_p.
 366 unfold sigma_p in \vdash (? ? (? ? ? ? (\lambda x:?.%) ? ?) ?).
 367 unfold sigma_p in \vdash (? ? ? (? ? ? ? (\lambda x:?.%) ? ?)).
 368
 369 apply(iter_p_gen_2_eq Z OZ Zplus ? ? ? g h11 h12 h21 h22 n1 m1 n2 m2 p11 p21 p12 p22)
 370 [ apply symmetricZPlus
 371 | apply associative_Zplus
 372 | intro.
 373   apply (Zplus_z_OZ a)
 374 | assumption
 375 | assumption
 376 ]
 377 qed.
 378
 379
 380
 381
 382 (*
 383
 384
 385
 386
 387
 388 rewrite < sigma_p2'.
 389 letin ha:= (\lambda x,y.(((h11 x y)*m1) + (h12 x y))).
 390 letin ha12:= (\lambda x.(h21 (x/m1) (x \mod m1))).
 391 letin ha22:= (\lambda x.(h22 (x/m1) (x \mod m1))).
 392
 393 apply (trans_eq ? ?
 394 (sigma_p n2 p21 (\lambda x:nat. sigma_p m2 (p22 x)
 395  (\lambda y:nat.(g (((h11 x y)*m1+(h12 x y))/m1) (((h11 x y)*m1+(h12 x y))\mod m1)) ) ) ))
 396 [
 397   apply (sigma_p_knm (\lambda e. (g (e/m1) (e \mod m1))) ha ha12 ha22);intros
 398   [ elim (and_true ? ? H3).
 399     cut(O \lt m1)
 400     [ cut(x/m1 < n1)
 401       [ cut((x \mod m1) < m1)
 402         [ elim (H1 ? ? Hcut1 Hcut2 H4 H5).
 403           elim H6.clear H6.
 404           elim H8.clear H8.
 405           elim H6.clear H6.
 406           elim H8.clear H8.
 407           split
 408           [ split
 409             [ split
 410               [ split
 411                 [ assumption
 412                 | assumption
 413                 ]
 414               | rewrite > H11.
 415                 rewrite > H10.
 416                 apply sym_eq.
 417                 apply div_mod.
 418                 assumption
 419               ]
 420             | assumption
 421             ]
 422           | assumption
 423           ]
 424         | apply lt_mod_m_m.
 425           assumption
 426         ]
 427       | apply (lt_times_n_to_lt m1)
 428         [ assumption
 429         | apply (le_to_lt_to_lt ? x)
 430           [ apply (eq_plus_to_le ? ? (x \mod m1)).
 431             apply div_mod.
 432             assumption
 433           | assumption
 434         ]
 435       ]
 436     ]
 437     | apply not_le_to_lt.unfold.intro.
 438       generalize in match H2.
 439       apply (le_n_O_elim ? H6).
 440       rewrite < times_n_O.
 441       apply le_to_not_lt.
 442       apply le_O_n.
 443     ]
 444   | elim (H ? ? H2 H3 H4 H5).
 445     elim H6.clear H6.
 446     elim H8.clear H8.
 447     elim H6.clear H6.
 448     elim H8.clear H8.
 449     cut(((h11 i j)*m1 + (h12 i j))/m1 = (h11 i j))
 450     [ cut(((h11 i j)*m1 + (h12 i j)) \mod m1 = (h12 i j))
 451       [ split
 452         [ split
 453           [ split
 454             [ apply true_to_true_to_andb_true
 455               [ rewrite > Hcut.
 456                 assumption
 457               | rewrite > Hcut1.
 458                 rewrite > Hcut.
 459                 assumption
 460               ]
 461             | rewrite > Hcut1.
 462               rewrite > Hcut.
 463               assumption
 464             ]
 465           | rewrite > Hcut1.
 466             rewrite > Hcut.
 467             assumption
 468           ]
 469         | cut(O \lt m1)
 470           [ cut(O \lt n1)
 471             [ apply (lt_to_le_to_lt ? ((h11 i j)*m1 + m1) )
 472               [ apply (lt_plus_r).
 473                 assumption
 474               | rewrite > sym_plus.
 475                 rewrite > (sym_times (h11 i j) m1).
 476                 rewrite > times_n_Sm.
 477                 rewrite > sym_times.
 478                 apply (le_times_l).
 479                 assumption
 480               ]
 481             | apply not_le_to_lt.unfold.intro.
 482               generalize in match H9.
 483               apply (le_n_O_elim ? H8).
 484               apply le_to_not_lt.
 485               apply le_O_n
 486             ]
 487           | apply not_le_to_lt.unfold.intro.
 488             generalize in match H7.
 489             apply (le_n_O_elim ? H8).
 490             apply le_to_not_lt.
 491             apply le_O_n
 492           ]
 493         ]
 494       | rewrite > (mod_plus_times m1 (h11 i j) (h12 i j)).
 495         reflexivity.
 496         assumption
 497       ]
 498     | rewrite > (div_plus_times m1 (h11 i j) (h12 i j)).
 499       reflexivity.
 500       assumption
 501     ]
 502   ]
 503 | apply (eq_sigma_p1)
 504   [ intros. reflexivity
 505   | intros.
 506     apply (eq_sigma_p1)
 507     [ intros. reflexivity
 508     | intros.
 509       rewrite > (div_plus_times)
 510       [ rewrite > (mod_plus_times)
 511         [ reflexivity
 512         | elim (H x x1 H2 H4 H3 H5).
 513           assumption
 514         ]
 515       | elim (H x x1 H2 H4 H3 H5).
 516         assumption
 517       ]
 518     ]
 519   ]
 520 ]
 521 qed.
 522
 523 rewrite < sigma_p2' in \vdash (? ? ? %).
 524 apply sym_eq.
 525 letin h := (\lambda x.(h11 (x/m2) (x\mod m2))*m1 + (h12 (x/m2) (x\mod m2))).
 526 letin h1 := (\lambda x.(h21 (x/m1) (x\mod m1))*m2 + (h22 (x/m1) (x\mod m1))).
 527 apply (trans_eq ? ?
 528   (sigma_p (n2*m2) (\lambda x:nat.p21 (x/m2)\land p22 (x/m2) (x\mod m2))
 529   (\lambda x:nat.g ((h x)/m1) ((h x)\mod m1))))
 530   [clear h.clear h1.
 531    apply eq_sigma_p1
 532     [intros.reflexivity
 533     |intros.
 534      cut (O < m2)
 535       [cut (x/m2 < n2)
 536         [cut (x \mod m2 < m2)
 537           [elim (and_true ? ? H3).
 538            elim (H ? ? Hcut1 Hcut2 H4 H5).
 539            elim H6.clear H6.
 540            elim H8.clear H8.
 541            elim H6.clear H6.
 542            elim H8.clear H8.
 543            apply eq_f2
 544             [apply sym_eq.
 545              apply div_plus_times.
 546              assumption
 547             |
 548               apply sym_eq.
 549               apply mod_plus_times.
 550               assumption
 551             ]
 552           |apply lt_mod_m_m.
 553            assumption
 554           ]
 555         |apply (lt_times_n_to_lt m2)
 556           [assumption
 557           |apply (le_to_lt_to_lt ? x)
 558             [apply (eq_plus_to_le ? ? (x \mod m2)).
 559              apply div_mod.
 560              assumption
 561             |assumption
 562             ]
 563           ]
 564         ]
 565       |apply not_le_to_lt.unfold.intro.
 566        generalize in match H2.
 567        apply (le_n_O_elim ? H4).
 568        rewrite < times_n_O.
 569        apply le_to_not_lt.
 570        apply le_O_n
 571       ]
 572     ]
 573   |apply (eq_sigma_p_gh ? h h1);intros
 574     [cut (O < m2)
 575       [cut (i/m2 < n2)
 576         [cut (i \mod m2 < m2)
 577           [elim (and_true ? ? H3).
 578            elim (H ? ? Hcut1 Hcut2 H4 H5).
 579            elim H6.clear H6.
 580            elim H8.clear H8.
 581            elim H6.clear H6.
 582            elim H8.clear H8.
 583            cut ((h11 (i/m2) (i\mod m2)*m1+h12 (i/m2) (i\mod m2))/m1 =
 584                  h11 (i/m2) (i\mod m2))
 585             [cut ((h11 (i/m2) (i\mod m2)*m1+h12 (i/m2) (i\mod m2))\mod m1 =
 586                   h12 (i/m2) (i\mod m2))
 587               [rewrite > Hcut3.
 588                rewrite > Hcut4.
 589                rewrite > H6.
 590                rewrite > H12.
 591                reflexivity
 592               |apply mod_plus_times.
 593                assumption
 594               ]
 595             |apply div_plus_times.
 596              assumption
 597             ]
 598           |apply lt_mod_m_m.
 599            assumption
 600           ]
 601         |apply (lt_times_n_to_lt m2)
 602           [assumption
 603           |apply (le_to_lt_to_lt ? i)
 604             [apply (eq_plus_to_le ? ? (i \mod m2)).
 605              apply div_mod.
 606              assumption
 607             |assumption
 608             ]
 609           ]
 610         ]
 611       |apply not_le_to_lt.unfold.intro.
 612        generalize in match H2.
 613        apply (le_n_O_elim ? H4).
 614        rewrite < times_n_O.
 615        apply le_to_not_lt.
 616        apply le_O_n
 617       ]
 618     |cut (O < m2)
 619       [cut (i/m2 < n2)
 620         [cut (i \mod m2 < m2)
 621           [elim (and_true ? ? H3).
 622            elim (H ? ? Hcut1 Hcut2 H4 H5).
 623            elim H6.clear H6.
 624            elim H8.clear H8.
 625            elim H6.clear H6.
 626            elim H8.clear H8.
 627            cut ((h11 (i/m2) (i\mod m2)*m1+h12 (i/m2) (i\mod m2))/m1 =
 628                  h11 (i/m2) (i\mod m2))
 629             [cut ((h11 (i/m2) (i\mod m2)*m1+h12 (i/m2) (i\mod m2))\mod m1 =
 630                   h12 (i/m2) (i\mod m2))
 631               [rewrite > Hcut3.
 632                rewrite > Hcut4.
 633                rewrite > H10.
 634                rewrite > H11.
 635                apply sym_eq.
 636                apply div_mod.
 637                assumption
 638               |apply mod_plus_times.
 639                assumption
 640               ]
 641             |apply div_plus_times.
 642              assumption
 643             ]
 644           |apply lt_mod_m_m.
 645            assumption
 646           ]
 647         |apply (lt_times_n_to_lt m2)
 648           [assumption
 649           |apply (le_to_lt_to_lt ? i)
 650             [apply (eq_plus_to_le ? ? (i \mod m2)).
 651              apply div_mod.
 652              assumption
 653             |assumption
 654             ]
 655           ]
 656         ]
 657       |apply not_le_to_lt.unfold.intro.
 658        generalize in match H2.
 659        apply (le_n_O_elim ? H4).
 660        rewrite < times_n_O.
 661        apply le_to_not_lt.
 662        apply le_O_n
 663       ]
 664     |cut (O < m2)
 665       [cut (i/m2 < n2)
 666         [cut (i \mod m2 < m2)
 667           [elim (and_true ? ? H3).
 668            elim (H ? ? Hcut1 Hcut2 H4 H5).
 669            elim H6.clear H6.
 670            elim H8.clear H8.
 671            elim H6.clear H6.
 672            elim H8.clear H8.
 673            apply lt_times_plus_times
 674             [assumption|assumption]
 675           |apply lt_mod_m_m.
 676            assumption
 677           ]
 678         |apply (lt_times_n_to_lt m2)
 679           [assumption
 680           |apply (le_to_lt_to_lt ? i)
 681             [apply (eq_plus_to_le ? ? (i \mod m2)).
 682              apply div_mod.
 683              assumption
 684             |assumption
 685             ]
 686           ]
 687         ]
 688       |apply not_le_to_lt.unfold.intro.
 689        generalize in match H2.
 690        apply (le_n_O_elim ? H4).
 691        rewrite < times_n_O.
 692        apply le_to_not_lt.
 693        apply le_O_n
 694       ]
 695     |cut (O < m1)
 696       [cut (j/m1 < n1)
 697         [cut (j \mod m1 < m1)
 698           [elim (and_true ? ? H3).
 699            elim (H1 ? ? Hcut1 Hcut2 H4 H5).
 700            elim H6.clear H6.
 701            elim H8.clear H8.
 702            elim H6.clear H6.
 703            elim H8.clear H8.
 704            cut ((h21 (j/m1) (j\mod m1)*m2+h22 (j/m1) (j\mod m1))/m2 =
 705                  h21 (j/m1) (j\mod m1))
 706             [cut ((h21 (j/m1) (j\mod m1)*m2+h22 (j/m1) (j\mod m1))\mod m2 =
 707                   h22 (j/m1) (j\mod m1))
 708               [rewrite > Hcut3.
 709                rewrite > Hcut4.
 710                rewrite > H6.
 711                rewrite > H12.
 712                reflexivity
 713               |apply mod_plus_times.
 714                assumption
 715               ]
 716             |apply div_plus_times.
 717              assumption
 718             ]
 719           |apply lt_mod_m_m.
 720            assumption
 721           ]
 722         |apply (lt_times_n_to_lt m1)
 723           [assumption
 724           |apply (le_to_lt_to_lt ? j)
 725             [apply (eq_plus_to_le ? ? (j \mod m1)).
 726              apply div_mod.
 727              assumption
 728             |assumption
 729             ]
 730           ]
 731         ]
 732       |apply not_le_to_lt.unfold.intro.
 733        generalize in match H2.
 734        apply (le_n_O_elim ? H4).
 735        rewrite < times_n_O.
 736        apply le_to_not_lt.
 737        apply le_O_n
 738       ]
 739     |cut (O < m1)
 740       [cut (j/m1 < n1)
 741         [cut (j \mod m1 < m1)
 742           [elim (and_true ? ? H3).
 743            elim (H1 ? ? Hcut1 Hcut2 H4 H5).
 744            elim H6.clear H6.
 745            elim H8.clear H8.
 746            elim H6.clear H6.
 747            elim H8.clear H8.
 748            cut ((h21 (j/m1) (j\mod m1)*m2+h22 (j/m1) (j\mod m1))/m2 =
 749                  h21 (j/m1) (j\mod m1))
 750             [cut ((h21 (j/m1) (j\mod m1)*m2+h22 (j/m1) (j\mod m1))\mod m2 =
 751                   h22 (j/m1) (j\mod m1))
 752               [rewrite > Hcut3.
 753                rewrite > Hcut4.
 754                rewrite > H10.
 755                rewrite > H11.
 756                apply sym_eq.
 757                apply div_mod.
 758                assumption
 759               |apply mod_plus_times.
 760                assumption
 761               ]
 762             |apply div_plus_times.
 763              assumption
 764             ]
 765           |apply lt_mod_m_m.
 766            assumption
 767           ]
 768         |apply (lt_times_n_to_lt m1)
 769           [assumption
 770           |apply (le_to_lt_to_lt ? j)
 771             [apply (eq_plus_to_le ? ? (j \mod m1)).
 772              apply div_mod.
 773              assumption
 774             |assumption
 775             ]
 776           ]
 777         ]
 778       |apply not_le_to_lt.unfold.intro.
 779        generalize in match H2.
 780        apply (le_n_O_elim ? H4).
 781        rewrite < times_n_O.
 782        apply le_to_not_lt.
 783        apply le_O_n
 784       ]
 785     |cut (O < m1)
 786       [cut (j/m1 < n1)
 787         [cut (j \mod m1 < m1)
 788           [elim (and_true ? ? H3).
 789            elim (H1 ? ? Hcut1 Hcut2 H4 H5).
 790            elim H6.clear H6.
 791            elim H8.clear H8.
 792            elim H6.clear H6.
 793            elim H8.clear H8.
 794            apply (lt_times_plus_times ? ? ? m2)
 795             [assumption|assumption]
 796           |apply lt_mod_m_m.
 797            assumption
 798           ]
 799         |apply (lt_times_n_to_lt m1)
 800           [assumption
 801           |apply (le_to_lt_to_lt ? j)
 802             [apply (eq_plus_to_le ? ? (j \mod m1)).
 803              apply div_mod.
 804              assumption
 805             |assumption
 806             ]
 807           ]
 808         ]
 809       |apply not_le_to_lt.unfold.intro.
 810        generalize in match H2.
 811        apply (le_n_O_elim ? H4).
 812        rewrite < times_n_O.
 813        apply le_to_not_lt.
 814        apply le_O_n
 815       ]
 816     ]
 817   ]
 818 qed.
 819 *)
 820
 821