Built with Alectryon, running Coq+SerAPI v8.10.0+0.7.0. Coq sources are in this panel; goals and messages will appear in the other. Bubbles () indicate interactive fragments: hover for details, tap to reveal contents. Use Ctrl+↑ Ctrl+↓ to navigate, Ctrl+🖱️ to focus.

(************************************************************************)
(*         *   The Coq Proof Assistant / The Coq Development Team       *)
(*  v      *   INRIA, CNRS and contributors - Copyright 1999-2018       *)
(* <O___,, *       (see CREDITS file for the list of authors)           *)
(*   \VV/  **************************************************************)
(*    //   *    This file is distributed under the terms of the         *)
(*         *     GNU Lesser General Public License Version 2.1          *)
(*         *     (see LICENSE file for the text of the license)         *)
(************************************************************************)

Require Import ZAxioms ZMulOrder ZSgnAbs NZDiv.

Euclidean Division for integers (Trunc convention)

We use here the convention known as Trunc, or Round-Toward-Zero, where a/b is the integer with the largest absolute value to be between zero and the exact fraction. It can be summarized by:

a = bq+r ∧ 0 ≤ |r| < |b| ∧ Sign(r) = Sign(a)

This is the convention of Ocaml and many other systems (C, ASM, ...). This convention is named "T" in the following paper:

R. Boute, "The Euclidean definition of the functions div and mod", ACM Transactions on Programming Languages and Systems, Vol. 14, No.2, pp. 127-144, April 1992.

See files ZDivFloor and ZDivEucl for others conventions.

Module Type ZQuotProp
 (Import A : ZAxiomsSig')
 (Import B : ZMulOrderProp A)
 (Import C : ZSgnAbsProp A B).

We benefit from what already exists for NZ

 Module Import Private_Div.
 Module Quot2Div <: NZDiv A.
  Definition div := quot.
  Definition modulo := A.rem.
  Definition div_wd := quot_wd.
  Definition mod_wd := rem_wd.
  Definition div_mod := quot_rem.
  Definition mod_bound_pos := rem_bound_pos.
 End Quot2Div.
 Module NZQuot := Nop <+ NZDivProp A Quot2Div B.
 End Private_Div.

Ltac pos_or_neg a :=
 let LT := fresh "LT" in
 let LE := fresh "LE" in
 destruct (le_gt_cases 0 a) as [LE|LT]; [|rewrite <- opp_pos_neg in LT].

Another formulation of the main equation

Lemma rem_eq :
 forall a b, b~=0 -> a rem b == a - b*(a÷b).forall a b : t, b ~= 0 -> a rem b == a - b * (a ÷ b)
Proof.forall a b : t, b ~= 0 -> a rem b == a - b * (a ÷ b)
intros.a, b:t
H:b ~= 0
a rem b == a - b * (a ÷ b)
rewrite <- add_move_l.a, b:t
H:b ~= 0
b * (a ÷ b) + a rem b == a
symmetry.a, b:t
H:b ~= 0
a == b * (a ÷ b) + a rem b now apply quot_rem.
Qed.

A few sign rules (simple ones)

Lemma rem_opp_opp : forall a b, b ~= 0 -> (-a) rem (-b) == - (a rem b).forall a b : t, b ~= 0 -> - a rem - b == - (a rem b)
Proof.forall a b : t, b ~= 0 -> - a rem - b == - (a rem b) intros.a, b:t
H:b ~= 0
- a rem - b == - (a rem b) now rewrite rem_opp_r, rem_opp_l. Qed.

Lemma quot_opp_l : forall a b, b ~= 0 -> (-a)÷b == -(a÷b).forall a b : t, b ~= 0 -> - a ÷ b == - (a ÷ b)
Proof.forall a b : t, b ~= 0 -> - a ÷ b == - (a ÷ b)
intros.a, b:t
H:b ~= 0
- a ÷ b == - (a ÷ b)
rewrite <- (mul_cancel_l _ _ b) by trivial.a, b:t
H:b ~= 0
b * (- a ÷ b) == b * - (a ÷ b)
rewrite <- (add_cancel_r _ _ ((-a) rem b)).a, b:t
H:b ~= 0
b * (- a ÷ b) + - a rem b == b * - (a ÷ b) + - a rem b
now rewrite <- quot_rem, rem_opp_l, mul_opp_r, <- opp_add_distr, <- quot_rem.
Qed.

Lemma quot_opp_r : forall a b, b ~= 0 -> a÷(-b) == -(a÷b).forall a b : t, b ~= 0 -> a ÷ - b == - (a ÷ b)
Proof.forall a b : t, b ~= 0 -> a ÷ - b == - (a ÷ b)
intros.a, b:t
H:b ~= 0
a ÷ - b == - (a ÷ b)
assert (-b ~= 0) by (now rewrite eq_opp_l, opp_0).a, b:t
H:b ~= 0
H0:- b ~= 0
a ÷ - b == - (a ÷ b)
rewrite <- (mul_cancel_l _ _ (-b)) by trivial.a, b:t
H:b ~= 0
H0:- b ~= 0
- b * (a ÷ - b) == - b * - (a ÷ b)
rewrite <- (add_cancel_r _ _ (a rem (-b))).a, b:t
H:b ~= 0
H0:- b ~= 0
- b * (a ÷ - b) + a rem - b ==
- b * - (a ÷ b) + a rem - b
now rewrite <- quot_rem, rem_opp_r, mul_opp_opp, <- quot_rem.
Qed.

Lemma quot_opp_opp : forall a b, b ~= 0 -> (-a)÷(-b) == a÷b.forall a b : t, b ~= 0 -> - a ÷ - b == a ÷ b
Proof.forall a b : t, b ~= 0 -> - a ÷ - b == a ÷ b intros.a, b:t
H:b ~= 0
- a ÷ - b == a ÷ b now rewrite quot_opp_r, quot_opp_l, opp_involutive. Qed.

Uniqueness theorems

Theorem quot_rem_unique : forall b q1 q2 r1 r2 : t,
  (0<=r1<b \/ b<r1<=0) -> (0<=r2<b \/ b<r2<=0) ->
  b*q1+r1 == b*q2+r2 -> q1 == q2 /\ r1 == r2.forall b q1 q2 r1 r2 : t,
0 <= r1 < b \/ b < r1 <= 0 ->
0 <= r2 < b \/ b < r2 <= 0 ->
b * q1 + r1 == b * q2 + r2 -> q1 == q2 /\ r1 == r2
Proof.forall b q1 q2 r1 r2 : t,
0 <= r1 < b \/ b < r1 <= 0 ->
0 <= r2 < b \/ b < r2 <= 0 ->
b * q1 + r1 == b * q2 + r2 -> q1 == q2 /\ r1 == r2
intros b q1 q2 r1 r2 Hr1 Hr2 EQ.b, q1, q2, r1, r2:t
Hr1:0 <= r1 < b \/ b < r1 <= 0
Hr2:0 <= r2 < b \/ b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
q1 == q2 /\ r1 == r2
destruct Hr1; destruct Hr2; try (intuition; order).b, q1, q2, r1, r2:t
H:0 <= r1 < b
H0:0 <= r2 < b
EQ:b * q1 + r1 == b * q2 + r2
q1 == q2 /\ r1 == r2
b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
q1 == q2 /\ r1 == r2
apply NZQuot.div_mod_unique with b; trivial.b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
q1 == q2 /\ r1 == r2
rewrite <- (opp_inj_wd r1 r2).b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
q1 == q2 /\ - r1 == - r2
apply NZQuot.div_mod_unique with (-b); trivial.b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
0 <= - r1 < - b
b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
0 <= - r2 < - b
b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
- b * q1 + - r1 == - b * q2 + - r2
rewrite <- opp_lt_mono, opp_nonneg_nonpos; tauto.b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
0 <= - r2 < - b
b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
- b * q1 + - r1 == - b * q2 + - r2
rewrite <- opp_lt_mono, opp_nonneg_nonpos; tauto.b, q1, q2, r1, r2:t
H:b < r1 <= 0
H0:b < r2 <= 0
EQ:b * q1 + r1 == b * q2 + r2
- b * q1 + - r1 == - b * q2 + - r2
now rewrite 2 mul_opp_l, <- 2 opp_add_distr, opp_inj_wd.
Qed.

Theorem quot_unique:
 forall a b q r, 0<=a -> 0<=r<b -> a == b*q + r -> q == a÷b.forall a b q r : t,
0 <= a -> 0 <= r < b -> a == b * q + r -> q == a ÷ b
Proof.forall a b q r : t,
0 <= a -> 0 <= r < b -> a == b * q + r -> q == a ÷ b intros; now apply NZQuot.div_unique with r. Qed.

Theorem rem_unique:
 forall a b q r, 0<=a -> 0<=r<b -> a == b*q + r -> r == a rem b.forall a b q r : t,
0 <= a -> 0 <= r < b -> a == b * q + r -> r == a rem b
Proof.forall a b q r : t,
0 <= a -> 0 <= r < b -> a == b * q + r -> r == a rem b intros; now apply NZQuot.mod_unique with q. Qed.

A division by itself returns 1

Lemma quot_same : forall a, a~=0 -> a÷a == 1.forall a : t, a ~= 0 -> a ÷ a == 1
Proof.forall a : t, a ~= 0 -> a ÷ a == 1
intros.a:t
H:a ~= 0
a ÷ a == 1 pos_or_neg a.a:t
H:a ~= 0
LE:0 <= a
a ÷ a == 1
a:t
H:a ~= 0
LT:0 < - a
a ÷ a == 1 apply NZQuot.div_same; order.a:t
H:a ~= 0
LT:0 < - a
a ÷ a == 1
rewrite <- quot_opp_opp by trivial.a:t
H:a ~= 0
LT:0 < - a
- a ÷ - a == 1 now apply NZQuot.div_same.
Qed.

Lemma rem_same : forall a, a~=0 -> a rem a == 0.forall a : t, a ~= 0 -> a rem a == 0
Proof.forall a : t, a ~= 0 -> a rem a == 0
intros.a:t
H:a ~= 0
a rem a == 0 rewrite rem_eq, quot_same by trivial.a:t
H:a ~= 0
a - a * 1 == 0 nzsimpl.a:t
H:a ~= 0
a - a == 0 apply sub_diag.
Qed.

A division of a small number by a bigger one yields zero.

Theorem quot_small: forall a b, 0<=a<b -> a÷b == 0.forall a b : t, 0 <= a < b -> a ÷ b == 0
Proof.forall a b : t, 0 <= a < b -> a ÷ b == 0 exact NZQuot.div_small. Qed.

Same situation, in term of remulo:

Theorem rem_small: forall a b, 0<=a<b -> a rem b == a.forall a b : t, 0 <= a < b -> a rem b == a
Proof.forall a b : t, 0 <= a < b -> a rem b == a exact NZQuot.mod_small. Qed.

Basic values of divisions and modulo.

Lemma quot_0_l: forall a, a~=0 -> 0÷a == 0.forall a : t, a ~= 0 -> 0 ÷ a == 0
Proof.forall a : t, a ~= 0 -> 0 ÷ a == 0
intros.a:t
H:a ~= 0
0 ÷ a == 0 pos_or_neg a.a:t
H:a ~= 0
LE:0 <= a
0 ÷ a == 0
a:t
H:a ~= 0
LT:0 < - a
0 ÷ a == 0 apply NZQuot.div_0_l; order.a:t
H:a ~= 0
LT:0 < - a
0 ÷ a == 0
rewrite <- quot_opp_opp, opp_0 by trivial.a:t
H:a ~= 0
LT:0 < - a
0 ÷ - a == 0 now apply NZQuot.div_0_l.
Qed.

Lemma rem_0_l: forall a, a~=0 -> 0 rem a == 0.forall a : t, a ~= 0 -> 0 rem a == 0
Proof.forall a : t, a ~= 0 -> 0 rem a == 0
intros; rewrite rem_eq, quot_0_l; now nzsimpl.
Qed.

Lemma quot_1_r: forall a, a÷1 == a.forall a : t, a ÷ 1 == a
Proof.forall a : t, a ÷ 1 == a
intros.a:t
a ÷ 1 == a pos_or_neg a.a:t
LE:0 <= a
a ÷ 1 == a
a:t
LT:0 < - a
a ÷ 1 == a now apply NZQuot.div_1_r.a:t
LT:0 < - a
a ÷ 1 == a
apply opp_inj.a:t
LT:0 < - a
- (a ÷ 1) == - a rewrite <- quot_opp_l.a:t
LT:0 < - a
- a ÷ 1 == - a
a:t
LT:0 < - a
1 ~= 0 apply NZQuot.div_1_r; order.a:t
LT:0 < - a
1 ~= 0
intro EQ; symmetry in EQ; revert EQ; apply lt_neq, lt_0_1.
Qed.

Lemma rem_1_r: forall a, a rem 1 == 0.forall a : t, a rem 1 == 0
Proof.forall a : t, a rem 1 == 0
intros.a:t
a rem 1 == 0 rewrite rem_eq, quot_1_r; nzsimpl; auto using sub_diag.a:t
1 ~= 0
intro EQ; symmetry in EQ; revert EQ; apply lt_neq; apply lt_0_1.
Qed.

Lemma quot_1_l: forall a, 1<a -> 1÷a == 0.forall a : t, 1 < a -> 1 ÷ a == 0
Proof.forall a : t, 1 < a -> 1 ÷ a == 0 exact NZQuot.div_1_l. Qed.

Lemma rem_1_l: forall a, 1<a -> 1 rem a == 1.forall a : t, 1 < a -> 1 rem a == 1
Proof.forall a : t, 1 < a -> 1 rem a == 1 exact NZQuot.mod_1_l. Qed.

Lemma quot_mul : forall a b, b~=0 -> (a*b)÷b == a.forall a b : t, b ~= 0 -> a * b ÷ b == a
Proof.forall a b : t, b ~= 0 -> a * b ÷ b == a
intros.a, b:t
H:b ~= 0
a * b ÷ b == a pos_or_neg a; pos_or_neg b.a, b:t
H:b ~= 0
LE:0 <= a
LE0:0 <= b
a * b ÷ b == a
a, b:t
H:b ~= 0
LE:0 <= a
LT:0 < - b
a * b ÷ b == a
a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a * b ÷ b == a
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a * b ÷ b == a apply NZQuot.div_mul; order.a, b:t
H:b ~= 0
LE:0 <= a
LT:0 < - b
a * b ÷ b == a
a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a * b ÷ b == a
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a * b ÷ b == a
rewrite <- quot_opp_opp, <- mul_opp_r by order.a, b:t
H:b ~= 0
LE:0 <= a
LT:0 < - b
a * - b ÷ - b == a
a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a * b ÷ b == a
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a * b ÷ b == a apply NZQuot.div_mul; order.a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a * b ÷ b == a
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a * b ÷ b == a
rewrite <- opp_inj_wd, <- quot_opp_l, <- mul_opp_l by order.a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
- a * b ÷ b == - a
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a * b ÷ b == a
apply NZQuot.div_mul; order.a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a * b ÷ b == a
rewrite <- opp_inj_wd, <- quot_opp_r, <- mul_opp_opp by order.a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
- a * - b ÷ - b == - a
apply NZQuot.div_mul; order.
Qed.

Lemma rem_mul : forall a b, b~=0 -> (a*b) rem b == 0.forall a b : t, b ~= 0 -> (a * b) rem b == 0
Proof.forall a b : t, b ~= 0 -> (a * b) rem b == 0
intros.a, b:t
H:b ~= 0
(a * b) rem b == 0 rewrite rem_eq, quot_mul by trivial.a, b:t
H:b ~= 0
a * b - b * a == 0 rewrite mul_comm; apply sub_diag.
Qed.

Theorem quot_unique_exact a b q: b~=0 -> a == b*q -> q == a÷b.a, b, q:t
b ~= 0 -> a == b * q -> q == a ÷ b
Proof.a, b, q:t
b ~= 0 -> a == b * q -> q == a ÷ b
 intros Hb H.a, b, q:t
Hb:b ~= 0
H:a == b * q
q == a ÷ b rewrite H, mul_comm.a, b, q:t
Hb:b ~= 0
H:a == b * q
q == q * b ÷ b symmetry.a, b, q:t
Hb:b ~= 0
H:a == b * q
q * b ÷ b == q now apply quot_mul.
Qed.

The sign of a rem b is the one of a (when it's not null)

Lemma rem_nonneg : forall a b, b~=0 -> 0 <= a -> 0 <= a rem b.forall a b : t, b ~= 0 -> 0 <= a -> 0 <= a rem b
Proof.forall a b : t, b ~= 0 -> 0 <= a -> 0 <= a rem b
 intros.a, b:t
H:b ~= 0
H0:0 <= a
0 <= a rem b pos_or_neg b.a, b:t
H:b ~= 0
H0:0 <= a
LE:0 <= b
0 <= a rem b
a, b:t
H:b ~= 0
H0:0 <= a
LT:0 < - b
0 <= a rem b destruct (rem_bound_pos a b); order.a, b:t
H:b ~= 0
H0:0 <= a
LT:0 < - b
0 <= a rem b
 rewrite <- rem_opp_r; trivial.a, b:t
H:b ~= 0
H0:0 <= a
LT:0 < - b
0 <= a rem - b
 destruct (rem_bound_pos a (-b)); trivial.
Qed.

Lemma rem_nonpos : forall a b, b~=0 -> a <= 0 -> a rem b <= 0.forall a b : t, b ~= 0 -> a <= 0 -> a rem b <= 0
Proof.forall a b : t, b ~= 0 -> a <= 0 -> a rem b <= 0
 intros a b Hb Ha.a, b:t
Hb:b ~= 0
Ha:a <= 0
a rem b <= 0
 apply opp_nonneg_nonpos.a, b:t
Hb:b ~= 0
Ha:a <= 0
0 <= - (a rem b) apply opp_nonneg_nonpos in Ha.a, b:t
Hb:b ~= 0
Ha:0 <= - a
0 <= - (a rem b)
 rewrite <- rem_opp_l by trivial.a, b:t
Hb:b ~= 0
Ha:0 <= - a
0 <= - a rem b now apply rem_nonneg.
Qed.

Lemma rem_sign_mul : forall a b, b~=0 -> 0 <= (a rem b) * a.forall a b : t, b ~= 0 -> 0 <= a rem b * a
Proof.forall a b : t, b ~= 0 -> 0 <= a rem b * a
intros a b Hb.a, b:t
Hb:b ~= 0
0 <= a rem b * a destruct (le_ge_cases 0 a).a, b:t
Hb:b ~= 0
H:0 <= a
0 <= a rem b * a
a, b:t
Hb:b ~= 0
H:a <= 0
0 <= a rem b * a
 apply mul_nonneg_nonneg; trivial.a, b:t
Hb:b ~= 0
H:0 <= a
0 <= a rem b
a, b:t
Hb:b ~= 0
H:a <= 0
0 <= a rem b * a now apply rem_nonneg.a, b:t
Hb:b ~= 0
H:a <= 0
0 <= a rem b * a
 apply mul_nonpos_nonpos; trivial.a, b:t
Hb:b ~= 0
H:a <= 0
a rem b <= 0 now apply rem_nonpos.
Qed.

Lemma rem_sign_nz : forall a b, b~=0 -> a rem b ~= 0 ->
 sgn (a rem b) == sgn a.forall a b : t,
b ~= 0 -> a rem b ~= 0 -> sgn (a rem b) == sgn a
Proof.forall a b : t,
b ~= 0 -> a rem b ~= 0 -> sgn (a rem b) == sgn a
intros a b Hb H.a, b:t
Hb:b ~= 0
H:a rem b ~= 0
sgn (a rem b) == sgn a destruct (lt_trichotomy 0 a) as [LT|[EQ|LT]].a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:0 < a
sgn (a rem b) == sgn a
a, b:t
Hb:b ~= 0
H:a rem b ~= 0
EQ:0 == a
sgn (a rem b) == sgn a
a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:a < 0
sgn (a rem b) == sgn a
rewrite 2 sgn_pos; try easy.a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:0 < a
0 < a rem b
a, b:t
Hb:b ~= 0
H:a rem b ~= 0
EQ:0 == a
sgn (a rem b) == sgn a
a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:a < 0
sgn (a rem b) == sgn a
 generalize (rem_nonneg a b Hb (lt_le_incl _ _ LT)).a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:0 < a
0 <= a rem b -> 0 < a rem b
a, b:t
Hb:b ~= 0
H:a rem b ~= 0
EQ:0 == a
sgn (a rem b) == sgn a
a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:a < 0
sgn (a rem b) == sgn a order.a, b:t
Hb:b ~= 0
H:a rem b ~= 0
EQ:0 == a
sgn (a rem b) == sgn a
a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:a < 0
sgn (a rem b) == sgn a
now rewrite <- EQ, rem_0_l, sgn_0.a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:a < 0
sgn (a rem b) == sgn a
rewrite 2 sgn_neg; try easy.a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:a < 0
a rem b < 0
 generalize (rem_nonpos a b Hb (lt_le_incl _ _ LT)).a, b:t
Hb:b ~= 0
H:a rem b ~= 0
LT:a < 0
a rem b <= 0 -> a rem b < 0 order.
Qed.

Lemma rem_sign : forall a b, a~=0 -> b~=0 -> sgn (a rem b) ~= -sgn a.forall a b : t,
a ~= 0 -> b ~= 0 -> sgn (a rem b) ~= - sgn a
Proof.forall a b : t,
a ~= 0 -> b ~= 0 -> sgn (a rem b) ~= - sgn a
intros a b Ha Hb H.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
False
destruct (eq_decidable (a rem b) 0) as [EQ|NEQ].a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
EQ:a rem b == 0
False
a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
False
apply Ha, sgn_null_iff, opp_inj.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
EQ:a rem b == 0
- sgn a == - 0
a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
False now rewrite <- H, opp_0, EQ, sgn_0.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
False
apply Ha, sgn_null_iff.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
sgn a == 0 apply eq_mul_0_l with 2; try order'.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
sgn a * 2 == 0 nzsimpl'.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
sgn a + sgn a == 0
apply add_move_0_l.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
sgn a == - sgn a rewrite <- H.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
sgn a == sgn (a rem b) symmetry.a, b:t
Ha:a ~= 0
Hb:b ~= 0
H:sgn (a rem b) == - sgn a
NEQ:a rem b ~= 0
sgn (a rem b) == sgn a now apply rem_sign_nz.
Qed.

Operations and absolute value

Lemma rem_abs_l : forall a b, b ~= 0 -> (abs a) rem b == abs (a rem b).forall a b : t, b ~= 0 -> abs a rem b == abs (a rem b)
Proof.forall a b : t, b ~= 0 -> abs a rem b == abs (a rem b)
intros a b Hb.a, b:t
Hb:b ~= 0
abs a rem b == abs (a rem b) destruct (le_ge_cases 0 a) as [LE|LE].a, b:t
Hb:b ~= 0
LE:0 <= a
abs a rem b == abs (a rem b)
a, b:t
Hb:b ~= 0
LE:a <= 0
abs a rem b == abs (a rem b)
rewrite 2 abs_eq; try easy.a, b:t
Hb:b ~= 0
LE:0 <= a
0 <= a rem b
a, b:t
Hb:b ~= 0
LE:a <= 0
abs a rem b == abs (a rem b) now apply rem_nonneg.a, b:t
Hb:b ~= 0
LE:a <= 0
abs a rem b == abs (a rem b)
rewrite 2 abs_neq, rem_opp_l; try easy.a, b:t
Hb:b ~= 0
LE:a <= 0
a rem b <= 0 now apply rem_nonpos.
Qed.

Lemma rem_abs_r : forall a b, b ~= 0 -> a rem (abs b) == a rem b.forall a b : t, b ~= 0 -> a rem abs b == a rem b
Proof.forall a b : t, b ~= 0 -> a rem abs b == a rem b
intros a b Hb.a, b:t
Hb:b ~= 0
a rem abs b == a rem b destruct (le_ge_cases 0 b).a, b:t
Hb:b ~= 0
H:0 <= b
a rem abs b == a rem b
a, b:t
Hb:b ~= 0
H:b <= 0
a rem abs b == a rem b
now rewrite abs_eq.a, b:t
Hb:b ~= 0
H:b <= 0
a rem abs b == a rem b now rewrite abs_neq, ?rem_opp_r.
Qed.

Lemma rem_abs : forall a b,  b ~= 0 -> (abs a) rem (abs b) == abs (a rem b).forall a b : t,
b ~= 0 -> abs a rem abs b == abs (a rem b)
Proof.forall a b : t,
b ~= 0 -> abs a rem abs b == abs (a rem b)
intros.a, b:t
H:b ~= 0
abs a rem abs b == abs (a rem b) now rewrite rem_abs_r, rem_abs_l.
Qed.

Lemma quot_abs_l : forall a b, b ~= 0 -> (abs a)÷b == (sgn a)*(a÷b).forall a b : t, b ~= 0 -> abs a ÷ b == sgn a * (a ÷ b)
Proof.forall a b : t, b ~= 0 -> abs a ÷ b == sgn a * (a ÷ b)
intros a b Hb.a, b:t
Hb:b ~= 0
abs a ÷ b == sgn a * (a ÷ b) destruct (lt_trichotomy 0 a) as [LT|[EQ|LT]].a, b:t
Hb:b ~= 0
LT:0 < a
abs a ÷ b == sgn a * (a ÷ b)
a, b:t
Hb:b ~= 0
EQ:0 == a
abs a ÷ b == sgn a * (a ÷ b)
a, b:t
Hb:b ~= 0
LT:a < 0
abs a ÷ b == sgn a * (a ÷ b)
rewrite abs_eq, sgn_pos by order.a, b:t
Hb:b ~= 0
LT:0 < a
a ÷ b == 1 * (a ÷ b)
a, b:t
Hb:b ~= 0
EQ:0 == a
abs a ÷ b == sgn a * (a ÷ b)
a, b:t
Hb:b ~= 0
LT:a < 0
abs a ÷ b == sgn a * (a ÷ b) now nzsimpl.a, b:t
Hb:b ~= 0
EQ:0 == a
abs a ÷ b == sgn a * (a ÷ b)
a, b:t
Hb:b ~= 0
LT:a < 0
abs a ÷ b == sgn a * (a ÷ b)
rewrite <- EQ, abs_0, quot_0_l; trivial.a, b:t
Hb:b ~= 0
EQ:0 == a
0 == sgn 0 * 0
a, b:t
Hb:b ~= 0
LT:a < 0
abs a ÷ b == sgn a * (a ÷ b) now nzsimpl.a, b:t
Hb:b ~= 0
LT:a < 0
abs a ÷ b == sgn a * (a ÷ b)
rewrite abs_neq, quot_opp_l, sgn_neg by order.a, b:t
Hb:b ~= 0
LT:a < 0
- (a ÷ b) == -1 * (a ÷ b)
 rewrite mul_opp_l.a, b:t
Hb:b ~= 0
LT:a < 0
- (a ÷ b) == - (1 * (a ÷ b)) now nzsimpl.
Qed.

Lemma quot_abs_r : forall a b, b ~= 0 -> a÷(abs b) == (sgn b)*(a÷b).forall a b : t, b ~= 0 -> a ÷ abs b == sgn b * (a ÷ b)
Proof.forall a b : t, b ~= 0 -> a ÷ abs b == sgn b * (a ÷ b)
intros a b Hb.a, b:t
Hb:b ~= 0
a ÷ abs b == sgn b * (a ÷ b) destruct (lt_trichotomy 0 b) as [LT|[EQ|LT]].a, b:t
Hb:b ~= 0
LT:0 < b
a ÷ abs b == sgn b * (a ÷ b)
a, b:t
Hb:b ~= 0
EQ:0 == b
a ÷ abs b == sgn b * (a ÷ b)
a, b:t
Hb:b ~= 0
LT:b < 0
a ÷ abs b == sgn b * (a ÷ b)
rewrite abs_eq, sgn_pos by order.a, b:t
Hb:b ~= 0
LT:0 < b
a ÷ b == 1 * (a ÷ b)
a, b:t
Hb:b ~= 0
EQ:0 == b
a ÷ abs b == sgn b * (a ÷ b)
a, b:t
Hb:b ~= 0
LT:b < 0
a ÷ abs b == sgn b * (a ÷ b) now nzsimpl.a, b:t
Hb:b ~= 0
EQ:0 == b
a ÷ abs b == sgn b * (a ÷ b)
a, b:t
Hb:b ~= 0
LT:b < 0
a ÷ abs b == sgn b * (a ÷ b)
order.a, b:t
Hb:b ~= 0
LT:b < 0
a ÷ abs b == sgn b * (a ÷ b)
rewrite abs_neq, quot_opp_r, sgn_neg by order.a, b:t
Hb:b ~= 0
LT:b < 0
- (a ÷ b) == -1 * (a ÷ b)
 rewrite mul_opp_l.a, b:t
Hb:b ~= 0
LT:b < 0
- (a ÷ b) == - (1 * (a ÷ b)) now nzsimpl.
Qed.

Lemma quot_abs : forall a b, b ~= 0 -> (abs a)÷(abs b) == abs (a÷b).forall a b : t, b ~= 0 -> abs a ÷ abs b == abs (a ÷ b)
Proof.forall a b : t, b ~= 0 -> abs a ÷ abs b == abs (a ÷ b)
intros a b Hb.a, b:t
Hb:b ~= 0
abs a ÷ abs b == abs (a ÷ b)
pos_or_neg a; [rewrite (abs_eq a)|rewrite (abs_neq a)];
 try apply opp_nonneg_nonpos; try order.a, b:t
Hb:b ~= 0
LE:0 <= a
a ÷ abs b == abs (a ÷ b)
a, b:t
Hb:b ~= 0
LT:0 < - a
- a ÷ abs b == abs (a ÷ b)
pos_or_neg b; [rewrite (abs_eq b)|rewrite (abs_neq b)];
 try apply opp_nonneg_nonpos; try order.a, b:t
Hb:b ~= 0
LE:0 <= a
LE0:0 <= b
a ÷ b == abs (a ÷ b)
a, b:t
Hb:b ~= 0
LE:0 <= a
LT:0 < - b
a ÷ - b == abs (a ÷ b)
a, b:t
Hb:b ~= 0
LT:0 < - a
- a ÷ abs b == abs (a ÷ b)
rewrite abs_eq; try easy.a, b:t
Hb:b ~= 0
LE:0 <= a
LE0:0 <= b
0 <= a ÷ b
a, b:t
Hb:b ~= 0
LE:0 <= a
LT:0 < - b
a ÷ - b == abs (a ÷ b)
a, b:t
Hb:b ~= 0
LT:0 < - a
- a ÷ abs b == abs (a ÷ b) apply NZQuot.div_pos; order.a, b:t
Hb:b ~= 0
LE:0 <= a
LT:0 < - b
a ÷ - b == abs (a ÷ b)
a, b:t
Hb:b ~= 0
LT:0 < - a
- a ÷ abs b == abs (a ÷ b)
rewrite <- abs_opp, <- quot_opp_r, abs_eq; try easy.a, b:t
Hb:b ~= 0
LE:0 <= a
LT:0 < - b
0 <= a ÷ - b
a, b:t
Hb:b ~= 0
LT:0 < - a
- a ÷ abs b == abs (a ÷ b)
 apply NZQuot.div_pos; order.a, b:t
Hb:b ~= 0
LT:0 < - a
- a ÷ abs b == abs (a ÷ b)
pos_or_neg b; [rewrite (abs_eq b)|rewrite (abs_neq b)];
 try apply opp_nonneg_nonpos; try order.a, b:t
Hb:b ~= 0
LT:0 < - a
LE:0 <= b
- a ÷ b == abs (a ÷ b)
a, b:t
Hb:b ~= 0
LT:0 < - a
LT0:0 < - b
- a ÷ - b == abs (a ÷ b)
rewrite <- (abs_opp (_÷_)), <- quot_opp_l, abs_eq; try easy.a, b:t
Hb:b ~= 0
LT:0 < - a
LE:0 <= b
0 <= - a ÷ b
a, b:t
Hb:b ~= 0
LT:0 < - a
LT0:0 < - b
- a ÷ - b == abs (a ÷ b)
 apply NZQuot.div_pos; order.a, b:t
Hb:b ~= 0
LT:0 < - a
LT0:0 < - b
- a ÷ - b == abs (a ÷ b)
rewrite <- (quot_opp_opp a b), abs_eq; try easy.a, b:t
Hb:b ~= 0
LT:0 < - a
LT0:0 < - b
0 <= - a ÷ - b
 apply NZQuot.div_pos; order.
Qed.

We have a general bound for absolute values

Lemma rem_bound_abs :
 forall a b, b~=0 -> abs (a rem b) < abs b.forall a b : t, b ~= 0 -> abs (a rem b) < abs b
Proof.forall a b : t, b ~= 0 -> abs (a rem b) < abs b
intros.a, b:t
H:b ~= 0
abs (a rem b) < abs b rewrite <- rem_abs; trivial.a, b:t
H:b ~= 0
abs a rem abs b < abs b
apply rem_bound_pos.a, b:t
H:b ~= 0
0 <= abs a
a, b:t
H:b ~= 0
0 < abs b apply abs_nonneg.a, b:t
H:b ~= 0
0 < abs b now apply abs_pos.
Qed.

Order results about rem and quot

A modulo cannot grow beyond its starting point.

Theorem rem_le: forall a b, 0<=a -> 0<b -> a rem b <= a.forall a b : t, 0 <= a -> 0 < b -> a rem b <= a
Proof.forall a b : t, 0 <= a -> 0 < b -> a rem b <= a exact NZQuot.mod_le. Qed.

Theorem quot_pos : forall a b, 0<=a -> 0<b -> 0<= a÷b.forall a b : t, 0 <= a -> 0 < b -> 0 <= a ÷ b
Proof.forall a b : t, 0 <= a -> 0 < b -> 0 <= a ÷ b exact NZQuot.div_pos. Qed.

Lemma quot_str_pos : forall a b, 0<b<=a -> 0 < a÷b.forall a b : t, 0 < b <= a -> 0 < a ÷ b
Proof.forall a b : t, 0 < b <= a -> 0 < a ÷ b exact NZQuot.div_str_pos. Qed.

Lemma quot_small_iff : forall a b, b~=0 -> (a÷b==0 <-> abs a < abs b).forall a b : t, b ~= 0 -> a ÷ b == 0 <-> abs a < abs b
Proof.forall a b : t, b ~= 0 -> a ÷ b == 0 <-> abs a < abs b
intros.a, b:t
H:b ~= 0
a ÷ b == 0 <-> abs a < abs b pos_or_neg a; pos_or_neg b.a, b:t
H:b ~= 0
LE:0 <= a
LE0:0 <= b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LE:0 <= a
LT:0 < - b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a ÷ b == 0 <-> abs a < abs b
rewrite NZQuot.div_small_iff; try order.a, b:t
H:b ~= 0
LE:0 <= a
LE0:0 <= b
a < b <-> abs a < abs b
a, b:t
H:b ~= 0
LE:0 <= a
LT:0 < - b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a ÷ b == 0 <-> abs a < abs b rewrite 2 abs_eq; intuition; order.a, b:t
H:b ~= 0
LE:0 <= a
LT:0 < - b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a ÷ b == 0 <-> abs a < abs b
rewrite <- opp_inj_wd, opp_0, <- quot_opp_r, NZQuot.div_small_iff by order.a, b:t
H:b ~= 0
LE:0 <= a
LT:0 < - b
a < - b <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a ÷ b == 0 <-> abs a < abs b
 rewrite (abs_eq a), (abs_neq' b); intuition; order.a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
a ÷ b == 0 <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a ÷ b == 0 <-> abs a < abs b
rewrite <- opp_inj_wd, opp_0, <- quot_opp_l, NZQuot.div_small_iff by order.a, b:t
H:b ~= 0
LT:0 < - a
LE:0 <= b
- a < b <-> abs a < abs b
a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a ÷ b == 0 <-> abs a < abs b
 rewrite (abs_neq' a), (abs_eq b); intuition; order.a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
a ÷ b == 0 <-> abs a < abs b
rewrite <- quot_opp_opp, NZQuot.div_small_iff by order.a, b:t
H:b ~= 0
LT:0 < - a
LT0:0 < - b
- a < - b <-> abs a < abs b
 rewrite (abs_neq' a), (abs_neq' b); intuition; order.
Qed.

Lemma rem_small_iff : forall a b, b~=0 -> (a rem b == a <-> abs a < abs b).forall a b : t,
b ~= 0 -> a rem b == a <-> abs a < abs b
Proof.forall a b : t,
b ~= 0 -> a rem b == a <-> abs a < abs b
intros.a, b:t
H:b ~= 0
a rem b == a <-> abs a < abs b rewrite rem_eq, <- quot_small_iff by order.a, b:t
H:b ~= 0
a - b * (a ÷ b) == a <-> a ÷ b == 0
rewrite sub_move_r, <- (add_0_r a) at 1.a, b:t
H:b ~= 0
a + 0 == a + b * (a ÷ b) <-> a ÷ b == 0 rewrite add_cancel_l.a, b:t
H:b ~= 0
0 == b * (a ÷ b) <-> a ÷ b == 0
rewrite eq_sym_iff, eq_mul_0.a, b:t
H:b ~= 0
b == 0 \/ a ÷ b == 0 <-> a ÷ b == 0 tauto.
Qed.

As soon as the divisor is strictly greater than 1, the division is strictly decreasing.

Lemma quot_lt : forall a b, 0<a -> 1<b -> a÷b < a.forall a b : t, 0 < a -> 1 < b -> a ÷ b < a
Proof.forall a b : t, 0 < a -> 1 < b -> a ÷ b < a exact NZQuot.div_lt. Qed.

le is compatible with a positive division.

Lemma quot_le_mono : forall a b c, 0<c -> a<=b -> a÷c <= b÷c.forall a b c : t, 0 < c -> a <= b -> a ÷ c <= b ÷ c
Proof.forall a b c : t, 0 < c -> a <= b -> a ÷ c <= b ÷ c
intros.a, b, c:t
H:0 < c
H0:a <= b
a ÷ c <= b ÷ c pos_or_neg a.a, b, c:t
H:0 < c
H0:a <= b
LE:0 <= a
a ÷ c <= b ÷ c
a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
a ÷ c <= b ÷ c apply NZQuot.div_le_mono; auto.a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
a ÷ c <= b ÷ c
pos_or_neg b.a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LE:0 <= b
a ÷ c <= b ÷ c
a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LT0:0 < - b
a ÷ c <= b ÷ c apply le_trans with 0.a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LE:0 <= b
a ÷ c <= 0
a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LE:0 <= b
0 <= b ÷ c
a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LT0:0 < - b
a ÷ c <= b ÷ c
 rewrite <- opp_nonneg_nonpos, <- quot_opp_l by order.a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LE:0 <= b
0 <= - a ÷ c
a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LE:0 <= b
0 <= b ÷ c
a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LT0:0 < - b
a ÷ c <= b ÷ c
 apply quot_pos; order.a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LE:0 <= b
0 <= b ÷ c
a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LT0:0 < - b
a ÷ c <= b ÷ c
 apply quot_pos; order.a, b, c:t
H:0 < c
H0:a <= b
LT:0 < - a
LT0:0 < - b
a ÷ c <= b ÷ c
rewrite opp_le_mono in *.a, b, c:t
H:0 < c
H0:- b <= - a
LT:0 < - a
LT0:0 < - b
- (b ÷ c) <= - (a ÷ c) rewrite <- 2 quot_opp_l by order.a, b, c:t
H:0 < c
H0:- b <= - a
LT:0 < - a
LT0:0 < - b
- b ÷ c <= - a ÷ c
 apply NZQuot.div_le_mono; intuition; order.
Qed.

With this choice of division, rounding of quot is always done toward zero:

Lemma mul_quot_le : forall a b, 0<=a -> b~=0 -> 0 <= b*(a÷b) <= a.forall a b : t,
0 <= a -> b ~= 0 -> 0 <= b * (a ÷ b) <= a
Proof.forall a b : t,
0 <= a -> b ~= 0 -> 0 <= b * (a ÷ b) <= a
intros.a, b:t
H:0 <= a
H0:b ~= 0
0 <= b * (a ÷ b) <= a pos_or_neg b.a, b:t
H:0 <= a
H0:b ~= 0
LE:0 <= b
0 <= b * (a ÷ b) <= a
a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
0 <= b * (a ÷ b) <= a
split.a, b:t
H:0 <= a
H0:b ~= 0
LE:0 <= b
0 <= b * (a ÷ b)
a, b:t
H:0 <= a
H0:b ~= 0
LE:0 <= b
b * (a ÷ b) <= a
a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
0 <= b * (a ÷ b) <= a
apply mul_nonneg_nonneg; [|apply quot_pos]; order.a, b:t
H:0 <= a
H0:b ~= 0
LE:0 <= b
b * (a ÷ b) <= a
a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
0 <= b * (a ÷ b) <= a
apply NZQuot.mul_div_le; order.a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
0 <= b * (a ÷ b) <= a
rewrite <- mul_opp_opp, <- quot_opp_r by order.a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
0 <= - b * (a ÷ - b) <= a
split.a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
0 <= - b * (a ÷ - b)
a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
- b * (a ÷ - b) <= a
apply mul_nonneg_nonneg; [|apply quot_pos]; order.a, b:t
H:0 <= a
H0:b ~= 0
LT:0 < - b
- b * (a ÷ - b) <= a
apply NZQuot.mul_div_le; order.
Qed.

Lemma mul_quot_ge : forall a b, a<=0 -> b~=0 -> a <= b*(a÷b) <= 0.forall a b : t,
a <= 0 -> b ~= 0 -> a <= b * (a ÷ b) <= 0
Proof.forall a b : t,
a <= 0 -> b ~= 0 -> a <= b * (a ÷ b) <= 0
intros.a, b:t
H:a <= 0
H0:b ~= 0
a <= b * (a ÷ b) <= 0
rewrite <- opp_nonneg_nonpos, opp_le_mono, <-mul_opp_r, <-quot_opp_l by order.a, b:t
H:a <= 0
H0:b ~= 0
b * (- a ÷ b) <= - a /\ 0 <= b * (- a ÷ b)
rewrite <- opp_nonneg_nonpos in *.a, b:t
H:0 <= - a
H0:b ~= 0
b * (- a ÷ b) <= - a /\ 0 <= b * (- a ÷ b)
destruct (mul_quot_le (-a) b); tauto.
Qed.

For positive numbers, considering S (a÷b) leads to an upper bound for a

Lemma mul_succ_quot_gt: forall a b, 0<=a -> 0<b -> a < b*(S (a÷b)).forall a b : t, 0 <= a -> 0 < b -> a < b * S (a ÷ b)
Proof.forall a b : t, 0 <= a -> 0 < b -> a < b * S (a ÷ b) exact NZQuot.mul_succ_div_gt. Qed.

Relations between usual operations and rem and quot

Unlike with other division conventions, some results here aren't always valid, and need to be restricted. For instance (a+b×c) rem c ≠ a rem c for a=9,b=-5,c=2

Lemma rem_add : forall a b c, c~=0 -> 0 <= (a+b*c)*a ->
 (a + b * c) rem c == a rem c.forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c
Proof.forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c
assert (forall a b c, c~=0 -> 0<=a -> 0<=a+b*c -> (a+b*c) rem c == a rem c).forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
H:forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c
 intros.a, b, c:t
H:c ~= 0
H0:0 <= a
H1:0 <= a + b * c
(a + b * c) rem c == a rem c
H:forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c pos_or_neg c.a, b, c:t
H:c ~= 0
H0:0 <= a
H1:0 <= a + b * c
LE:0 <= c
(a + b * c) rem c == a rem c
a, b, c:t
H:c ~= 0
H0:0 <= a
H1:0 <= a + b * c
LT:0 < - c
(a + b * c) rem c == a rem c
H:forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c apply NZQuot.mod_add; order.a, b, c:t
H:c ~= 0
H0:0 <= a
H1:0 <= a + b * c
LT:0 < - c
(a + b * c) rem c == a rem c
H:forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c
 rewrite <- (rem_opp_r a), <- (rem_opp_r (a+b*c)) by order.a, b, c:t
H:c ~= 0
H0:0 <= a
H1:0 <= a + b * c
LT:0 < - c
(a + b * c) rem - c == a rem - c
H:forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c
 rewrite <- mul_opp_opp in *.a, b, c:t
H:c ~= 0
H0:0 <= a
H1:0 <= a + - b * - c
LT:0 < - c
(a + - b * - c) rem - c == a rem - c
H:forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c
 apply NZQuot.mod_add; order.H:forall a b c : t,
c ~= 0 ->
0 <= a ->
0 <= a + b * c -> (a + b * c) rem c == a rem c
forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) rem c == a rem c
intros a b c Hc Habc.H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
(a + b * c) rem c == a rem c
destruct (le_0_mul _ _ Habc) as [(Habc',Ha)|(Habc',Ha)].H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
Habc':0 <= a + b * c
Ha:0 <= a
(a + b * c) rem c == a rem c
H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
Habc':a + b * c <= 0
Ha:a <= 0
(a + b * c) rem c == a rem c auto.H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
Habc':a + b * c <= 0
Ha:a <= 0
(a + b * c) rem c == a rem c
apply opp_inj.H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
Habc':a + b * c <= 0
Ha:a <= 0
- ((a + b * c) rem c) == - (a rem c) revert Ha Habc'.H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
a <= 0 ->
a + b * c <= 0 -> - ((a + b * c) rem c) == - (a rem c)
rewrite <- 2 opp_nonneg_nonpos.H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
0 <= - a ->
0 <= - (a + b * c) ->
- ((a + b * c) rem c) == - (a rem c)
rewrite <- 2 rem_opp_l, opp_add_distr, <- mul_opp_l by order.H:forall a0 b0 c0 : t,
c0 ~= 0 ->
0 <= a0 ->
0 <= a0 + b0 * c0 ->
(a0 + b0 * c0) rem c0 == a0 rem c0
a, b, c:t
Hc:c ~= 0
Habc:0 <= (a + b * c) * a
0 <= - a ->
0 <= - a + - b * c ->
(- a + - b * c) rem c == - a rem c auto.
Qed.

Lemma quot_add : forall a b c, c~=0 -> 0 <= (a+b*c)*a ->
 (a + b * c) ÷ c == a ÷ c + b.forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) ÷ c == a ÷ c + b
Proof.forall a b c : t,
c ~= 0 ->
0 <= (a + b * c) * a -> (a + b * c) ÷ c == a ÷ c + b
intros.a, b, c:t
H:c ~= 0
H0:0 <= (a + b * c) * a
(a + b * c) ÷ c == a ÷ c + b
rewrite <- (mul_cancel_l _ _ c) by trivial.a, b, c:t
H:c ~= 0
H0:0 <= (a + b * c) * a
c * ((a + b * c) ÷ c) == c * (a ÷ c + b)
rewrite <- (add_cancel_r _ _ ((a+b*c) rem c)).a, b, c:t
H:c ~= 0
H0:0 <= (a + b * c) * a
c * ((a + b * c) ÷ c) + (a + b * c) rem c ==
c * (a ÷ c + b) + (a + b * c) rem c
rewrite <- quot_rem, rem_add by trivial.a, b, c:t
H:c ~= 0
H0:0 <= (a + b * c) * a
a + b * c == c * (a ÷ c + b) + a rem c
now rewrite mul_add_distr_l, add_shuffle0, <-quot_rem, mul_comm.
Qed.

Lemma quot_add_l: forall a b c, b~=0 -> 0 <= (a*b+c)*c ->
 (a * b + c) ÷ b == a + c ÷ b.forall a b c : t,
b ~= 0 ->
0 <= (a * b + c) * c -> (a * b + c) ÷ b == a + c ÷ b
Proof.forall a b c : t,
b ~= 0 ->
0 <= (a * b + c) * c -> (a * b + c) ÷ b == a + c ÷ b
 intros a b c.a, b, c:t
b ~= 0 ->
0 <= (a * b + c) * c -> (a * b + c) ÷ b == a + c ÷ b rewrite add_comm, (add_comm a).a, b, c:t
b ~= 0 ->
0 <= (c + a * b) * c -> (c + a * b) ÷ b == c ÷ b + a now apply quot_add.
Qed.

Cancellations.

Lemma quot_mul_cancel_r : forall a b c, b~=0 -> c~=0 ->
 (a*c)÷(b*c) == a÷b.forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Proof.forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
assert (Aux1 : forall a b c, 0<=a -> 0<b -> c~=0 -> (a*c)÷(b*c) == a÷b).forall a b c : t,
0 <= a -> 0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
 intros.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b pos_or_neg c.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LE:0 <= c
a * c ÷ (b * c) == a ÷ b
a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b apply NZQuot.div_mul_cancel_r; order.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
 rewrite <- quot_opp_opp, <- 2 mul_opp_r.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
a * - c ÷ (b * - c) == a ÷ b
a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b apply NZQuot.div_mul_cancel_r; order.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
 rewrite <- neq_mul_0; intuition order.Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
assert (Aux2 : forall a b c, 0<=a -> b~=0 -> c~=0 -> (a*c)÷(b*c) == a÷b).Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
0 <= a -> b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
 intros.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b pos_or_neg b.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LE:0 <= b
a * c ÷ (b * c) == a ÷ b
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b apply Aux1; order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
a * c ÷ (b * c) == a ÷ b
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
 apply opp_inj.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
- (a * c ÷ (b * c)) == - (a ÷ b)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b rewrite <- 2 quot_opp_r, <- mul_opp_l; try order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
a * c ÷ (- b * c) == a ÷ - b
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b apply Aux1; order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
 rewrite <- neq_mul_0; intuition order.Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
forall a b c : t,
b ~= 0 -> c ~= 0 -> a * c ÷ (b * c) == a ÷ b
intros.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
a * c ÷ (b * c) == a ÷ b pos_or_neg a.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
LE:0 <= a
a * c ÷ (b * c) == a ÷ b
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
a * c ÷ (b * c) == a ÷ b apply Aux2; order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
a * c ÷ (b * c) == a ÷ b
apply opp_inj.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
- (a * c ÷ (b * c)) == - (a ÷ b) rewrite <- 2 quot_opp_l, <- mul_opp_l; try order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
- a * c ÷ (b * c) == - a ÷ b
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
b * c ~= 0 apply Aux2; order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 * c0 ÷ (b0 * c0) == a0 ÷ b0
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
b * c ~= 0
rewrite <- neq_mul_0; intuition order.
Qed.

Lemma quot_mul_cancel_l : forall a b c, b~=0 -> c~=0 ->
 (c*a)÷(c*b) == a÷b.forall a b c : t,
b ~= 0 -> c ~= 0 -> c * a ÷ (c * b) == a ÷ b
Proof.forall a b c : t,
b ~= 0 -> c ~= 0 -> c * a ÷ (c * b) == a ÷ b
intros.a, b, c:t
H:b ~= 0
H0:c ~= 0
c * a ÷ (c * b) == a ÷ b rewrite !(mul_comm c); now apply quot_mul_cancel_r.
Qed.

Lemma mul_rem_distr_r: forall a b c, b~=0 -> c~=0 ->
  (a*c) rem (b*c) == (a rem b) * c.forall a b c : t,
b ~= 0 -> c ~= 0 -> (a * c) rem (b * c) == a rem b * c
Proof.forall a b c : t,
b ~= 0 -> c ~= 0 -> (a * c) rem (b * c) == a rem b * c
intros.a, b, c:t
H:b ~= 0
H0:c ~= 0
(a * c) rem (b * c) == a rem b * c
assert (b*c ~= 0) by (rewrite <- neq_mul_0; tauto).a, b, c:t
H:b ~= 0
H0:c ~= 0
H1:b * c ~= 0
(a * c) rem (b * c) == a rem b * c
rewrite ! rem_eq by trivial.a, b, c:t
H:b ~= 0
H0:c ~= 0
H1:b * c ~= 0
a * c - b * c * (a * c ÷ (b * c)) ==
(a - b * (a ÷ b)) * c
rewrite quot_mul_cancel_r by order.a, b, c:t
H:b ~= 0
H0:c ~= 0
H1:b * c ~= 0
a * c - b * c * (a ÷ b) == (a - b * (a ÷ b)) * c
now rewrite mul_sub_distr_r, <- !mul_assoc, (mul_comm (a÷b) c).
Qed.

Lemma mul_rem_distr_l: forall a b c, b~=0 -> c~=0 ->
  (c*a) rem (c*b) == c * (a rem b).forall a b c : t,
b ~= 0 ->
c ~= 0 -> (c * a) rem (c * b) == c * (a rem b)
Proof.forall a b c : t,
b ~= 0 ->
c ~= 0 -> (c * a) rem (c * b) == c * (a rem b)
intros; rewrite !(mul_comm c); now apply mul_rem_distr_r.
Qed.

Operations modulo.

Theorem rem_rem: forall a n, n~=0 ->
 (a rem n) rem n == a rem n.forall a n : t, n ~= 0 -> (a rem n) rem n == a rem n
Proof.forall a n : t, n ~= 0 -> (a rem n) rem n == a rem n
intros.a, n:t
H:n ~= 0
(a rem n) rem n == a rem n pos_or_neg a; pos_or_neg n.a, n:t
H:n ~= 0
LE:0 <= a
LE0:0 <= n
(a rem n) rem n == a rem n
a, n:t
H:n ~= 0
LE:0 <= a
LT:0 < - n
(a rem n) rem n == a rem n
a, n:t
H:n ~= 0
LT:0 < - a
LE:0 <= n
(a rem n) rem n == a rem n
a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(a rem n) rem n == a rem n apply NZQuot.mod_mod; order.a, n:t
H:n ~= 0
LE:0 <= a
LT:0 < - n
(a rem n) rem n == a rem n
a, n:t
H:n ~= 0
LT:0 < - a
LE:0 <= n
(a rem n) rem n == a rem n
a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(a rem n) rem n == a rem n
rewrite <- ! (rem_opp_r _ n) by trivial.a, n:t
H:n ~= 0
LE:0 <= a
LT:0 < - n
(a rem - n) rem - n == a rem - n
a, n:t
H:n ~= 0
LT:0 < - a
LE:0 <= n
(a rem n) rem n == a rem n
a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(a rem n) rem n == a rem n apply NZQuot.mod_mod; order.a, n:t
H:n ~= 0
LT:0 < - a
LE:0 <= n
(a rem n) rem n == a rem n
a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(a rem n) rem n == a rem n
apply opp_inj.a, n:t
H:n ~= 0
LT:0 < - a
LE:0 <= n
- ((a rem n) rem n) == - (a rem n)
a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(a rem n) rem n == a rem n rewrite <- !rem_opp_l by order.a, n:t
H:n ~= 0
LT:0 < - a
LE:0 <= n
(- a rem n) rem n == - a rem n
a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(a rem n) rem n == a rem n apply NZQuot.mod_mod; order.a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(a rem n) rem n == a rem n
apply opp_inj.a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
- ((a rem n) rem n) == - (a rem n) rewrite <- !rem_opp_opp by order.a, n:t
H:n ~= 0
LT:0 < - a
LT0:0 < - n
(- a rem - n) rem - n == - a rem - n apply NZQuot.mod_mod; order.
Qed.

Lemma mul_rem_idemp_l : forall a b n, n~=0 ->
 ((a rem n)*b) rem n == (a*b) rem n.forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Proof.forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
assert (Aux1 : forall a b n, 0<=a -> 0<=b -> n~=0 ->
         ((a rem n)*b) rem n == (a*b) rem n).forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
 intros.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n pos_or_neg n.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LE:0 <= n
(a rem n * b) rem n == (a * b) rem n
a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LT:0 < - n
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n apply NZQuot.mul_mod_idemp_l; order.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LT:0 < - n
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
 rewrite <- ! (rem_opp_r _ n) by order.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LT:0 < - n
(a rem - n * b) rem - n == (a * b) rem - n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n apply NZQuot.mul_mod_idemp_l; order.Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
assert (Aux2 : forall a b n, 0<=a -> n~=0 ->
         ((a rem n)*b) rem n == (a*b) rem n).Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux2:forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
 intros.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
H:0 <= a
H0:n ~= 0
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux2:forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n pos_or_neg b.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
H:0 <= a
H0:n ~= 0
LE:0 <= b
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
H:0 <= a
H0:n ~= 0
LT:0 < - b
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux2:forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n now apply Aux1.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
H:0 <= a
H0:n ~= 0
LT:0 < - b
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux2:forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
 apply opp_inj.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
H:0 <= a
H0:n ~= 0
LT:0 < - b
- ((a rem n * b) rem n) == - ((a * b) rem n)
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux2:forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n rewrite <-2 rem_opp_l, <-2 mul_opp_r by order.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
H:0 <= a
H0:n ~= 0
LT:0 < - b
(a rem n * - b) rem n == (a * - b) rem n
Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux2:forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
  apply Aux1; order.Aux1:forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
Aux2:forall a b n : t,
0 <= a ->
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
forall a b n : t,
n ~= 0 -> (a rem n * b) rem n == (a * b) rem n
intros a b n Hn.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
Aux2:forall a0 b0 n0 : t,
0 <= a0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
Hn:n ~= 0
(a rem n * b) rem n == (a * b) rem n pos_or_neg a.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
Aux2:forall a0 b0 n0 : t,
0 <= a0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
Hn:n ~= 0
LE:0 <= a
(a rem n * b) rem n == (a * b) rem n
Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
Aux2:forall a0 b0 n0 : t,
0 <= a0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
Hn:n ~= 0
LT:0 < - a
(a rem n * b) rem n == (a * b) rem n now apply Aux2.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
Aux2:forall a0 b0 n0 : t,
0 <= a0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
Hn:n ~= 0
LT:0 < - a
(a rem n * b) rem n == (a * b) rem n
apply opp_inj.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
Aux2:forall a0 b0 n0 : t,
0 <= a0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
Hn:n ~= 0
LT:0 < - a
- ((a rem n * b) rem n) == - ((a * b) rem n) rewrite <-2 rem_opp_l, <-2 mul_opp_l, <-rem_opp_l by order.Aux1:forall a0 b0 n0 : t,
0 <= a0 ->
0 <= b0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
Aux2:forall a0 b0 n0 : t,
0 <= a0 ->
n0 ~= 0 ->
(a0 rem n0 * b0) rem n0 == (a0 * b0) rem n0
a, b, n:t
Hn:n ~= 0
LT:0 < - a
(- a rem n * b) rem n == (- a * b) rem n
apply Aux2; order.
Qed.

Lemma mul_rem_idemp_r : forall a b n, n~=0 ->
 (a*(b rem n)) rem n == (a*b) rem n.forall a b n : t,
n ~= 0 -> (a * (b rem n)) rem n == (a * b) rem n
Proof.forall a b n : t,
n ~= 0 -> (a * (b rem n)) rem n == (a * b) rem n
intros.a, b, n:t
H:n ~= 0
(a * (b rem n)) rem n == (a * b) rem n rewrite !(mul_comm a).a, b, n:t
H:n ~= 0
(b rem n * a) rem n == (b * a) rem n now apply mul_rem_idemp_l.
Qed.

Theorem mul_rem: forall a b n, n~=0 ->
 (a * b) rem n == ((a rem n) * (b rem n)) rem n.forall a b n : t,
n ~= 0 -> (a * b) rem n == (a rem n * (b rem n)) rem n
Proof.forall a b n : t,
n ~= 0 -> (a * b) rem n == (a rem n * (b rem n)) rem n
intros.a, b, n:t
H:n ~= 0
(a * b) rem n == (a rem n * (b rem n)) rem n now rewrite mul_rem_idemp_l, mul_rem_idemp_r.
Qed.

addition and modulo

Generally speaking, unlike with other conventions, we don't have (a+b) rem n = (a rem n + b rem n) rem n for any a and b. For instance, take (8 + (-10)) rem 3 = -2 whereas (8 rem 3 + (-10 rem 3)) rem 3 = 1.

Lemma add_rem_idemp_l : forall a b n, n~=0 -> 0 <= a*b ->
 ((a rem n)+b) rem n == (a+b) rem n.forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n
Proof.forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n
assert (Aux : forall a b n, 0<=a -> 0<=b -> n~=0 ->
          ((a rem n)+b) rem n == (a+b) rem n).forall a b n : t,
0 <= a ->
0 <= b ->
n ~= 0 -> (a rem n + b) rem n == (a + b) rem n
Aux:forall a b n : t,
0 <= a -> 0 <= b -> n ~= 0 -> (a rem n + b) rem n == (a + b) rem n
forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n
 intros.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
(a rem n + b) rem n == (a + b) rem n
Aux:forall a b n : t,
0 <= a -> 0 <= b -> n ~= 0 -> (a rem n + b) rem n == (a + b) rem n
forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n pos_or_neg n.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LE:0 <= n
(a rem n + b) rem n == (a + b) rem n
a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LT:0 < - n
(a rem n + b) rem n == (a + b) rem n
Aux:forall a b n : t,
0 <= a -> 0 <= b -> n ~= 0 -> (a rem n + b) rem n == (a + b) rem n
forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n apply NZQuot.add_mod_idemp_l; order.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LT:0 < - n
(a rem n + b) rem n == (a + b) rem n
Aux:forall a b n : t,
0 <= a -> 0 <= b -> n ~= 0 -> (a rem n + b) rem n == (a + b) rem n
forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n
 rewrite <- ! (rem_opp_r _ n) by order.a, b, n:t
H:0 <= a
H0:0 <= b
H1:n ~= 0
LT:0 < - n
(a rem - n + b) rem - n == (a + b) rem - n
Aux:forall a b n : t,
0 <= a -> 0 <= b -> n ~= 0 -> (a rem n + b) rem n == (a + b) rem n
forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n apply NZQuot.add_mod_idemp_l; order.Aux:forall a b n : t,
0 <= a -> 0 <= b -> n ~= 0 -> (a rem n + b) rem n == (a + b) rem n
forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a rem n + b) rem n == (a + b) rem n
intros a b n Hn Hab.Aux:forall a0 b0 n0 : t,
0 <= a0 -> 0 <= b0 -> n0 ~= 0 -> (a0 rem n0 + b0) rem n0 == (a0 + b0) rem n0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
(a rem n + b) rem n == (a + b) rem n destruct (le_0_mul _ _ Hab) as [(Ha,Hb)|(Ha,Hb)].Aux:forall a0 b0 n0 : t,
0 <= a0 -> 0 <= b0 -> n0 ~= 0 -> (a0 rem n0 + b0) rem n0 == (a0 + b0) rem n0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:0 <= a
Hb:0 <= b
(a rem n + b) rem n == (a + b) rem n
Aux:forall a0 b0 n0 : t,
0 <= a0 -> 0 <= b0 -> n0 ~= 0 -> (a0 rem n0 + b0) rem n0 == (a0 + b0) rem n0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
(a rem n + b) rem n == (a + b) rem n
now apply Aux.Aux:forall a0 b0 n0 : t,
0 <= a0 -> 0 <= b0 -> n0 ~= 0 -> (a0 rem n0 + b0) rem n0 == (a0 + b0) rem n0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
(a rem n + b) rem n == (a + b) rem n
apply opp_inj.Aux:forall a0 b0 n0 : t,
0 <= a0 -> 0 <= b0 -> n0 ~= 0 -> (a0 rem n0 + b0) rem n0 == (a0 + b0) rem n0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
- ((a rem n + b) rem n) == - ((a + b) rem n) rewrite <-2 rem_opp_l, 2 opp_add_distr, <-rem_opp_l by order.Aux:forall a0 b0 n0 : t,
0 <= a0 -> 0 <= b0 -> n0 ~= 0 -> (a0 rem n0 + b0) rem n0 == (a0 + b0) rem n0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
(- a rem n + - b) rem n == (- a + - b) rem n
rewrite <- opp_nonneg_nonpos in *.Aux:forall a0 b0 n0 : t,
0 <= a0 -> 0 <= b0 -> n0 ~= 0 -> (a0 rem n0 + b0) rem n0 == (a0 + b0) rem n0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:0 <= - a
Hb:0 <= - b
(- a rem n + - b) rem n == (- a + - b) rem n
now apply Aux.
Qed.

Lemma add_rem_idemp_r : forall a b n, n~=0 -> 0 <= a*b ->
 (a+(b rem n)) rem n == (a+b) rem n.forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a + b rem n) rem n == (a + b) rem n
Proof.forall a b n : t,
n ~= 0 ->
0 <= a * b -> (a + b rem n) rem n == (a + b) rem n
intros.a, b, n:t
H:n ~= 0
H0:0 <= a * b
(a + b rem n) rem n == (a + b) rem n rewrite !(add_comm a).a, b, n:t
H:n ~= 0
H0:0 <= a * b
(b rem n + a) rem n == (b + a) rem n apply add_rem_idemp_l; trivial.a, b, n:t
H:n ~= 0
H0:0 <= a * b
0 <= b * a
now rewrite mul_comm.
Qed.

Theorem add_rem: forall a b n, n~=0 -> 0 <= a*b ->
 (a+b) rem n == (a rem n + b rem n) rem n.forall a b n : t,
n ~= 0 ->
0 <= a * b ->
(a + b) rem n == (a rem n + b rem n) rem n
Proof.forall a b n : t,
n ~= 0 ->
0 <= a * b ->
(a + b) rem n == (a rem n + b rem n) rem n
intros a b n Hn Hab.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
(a + b) rem n == (a rem n + b rem n) rem n rewrite add_rem_idemp_l, add_rem_idemp_r; trivial.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
(a + b) rem n == (a + b) rem n
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
0 <= a * (b rem n)
reflexivity.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
0 <= a * (b rem n)
destruct (le_0_mul _ _ Hab) as [(Ha,Hb)|(Ha,Hb)];
 destruct (le_0_mul _ _ (rem_sign_mul b n Hn)) as [(Hb',Hm)|(Hb',Hm)];
 auto using mul_nonneg_nonneg, mul_nonpos_nonpos.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:0 <= a
Hb:0 <= b
Hb':b rem n <= 0
Hm:b <= 0
0 <= a * (b rem n)
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
Hb':0 <= b rem n
Hm:0 <= b
0 <= a * (b rem n)
 setoid_replace b with 0 by order.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:0 <= a
Hb:0 <= b
Hb':b rem n <= 0
Hm:b <= 0
0 <= a * (0 rem n)
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
Hb':0 <= b rem n
Hm:0 <= b
0 <= a * (b rem n) rewrite rem_0_l by order.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:0 <= a
Hb:0 <= b
Hb':b rem n <= 0
Hm:b <= 0
0 <= a * 0
a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
Hb':0 <= b rem n
Hm:0 <= b
0 <= a * (b rem n) nzsimpl; order.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
Hb':0 <= b rem n
Hm:0 <= b
0 <= a * (b rem n)
 setoid_replace b with 0 by order.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
Hb':0 <= b rem n
Hm:0 <= b
0 <= a * (0 rem n) rewrite rem_0_l by order.a, b, n:t
Hn:n ~= 0
Hab:0 <= a * b
Ha:a <= 0
Hb:b <= 0
Hb':0 <= b rem n
Hm:0 <= b
0 <= a * 0 nzsimpl; order.
Qed.

Conversely, the following results need less restrictions here.

Lemma quot_quot : forall a b c, b~=0 -> c~=0 ->
 (a÷b)÷c == a÷(b*c).forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Proof.forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
assert (Aux1 : forall a b c, 0<=a -> 0<b -> c~=0 -> (a÷b)÷c == a÷(b*c)).forall a b c : t,
0 <= a -> 0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 intros.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c) pos_or_neg c.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LE:0 <= c
a ÷ b ÷ c == a ÷ (b * c)
a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c) apply NZQuot.div_div; order.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 apply opp_inj.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
- (a ÷ b ÷ c) == - (a ÷ (b * c))
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c) rewrite <- 2 quot_opp_r, <- mul_opp_r; trivial.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
a ÷ b ÷ - c == a ÷ (b * - c)
a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 apply NZQuot.div_div; order.a, b, c:t
H:0 <= a
H0:0 < b
H1:c ~= 0
LT:0 < - c
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 rewrite <- neq_mul_0; intuition order.Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
assert (Aux2 : forall a b c, 0<=a -> b~=0 -> c~=0 -> (a÷b)÷c == a÷(b*c)).Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
0 <= a -> b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 intros.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c) pos_or_neg b.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LE:0 <= b
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c) apply Aux1; order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 apply opp_inj.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
- (a ÷ b ÷ c) == - (a ÷ (b * c))
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c) rewrite <- quot_opp_l, <- 2 quot_opp_r, <- mul_opp_l; trivial.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
a ÷ - b ÷ c == a ÷ (- b * c)
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 apply Aux1; trivial.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:0 <= a
H0:b ~= 0
H1:c ~= 0
LT:0 < - b
b * c ~= 0
Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
 rewrite <- neq_mul_0; intuition order.Aux1:forall a b c : t,
