proposition: Lemma gauss : forall n m p, (n | m * p) -> gcd n m == 1 -> (n | p).
proof: Proof. intros n m p H G. destruct (eq_0_gt_0_cases n) as [EQ|LT]. - rewrite EQ in *. rewrite gcd_0_l in G. now rewrite <- (mul_1_l p), <- G. - destruct (gcd_bezout_pos n m) as (a & b & EQ); trivial. rewrite G in EQ. apply divide_add_cancel_r with (m*p*b). + now apply divide_mul_l. + rewrite (mul_comm _ b), mul_assoc. rewrite <- (mul_1_l p) at 2. rewrite <- mul_add_distr_r, add_comm, <- EQ. now apply divide_mul_l, divide_factor_r. Qed.
imports: NAxioms NSub NZGcd