blob: a0dd717697a62f532193bea717aba43d02d5e367 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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.
|