proposition: Lemma egcd_log2_ok: forall c a b, match egcd_log2 a b c with None => True | Some (u,v,r) => u * a + v * b = r end.
proof: Proof. induction c; simpl; auto; intros a b; generalize (div_eucl_spec a b); case (a/b); simpl fst; simpl snd; intros q r1; case r1; try (intros; ring); simpl; intros r (Hr1, Hr2); clear r1; generalize (div_eucl_spec b r); case (b/r); simpl fst; simpl snd; intros q' r1; case r1; try (intros; rewrite Hr1; ring); simpl; intros r' (Hr'1, Hr'2); clear r1; auto; generalize (IHc r r'); case egcd_log2; auto; intros ((u',v'),w'); case gcd_log2; auto; intros; rw ((I, H), Hr1, Hr'1); ring. Qed.
imports: ZArith Lia ZCmisc