From 9aa32499597678e3b0e7ef0b8a85ca5beda44938 Mon Sep 17 00:00:00 2001 From: James Pollard Date: Mon, 29 Jun 2020 12:21:38 +0100 Subject: Add missing file. --- src/common/ZExtra.v | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 src/common/ZExtra.v (limited to 'src/common') diff --git a/src/common/ZExtra.v b/src/common/ZExtra.v new file mode 100644 index 0000000..a0dd717 --- /dev/null +++ b/src/common/ZExtra.v @@ -0,0 +1,34 @@ +Require Import ZArith. +Require Import Lia. + +Local Open Scope Z_scope. + +Module ZExtra. + + Lemma mod_0_bounds : + forall x y m, + 0 < m -> + x mod m = 0 -> + y mod m = 0 -> + x <> y -> + x + m > y -> + y + m <= x. + Proof. + intros x y m. + intros POS XMOD YMOD NEQ H. + destruct (Z_le_gt_dec (y + m) x); eauto. + + apply Znumtheory.Zmod_divide in YMOD; try lia. + apply Znumtheory.Zmod_divide in XMOD; try lia. + inversion XMOD as [x']; subst; clear XMOD. + inversion YMOD as [y']; subst; clear YMOD. + + assert (x' <> y') as NEQ' by lia; clear NEQ. + + rewrite <- Z.mul_succ_l in H. + rewrite <- Z.mul_succ_l in g. + apply Zmult_gt_reg_r in H; + apply Zmult_gt_reg_r in g; lia. + Qed. + +End ZExtra. -- cgit