equal
deleted
inserted
replaced
14 \<close> |
14 \<close> |
15 |
15 |
16 subsection \<open>Specification of GCD on nats\<close> |
16 subsection \<open>Specification of GCD on nats\<close> |
17 |
17 |
18 definition |
18 definition |
19 is_gcd :: "nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> bool" where -- \<open>@{term gcd} as a relation\<close> |
19 is_gcd :: "nat \<Rightarrow> nat \<Rightarrow> nat \<Rightarrow> bool" where \<comment> \<open>@{term gcd} as a relation\<close> |
20 "is_gcd m n p \<longleftrightarrow> p dvd m \<and> p dvd n \<and> |
20 "is_gcd m n p \<longleftrightarrow> p dvd m \<and> p dvd n \<and> |
21 (\<forall>d. d dvd m \<longrightarrow> d dvd n \<longrightarrow> d dvd p)" |
21 (\<forall>d. d dvd m \<longrightarrow> d dvd n \<longrightarrow> d dvd p)" |
22 |
22 |
23 text \<open>Uniqueness\<close> |
23 text \<open>Uniqueness\<close> |
24 |
24 |
67 unfolding One_nat_def by (rule gcd_1) |
67 unfolding One_nat_def by (rule gcd_1) |
68 |
68 |
69 declare gcd.simps [simp del] |
69 declare gcd.simps [simp del] |
70 |
70 |
71 text \<open> |
71 text \<open> |
72 \medskip @{term "gcd m n"} divides @{text m} and @{text n}. The |
72 \medskip @{term "gcd m n"} divides \<open>m\<close> and \<open>n\<close>. The |
73 conjunctions don't seem provable separately. |
73 conjunctions don't seem provable separately. |
74 \<close> |
74 \<close> |
75 |
75 |
76 lemma gcd_dvd1 [iff, algebra]: "gcd m n dvd m" |
76 lemma gcd_dvd1 [iff, algebra]: "gcd m n dvd m" |
77 and gcd_dvd2 [iff, algebra]: "gcd m n dvd n" |
77 and gcd_dvd2 [iff, algebra]: "gcd m n dvd n" |
128 text \<open> |
128 text \<open> |
129 \medskip Multiplication laws |
129 \medskip Multiplication laws |
130 \<close> |
130 \<close> |
131 |
131 |
132 lemma gcd_mult_distrib2: "k * gcd m n = gcd (k * m) (k * n)" |
132 lemma gcd_mult_distrib2: "k * gcd m n = gcd (k * m) (k * n)" |
133 -- \<open>@{cite \<open>page 27\<close> davenport92}\<close> |
133 \<comment> \<open>@{cite \<open>page 27\<close> davenport92}\<close> |
134 apply (induct m n rule: gcd_induct) |
134 apply (induct m n rule: gcd_induct) |
135 apply simp |
135 apply simp |
136 apply (case_tac "k = 0") |
136 apply (case_tac "k = 0") |
137 apply (simp_all add: gcd_non_0) |
137 apply (simp_all add: gcd_non_0) |
138 done |
138 done |
695 apply (rule zgcd_assoc [THEN trans]) |
695 apply (rule zgcd_assoc [THEN trans]) |
696 apply (rule zgcd_commute [THEN arg_cong]) |
696 apply (rule zgcd_commute [THEN arg_cong]) |
697 done |
697 done |
698 |
698 |
699 lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute |
699 lemmas zgcd_ac = zgcd_assoc zgcd_commute zgcd_left_commute |
700 -- \<open>addition is an AC-operator\<close> |
700 \<comment> \<open>addition is an AC-operator\<close> |
701 |
701 |
702 lemma zgcd_zmult_distrib2: "0 \<le> k ==> k * zgcd m n = zgcd (k * m) (k * n)" |
702 lemma zgcd_zmult_distrib2: "0 \<le> k ==> k * zgcd m n = zgcd (k * m) (k * n)" |
703 by (simp del: minus_mult_right [symmetric] |
703 by (simp del: minus_mult_right [symmetric] |
704 add: minus_mult_right nat_mult_distrib zgcd_def abs_if |
704 add: minus_mult_right nat_mult_distrib zgcd_def abs_if |
705 mult_less_0_iff gcd_mult_distrib2 [symmetric] of_nat_mult) |
705 mult_less_0_iff gcd_mult_distrib2 [symmetric] of_nat_mult) |