proposition: Lemma mod_mult_cancel_r : forall (a b c : Z) (p : nat), Prime p -> ~ Mod c 0 p -> Mod (a * c) (b * c) p -> Mod a b p.
proof: Proof. intros. elim (mod_mult_inv_r c p). intro rc. intros. apply mod_trans with (a * c * rc)%Z. rewrite Zmult_assoc_reverse. pattern a at 1 in |- *. replace a with (a * 1)%Z. apply mod_mult_compat. apply mod_refl. apply mod_sym. assumption. rewrite Zmult_comm. apply Zmult_1_l. apply mod_trans with (b * c * rc)%Z. apply mod_mult_compat. assumption. apply mod_refl. rewrite Zmult_assoc_reverse. pattern b at 2 in |- *. replace b with (b * 1)%Z. apply mod_mult_compat. apply mod_refl. assumption. rewrite Zmult_comm. apply Zmult_1_l. assumption. assumption. Qed.
imports: Arith ZArith Wf_nat lemmas natZ dec list exp divides prime modulo gcd