proposition: Theorem euclid_gcd : forall (d1 d2 : nat) (x y q r : Z), x = (q * y + r)%Z -> gcd x y d1 -> gcd r y d2 -> d1 = d2.
proof: Proof. intros. apply (gcd_unq d1 d2 r y). apply euclid_gcd1 with x q. assumption. assumption. assumption. Qed.
imports: ZArith Wf_nat lemmas natZ divides modulo