proposition: Lemma add_mul_mod_distr_l: forall a b c d, 0<=a -> 0<b -> 0<=d<c -> (c*a+d) mod (c*b) == c*(a mod b)+d.
proof: Proof. intros a b c d ? ? [? ?]. assert (0 <= a*c) by (apply mul_nonneg_nonneg; order). assert (0 <= a*c+d) by (apply add_nonneg_nonneg; order). rewrite (mul_comm c a), mod_mul_r, add_mod, mod_mul, div_add_l; [|order ..]. now rewrite ? add_0_l, div_small, add_0_r, ? (mod_small d c), (add_comm d). Qed.
imports: NZAxioms NZMulOrder