equal
deleted
inserted
replaced
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" |