0 <= a ->
0 < b -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
Aux2:forall a b c : t,
0 <= a ->
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
forall a b c : t,
b ~= 0 -> c ~= 0 -> a ÷ b ÷ c == a ÷ (b * c)
intros.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
a ÷ b ÷ c == a ÷ (b * c) pos_or_neg a.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LE:0 <= a
a ÷ b ÷ c == a ÷ (b * c)
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
a ÷ b ÷ c == a ÷ (b * c) apply Aux2; order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
a ÷ b ÷ c == a ÷ (b * c)
apply opp_inj.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
- (a ÷ b ÷ c) == - (a ÷ (b * c)) rewrite <- 3 quot_opp_l; try order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
- a ÷ b ÷ c == - a ÷ (b * c)
Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
b * c ~= 0 apply Aux2; order.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
b * c ~= 0
rewrite <- neq_mul_0.Aux1:forall a0 b0 c0 : t,
0 <= a0 ->
0 < b0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
Aux2:forall a0 b0 c0 : t,
0 <= a0 ->
b0 ~= 0 ->
c0 ~= 0 -> a0 ÷ b0 ÷ c0 == a0 ÷ (b0 * c0)
a, b, c:t
H:b ~= 0
H0:c ~= 0
LT:0 < - a
b ~= 0 /\ c ~= 0 tauto.
Qed.

