src/HOL/GCD.thy
changeset 37770 cddb3106adb8
parent 36350 bc7982c54e37
child 41550 efa734d9b221
equal deleted inserted replaced
37769:4511931c0692 37770:cddb3106adb8
   300   by (insert gcd_zero_nat [of m n], arith)
   300   by (insert gcd_zero_nat [of m n], arith)
   301 
   301 
   302 lemma gcd_pos_int [simp]: "(gcd (m::int) n > 0) = (m ~= 0 | n ~= 0)"
   302 lemma gcd_pos_int [simp]: "(gcd (m::int) n > 0) = (m ~= 0 | n ~= 0)"
   303   by (insert gcd_zero_int [of m n], insert gcd_ge_0_int [of m n], arith)
   303   by (insert gcd_zero_int [of m n], insert gcd_ge_0_int [of m n], arith)
   304 
   304 
   305 interpretation gcd_nat!: abel_semigroup "gcd :: nat \<Rightarrow> nat \<Rightarrow> nat"
   305 interpretation gcd_nat: abel_semigroup "gcd :: nat \<Rightarrow> nat \<Rightarrow> nat"
   306 proof
   306 proof
   307 qed (auto intro: dvd_antisym dvd_trans)
   307 qed (auto intro: dvd_antisym dvd_trans)
   308 
   308 
   309 interpretation gcd_int!: abel_semigroup "gcd :: int \<Rightarrow> int \<Rightarrow> int"
   309 interpretation gcd_int: abel_semigroup "gcd :: int \<Rightarrow> int \<Rightarrow> int"
   310 proof
   310 proof
   311 qed (simp_all add: gcd_int_def gcd_nat.assoc gcd_nat.commute gcd_nat.left_commute)
   311 qed (simp_all add: gcd_int_def gcd_nat.assoc gcd_nat.commute gcd_nat.left_commute)
   312 
   312 
   313 lemmas gcd_assoc_nat = gcd_nat.assoc
   313 lemmas gcd_assoc_nat = gcd_nat.assoc
   314 lemmas gcd_commute_nat = gcd_nat.commute
   314 lemmas gcd_commute_nat = gcd_nat.commute
  1381 
  1381 
  1382 lemma lcm_unique_int: "d >= 0 \<and> (a::int) dvd d \<and> b dvd d \<and>
  1382 lemma lcm_unique_int: "d >= 0 \<and> (a::int) dvd d \<and> b dvd d \<and>
  1383     (\<forall>e. a dvd e \<and> b dvd e \<longrightarrow> d dvd e) \<longleftrightarrow> d = lcm a b"
  1383     (\<forall>e. a dvd e \<and> b dvd e \<longrightarrow> d dvd e) \<longleftrightarrow> d = lcm a b"
  1384   by (auto intro: dvd_antisym [transferred] lcm_least_int)
  1384   by (auto intro: dvd_antisym [transferred] lcm_least_int)
  1385 
  1385 
  1386 interpretation lcm_nat!: abel_semigroup "lcm :: nat \<Rightarrow> nat \<Rightarrow> nat"
  1386 interpretation lcm_nat: abel_semigroup "lcm :: nat \<Rightarrow> nat \<Rightarrow> nat"
  1387 proof
  1387 proof
  1388   fix n m p :: nat
  1388   fix n m p :: nat
  1389   show "lcm (lcm n m) p = lcm n (lcm m p)"
  1389   show "lcm (lcm n m) p = lcm n (lcm m p)"
  1390     by (rule lcm_unique_nat [THEN iffD1]) (metis dvd.order_trans lcm_unique_nat)
  1390     by (rule lcm_unique_nat [THEN iffD1]) (metis dvd.order_trans lcm_unique_nat)
  1391   show "lcm m n = lcm n m"
  1391   show "lcm m n = lcm n m"
  1392     by (simp add: lcm_nat_def gcd_commute_nat field_simps)
  1392     by (simp add: lcm_nat_def gcd_commute_nat field_simps)
  1393 qed
  1393 qed
  1394 
  1394 
  1395 interpretation lcm_int!: abel_semigroup "lcm :: int \<Rightarrow> int \<Rightarrow> int"
  1395 interpretation lcm_int: abel_semigroup "lcm :: int \<Rightarrow> int \<Rightarrow> int"
  1396 proof
  1396 proof
  1397   fix n m p :: int
  1397   fix n m p :: int
  1398   show "lcm (lcm n m) p = lcm n (lcm m p)"
  1398   show "lcm (lcm n m) p = lcm n (lcm m p)"
  1399     by (rule lcm_unique_int [THEN iffD1]) (metis dvd_trans lcm_unique_int)
  1399     by (rule lcm_unique_int [THEN iffD1]) (metis dvd_trans lcm_unique_int)
  1400   show "lcm m n = lcm n m"
  1400   show "lcm m n = lcm n m"