src/HOL/Old_Number_Theory/Legacy_GCD.thy
changeset 63167 0909deb8059b
parent 62348 9a5f43dac883
equal deleted inserted replaced
63166:143f58bb34f9 63167:0909deb8059b
    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)