Lemma mod_mul_r : forall a b c, b~=0 -> c~=0 ->
 a rem (b*c) == a rem b + b*((a÷b) rem c).forall a b c : t,
b ~= 0 ->
c ~= 0 ->
a rem (b * c) == a rem b + b * ((a ÷ b) rem c)
Proof.forall a b c : t,
b ~= 0 ->
c ~= 0 ->
a rem (b * c) == a rem b + b * ((a ÷ b) rem c)
 intros a b c Hb Hc.a, b, c:t
Hb:b ~= 0
Hc:c ~= 0
a rem (b * c) == a rem b + b * ((a ÷ b) rem c)
 apply add_cancel_l with (b*c*(a÷(b*c))).a, b, c:t
Hb:b ~= 0
Hc:c ~= 0
b * c * (a ÷ (b * c)) + a rem (b * c) ==
b * c * (a ÷ (b * c)) +
(a rem b + b * ((a ÷ b) rem c))
 rewrite <- quot_rem by (apply neq_mul_0; split; order).a, b, c:t
Hb:b ~= 0
Hc:c ~= 0
a ==
b * c * (a ÷ (b * c)) +
(a rem b + b * ((a ÷ b) rem c))
 rewrite <- quot_quot by trivial.a, b, c:t
Hb:b ~= 0
Hc:c ~= 0
a ==
b * c * (a ÷ b ÷ c) + (a rem b + b * ((a ÷ b) rem c))
 rewrite add_assoc, add_shuffle0, <- mul_assoc, <- mul_add_distr_l.a, b, c:t
