proposition: Lemma prime_gcd : forall p n : nat, prime p -> ~ divides p n -> is_gcd n p 1.
proof: Proof. intros p n H' H'0; split; auto; split; auto. intros d H'1 H'2. case H'; intros H'3 H'4. case (eq_nat_dec d 1); intros H'5; auto. rewrite H'5; auto. case (eq_nat_dec p d); intros H'6; auto. case H'0; try rewrite H'6; auto. case H'6; auto. Qed.
imports: Coq(Arith ArithRing Peano_dec Wf_nat)