Library rt.util.div_mod

Require Import Arith Omega Nat.
Require Import rt.util.tactics rt.util.ssromega rt.util.nat.


  Definition div_floor (x y: nat) : nat := x %/ y.
  Definition div_ceil (x y: nat) := if y %| x then x %/ y else (x %/ y).+1.

  Lemma ltn_div_trunc :
    ∀ m n d,
      d > 0 →
      m %/ d < n %/ d →
      m < n.

  Lemma subndiv_eq_mod:
    ∀ n d, n - n %/ d × d = n %% d.

  Lemma divSn_cases :
    ∀ n d,
      d > 1 →
      (n %/ d = n.+1 %/d ∧ n %% d + 1 = n.+1 %% d) ∨
      (n %/ d + 1 = n.+1 %/ d).

  Lemma ceil_neq0 :
    ∀ x y,
      x > 0 →
      y > 0 →
      div_ceil x y > 0.

  Lemma leq_divceil2r :
    ∀ d m n,
      d > 0 →
      m ≤ n →
      div_ceil m d ≤ div_ceil n d.

(* Versions of eqn_modDl and eqn_modDl in Prop *)

  Lemma eq_modDl: ∀ p m n d, (p + m = p + n %[mod d]) ↔ (m = n %[mod d]).

  Lemma eq_modDr: ∀ p m n d, (m + p = n + p %[mod d]) ↔ (m = n %[mod d]).

  (* If a(n)= b+a (n) then b is a multiple of c 
    Proposed name modnD_k *)

  Lemma modulo_exists: ∀ a b c,
    c>0 → a = b + a %[mod c] → ∃ k, b = k×c.

  (* If (a+1)[n+1]=0 then a[n+1]=n *)
  Lemma modnS_eq : ∀ a n, a.+1 %% n.+1 =0 ↔ a %% n.+1 = n.

  (* Incrementing the integer under a modulo either increments the result or yields 0 *)

  Lemma modnSor': ∀ a n, a.+1 %% n = (a %% n).+1 ∨ (a.+1 %% n =0).

  Lemma modnSor: ∀ a n, a.+1 %% n.+1 = (a %% n.+1).+1 ∨ (a.+1 %% n.+1 =0).

  (* Old version of the lemma which is now covered by modnSor and modnS_eq *)

  Lemma modulo_cases : ∀ a c,
    a.+1 %% c.+1 = (a %% c.+1).+1 ∨ (a.+1 %% c.+1 =0 ∧ a %% c.+1 =c).

  Lemma ceil_eq1: ∀ a c, a > 0 → a ≤ c → div_ceil a c = 1.

  Lemma ceil_suba: ∀ a c, c > 0 → a > c → div_ceil a c = (div_ceil (a-c) c).+1.

  Lemma mod_eq: ∀ a b, a%%b = a - a%/b × b.

  Lemma mod_elim:
    ∀ a b c,
      c>0 →
      b<c →
      (a + c - b)%%c = ( if a%%c ≥ b then (a%%c - b) else (a%%c + c - b)).