Hb:b ~= 0
Hc:c ~= 0
a == b * (c * (a ÷ b ÷ c) + (a ÷ b) rem c) + a rem b
 rewrite <- quot_rem by order.a, b, c:t
Hb:b ~= 0
Hc:c ~= 0
a == b * (a ÷ b) + a rem b
 apply quot_rem; order.
Qed.

Lemma rem_quot: forall a b, b~=0 ->
 a rem b ÷ b == 0.forall a b : t, b ~= 0 -> a rem b ÷ b == 0
Proof.forall a b : t, b ~= 0 -> a rem b ÷ b == 0
 intros a b Hb.a, b:t
Hb:b ~= 0
a rem b ÷ b == 0
 rewrite quot_small_iff by assumption.a, b:t
Hb:b ~= 0
abs (a rem b) < abs b
 auto using rem_bound_abs.
Qed.

A last inequality:

Theorem quot_mul_le:
 forall a b c, 0<=a -> 0<b -> 0<=c -> c*(a÷b) <= (c*a)÷b.forall a b c : t,
0 <= a -> 0 < b -> 0 <= c -> c * (a ÷ b) <= c * a ÷ b
Proof.forall a b c : t,
0 <= a -> 0 < b -> 0 <= c -> c * (a ÷ b) <= c * a ÷ b exact NZQuot.div_mul_le. Qed.

End ZQuotProp.