# HG changeset patch # User haftmann # Date 1574502971 0 # Node ID 8bdf3c36011c1ffcf21e0a78c78d8e54438a4b34 # Parent 1299c8c91ed583b804cf1c2f5c10109a30ffcebd tuned theory structure diff -r 1299c8c91ed5 -r 8bdf3c36011c src/HOL/Euclidean_Division.thy --- a/src/HOL/Euclidean_Division.thy Sat Nov 23 16:02:42 2019 +0100 +++ b/src/HOL/Euclidean_Division.thy Sat Nov 23 09:56:11 2019 +0000 @@ -1711,6 +1711,239 @@ qed +subsection \Special case: euclidean rings containing the natural numbers\ + +class unique_euclidean_semiring_with_nat = semidom + semiring_char_0 + unique_euclidean_semiring + + assumes of_nat_div: "of_nat (m div n) = of_nat m div of_nat n" + and division_segment_of_nat [simp]: "division_segment (of_nat n) = 1" + and division_segment_euclidean_size [simp]: "division_segment a * of_nat (euclidean_size a) = a" +begin + +lemma division_segment_eq_iff: + "a = b" if "division_segment a = division_segment b" + and "euclidean_size a = euclidean_size b" + using that division_segment_euclidean_size [of a] by simp + +lemma euclidean_size_of_nat [simp]: + "euclidean_size (of_nat n) = n" +proof - + have "division_segment (of_nat n) * of_nat (euclidean_size (of_nat n)) = of_nat n" + by (fact division_segment_euclidean_size) + then show ?thesis by simp +qed + +lemma of_nat_euclidean_size: + "of_nat (euclidean_size a) = a div division_segment a" +proof - + have "of_nat (euclidean_size a) = division_segment a * of_nat (euclidean_size a) div division_segment a" + by (subst nonzero_mult_div_cancel_left) simp_all + also have "\ = a div division_segment a" + by simp + finally show ?thesis . +qed + +lemma division_segment_1 [simp]: + "division_segment 1 = 1" + using division_segment_of_nat [of 1] by simp + +lemma division_segment_numeral [simp]: + "division_segment (numeral k) = 1" + using division_segment_of_nat [of "numeral k"] by simp + +lemma euclidean_size_1 [simp]: + "euclidean_size 1 = 1" + using euclidean_size_of_nat [of 1] by simp + +lemma euclidean_size_numeral [simp]: + "euclidean_size (numeral k) = numeral k" + using euclidean_size_of_nat [of "numeral k"] by simp + +lemma of_nat_dvd_iff: + "of_nat m dvd of_nat n \ m dvd n" (is "?P \ ?Q") +proof (cases "m = 0") + case True + then show ?thesis + by simp +next + case False + show ?thesis + proof + assume ?Q + then show ?P + by auto + next + assume ?P + with False have "of_nat n = of_nat n div of_nat m * of_nat m" + by simp + then have "of_nat n = of_nat (n div m * m)" + by (simp add: of_nat_div) + then have "n = n div m * m" + by (simp only: of_nat_eq_iff) + then have "n = m * (n div m)" + by (simp add: ac_simps) + then show ?Q .. + qed +qed + +lemma of_nat_mod: + "of_nat (m mod n) = of_nat m mod of_nat n" +proof - + have "of_nat m div of_nat n * of_nat n + of_nat m mod of_nat n = of_nat m" + by (simp add: div_mult_mod_eq) + also have "of_nat m = of_nat (m div n * n + m mod n)" + by simp + finally show ?thesis + by (simp only: of_nat_div of_nat_mult of_nat_add) simp +qed + +lemma one_div_two_eq_zero [simp]: + "1 div 2 = 0" +proof - + from of_nat_div [symmetric] have "of_nat 1 div of_nat 2 = of_nat 0" + by (simp only:) simp + then show ?thesis + by simp +qed + +lemma one_mod_two_eq_one [simp]: + "1 mod 2 = 1" +proof - + from of_nat_mod [symmetric] have "of_nat 1 mod of_nat 2 = of_nat 1" + by (simp only:) simp + then show ?thesis + by simp +qed + +lemma one_mod_2_pow_eq [simp]: + "1 mod (2 ^ n) = of_bool (n > 0)" +proof - + have "1 mod (2 ^ n) = of_nat (1 mod (2 ^ n))" + using of_nat_mod [of 1 "2 ^ n"] by simp + also have "\ = of_bool (n > 0)" + by simp + finally show ?thesis . +qed + +lemma one_div_2_pow_eq [simp]: + "1 div (2 ^ n) = of_bool (n = 0)" + using div_mult_mod_eq [of 1 "2 ^ n"] by auto + +lemma div_mult2_eq': + "a div (of_nat m * of_nat n) = a div of_nat m div of_nat n" +proof (cases a "of_nat m * of_nat n" rule: divmod_cases) + case (divides q) + then show ?thesis + using nonzero_mult_div_cancel_right [of "of_nat m" "q * of_nat n"] + by (simp add: ac_simps) +next + case (remainder q r) + then have "division_segment r = 1" + using division_segment_of_nat [of "m * n"] by simp + with division_segment_euclidean_size [of r] + have "of_nat (euclidean_size r) = r" + by simp + have "a mod (of_nat m * of_nat n) div (of_nat m * of_nat n) = 0" + by simp + with remainder(6) have "r div (of_nat m * of_nat n) = 0" + by simp + with \of_nat (euclidean_size r) = r\ + have "of_nat (euclidean_size r) div (of_nat m * of_nat n) = 0" + by simp + then have "of_nat (euclidean_size r div (m * n)) = 0" + by (simp add: of_nat_div) + then have "of_nat (euclidean_size r div m div n) = 0" + by (simp add: div_mult2_eq) + with \of_nat (euclidean_size r) = r\ have "r div of_nat m div of_nat n = 0" + by (simp add: of_nat_div) + with remainder(1) + have "q = (r div of_nat m + q * of_nat n * of_nat m div of_nat m) div of_nat n" + by simp + with remainder(5) remainder(7) show ?thesis + using div_plus_div_distrib_dvd_right [of "of_nat m" "q * (of_nat m * of_nat n)" r] + by (simp add: ac_simps) +next + case by0 + then show ?thesis + by auto +qed + +lemma mod_mult2_eq': + "a mod (of_nat m * of_nat n) = of_nat m * (a div of_nat m mod of_nat n) + a mod of_nat m" +proof - + have "a div (of_nat m * of_nat n) * (of_nat m * of_nat n) + a mod (of_nat m * of_nat n) = a div of_nat m div of_nat n * of_nat n * of_nat m + (a div of_nat m mod of_nat n * of_nat m + a mod of_nat m)" + by (simp add: combine_common_factor div_mult_mod_eq) + moreover have "a div of_nat m div of_nat n * of_nat n * of_nat m = of_nat n * of_nat m * (a div of_nat m div of_nat n)" + by (simp add: ac_simps) + ultimately show ?thesis + by (simp add: div_mult2_eq' mult_commute) +qed + +lemma div_mult2_numeral_eq: + "a div numeral k div numeral l = a div numeral (k * l)" (is "?A = ?B") +proof - + have "?A = a div of_nat (numeral k) div of_nat (numeral l)" + by simp + also have "\ = a div (of_nat (numeral k) * of_nat (numeral l))" + by (fact div_mult2_eq' [symmetric]) + also have "\ = ?B" + by simp + finally show ?thesis . +qed + +lemma numeral_Bit0_div_2: + "numeral (num.Bit0 n) div 2 = numeral n" +proof - + have "numeral (num.Bit0 n) = numeral n + numeral n" + by (simp only: numeral.simps) + also have "\ = numeral n * 2" + by (simp add: mult_2_right) + finally have "numeral (num.Bit0 n) div 2 = numeral n * 2 div 2" + by simp + also have "\ = numeral n" + by (rule nonzero_mult_div_cancel_right) simp + finally show ?thesis . +qed + +lemma numeral_Bit1_div_2: + "numeral (num.Bit1 n) div 2 = numeral n" +proof - + have "numeral (num.Bit1 n) = numeral n + numeral n + 1" + by (simp only: numeral.simps) + also have "\ = numeral n * 2 + 1" + by (simp add: mult_2_right) + finally have "numeral (num.Bit1 n) div 2 = (numeral n * 2 + 1) div 2" + by simp + also have "\ = numeral n * 2 div 2 + 1 div 2" + using dvd_triv_right by (rule div_plus_div_distrib_dvd_left) + also have "\ = numeral n * 2 div 2" + by simp + also have "\ = numeral n" + by (rule nonzero_mult_div_cancel_right) simp + finally show ?thesis . +qed + +lemma exp_mod_exp: + \2 ^ m mod 2 ^ n = of_bool (m < n) * 2 ^ m\ +proof - + have \(2::nat) ^ m mod 2 ^ n = of_bool (m < n) * 2 ^ m\ (is \?lhs = ?rhs\) + by (auto simp add: not_less monoid_mult_class.power_add dest!: le_Suc_ex) + then have \of_nat ?lhs = of_nat ?rhs\ + by simp + then show ?thesis + by (simp add: of_nat_mod) +qed + +end + +class unique_euclidean_ring_with_nat = ring + unique_euclidean_semiring_with_nat + +instance nat :: unique_euclidean_semiring_with_nat + by standard (simp_all add: dvd_eq_mod_eq_0) + +instance int :: unique_euclidean_ring_with_nat + by standard (simp_all add: dvd_eq_mod_eq_0 divide_int_def division_segment_int_def) + + subsection \Code generation\ code_identifier diff -r 1299c8c91ed5 -r 8bdf3c36011c src/HOL/Parity.thy --- a/src/HOL/Parity.thy Sat Nov 23 16:02:42 2019 +0100 +++ b/src/HOL/Parity.thy Sat Nov 23 09:56:11 2019 +0000 @@ -166,107 +166,9 @@ subsection \Special case: euclidean rings containing the natural numbers\ -class unique_euclidean_semiring_with_nat = semidom + semiring_char_0 + unique_euclidean_semiring + - assumes of_nat_div: "of_nat (m div n) = of_nat m div of_nat n" - and division_segment_of_nat [simp]: "division_segment (of_nat n) = 1" - and division_segment_euclidean_size [simp]: "division_segment a * of_nat (euclidean_size a) = a" +context unique_euclidean_semiring_with_nat begin -lemma division_segment_eq_iff: - "a = b" if "division_segment a = division_segment b" - and "euclidean_size a = euclidean_size b" - using that division_segment_euclidean_size [of a] by simp - -lemma euclidean_size_of_nat [simp]: - "euclidean_size (of_nat n) = n" -proof - - have "division_segment (of_nat n) * of_nat (euclidean_size (of_nat n)) = of_nat n" - by (fact division_segment_euclidean_size) - then show ?thesis by simp -qed - -lemma of_nat_euclidean_size: - "of_nat (euclidean_size a) = a div division_segment a" -proof - - have "of_nat (euclidean_size a) = division_segment a * of_nat (euclidean_size a) div division_segment a" - by (subst nonzero_mult_div_cancel_left) simp_all - also have "\ = a div division_segment a" - by simp - finally show ?thesis . -qed - -lemma division_segment_1 [simp]: - "division_segment 1 = 1" - using division_segment_of_nat [of 1] by simp - -lemma division_segment_numeral [simp]: - "division_segment (numeral k) = 1" - using division_segment_of_nat [of "numeral k"] by simp - -lemma euclidean_size_1 [simp]: - "euclidean_size 1 = 1" - using euclidean_size_of_nat [of 1] by simp - -lemma euclidean_size_numeral [simp]: - "euclidean_size (numeral k) = numeral k" - using euclidean_size_of_nat [of "numeral k"] by simp - -lemma of_nat_dvd_iff: - "of_nat m dvd of_nat n \ m dvd n" (is "?P \ ?Q") -proof (cases "m = 0") - case True - then show ?thesis - by simp -next - case False - show ?thesis - proof - assume ?Q - then show ?P - by auto - next - assume ?P - with False have "of_nat n = of_nat n div of_nat m * of_nat m" - by simp - then have "of_nat n = of_nat (n div m * m)" - by (simp add: of_nat_div) - then have "n = n div m * m" - by (simp only: of_nat_eq_iff) - then have "n = m * (n div m)" - by (simp add: ac_simps) - then show ?Q .. - qed -qed - -lemma of_nat_mod: - "of_nat (m mod n) = of_nat m mod of_nat n" -proof - - have "of_nat m div of_nat n * of_nat n + of_nat m mod of_nat n = of_nat m" - by (simp add: div_mult_mod_eq) - also have "of_nat m = of_nat (m div n * n + m mod n)" - by simp - finally show ?thesis - by (simp only: of_nat_div of_nat_mult of_nat_add) simp -qed - -lemma one_div_two_eq_zero [simp]: - "1 div 2 = 0" -proof - - from of_nat_div [symmetric] have "of_nat 1 div of_nat 2 = of_nat 0" - by (simp only:) simp - then show ?thesis - by simp -qed - -lemma one_mod_two_eq_one [simp]: - "1 mod 2 = 1" -proof - - from of_nat_mod [symmetric] have "of_nat 1 mod of_nat 2 = of_nat 1" - by (simp only:) simp - then show ?thesis - by simp -qed - subclass semiring_parity proof show "2 dvd a \ a mod 2 = 0" for a @@ -323,20 +225,6 @@ finally show ?thesis . qed -lemma one_mod_2_pow_eq [simp]: - "1 mod (2 ^ n) = of_bool (n > 0)" -proof - - have "1 mod (2 ^ n) = of_nat (1 mod (2 ^ n))" - using of_nat_mod [of 1 "2 ^ n"] by simp - also have "\ = of_bool (n > 0)" - by simp - finally show ?thesis . -qed - -lemma one_div_2_pow_eq [simp]: - "1 div (2 ^ n) = of_bool (n = 0)" - using div_mult_mod_eq [of 1 "2 ^ n"] by auto - lemma even_succ_div_two [simp]: "even a \ (a + 1) div 2 = a div 2" by (cases "a = 0") (auto elim!: evenE dest: mult_not_zero) @@ -386,114 +274,9 @@ "coprime a 2 \ odd a" using coprime_left_2_iff_odd [of a] by (simp add: ac_simps) -lemma div_mult2_eq': - "a div (of_nat m * of_nat n) = a div of_nat m div of_nat n" -proof (cases a "of_nat m * of_nat n" rule: divmod_cases) - case (divides q) - then show ?thesis - using nonzero_mult_div_cancel_right [of "of_nat m" "q * of_nat n"] - by (simp add: ac_simps) -next - case (remainder q r) - then have "division_segment r = 1" - using division_segment_of_nat [of "m * n"] by simp - with division_segment_euclidean_size [of r] - have "of_nat (euclidean_size r) = r" - by simp - have "a mod (of_nat m * of_nat n) div (of_nat m * of_nat n) = 0" - by simp - with remainder(6) have "r div (of_nat m * of_nat n) = 0" - by simp - with \of_nat (euclidean_size r) = r\ - have "of_nat (euclidean_size r) div (of_nat m * of_nat n) = 0" - by simp - then have "of_nat (euclidean_size r div (m * n)) = 0" - by (simp add: of_nat_div) - then have "of_nat (euclidean_size r div m div n) = 0" - by (simp add: div_mult2_eq) - with \of_nat (euclidean_size r) = r\ have "r div of_nat m div of_nat n = 0" - by (simp add: of_nat_div) - with remainder(1) - have "q = (r div of_nat m + q * of_nat n * of_nat m div of_nat m) div of_nat n" - by simp - with remainder(5) remainder(7) show ?thesis - using div_plus_div_distrib_dvd_right [of "of_nat m" "q * (of_nat m * of_nat n)" r] - by (simp add: ac_simps) -next - case by0 - then show ?thesis - by auto -qed - -lemma mod_mult2_eq': - "a mod (of_nat m * of_nat n) = of_nat m * (a div of_nat m mod of_nat n) + a mod of_nat m" -proof - - have "a div (of_nat m * of_nat n) * (of_nat m * of_nat n) + a mod (of_nat m * of_nat n) = a div of_nat m div of_nat n * of_nat n * of_nat m + (a div of_nat m mod of_nat n * of_nat m + a mod of_nat m)" - by (simp add: combine_common_factor div_mult_mod_eq) - moreover have "a div of_nat m div of_nat n * of_nat n * of_nat m = of_nat n * of_nat m * (a div of_nat m div of_nat n)" - by (simp add: ac_simps) - ultimately show ?thesis - by (simp add: div_mult2_eq' mult_commute) -qed - -lemma div_mult2_numeral_eq: - "a div numeral k div numeral l = a div numeral (k * l)" (is "?A = ?B") -proof - - have "?A = a div of_nat (numeral k) div of_nat (numeral l)" - by simp - also have "\ = a div (of_nat (numeral k) * of_nat (numeral l))" - by (fact div_mult2_eq' [symmetric]) - also have "\ = ?B" - by simp - finally show ?thesis . -qed - -lemma numeral_Bit0_div_2: - "numeral (num.Bit0 n) div 2 = numeral n" -proof - - have "numeral (num.Bit0 n) = numeral n + numeral n" - by (simp only: numeral.simps) - also have "\ = numeral n * 2" - by (simp add: mult_2_right) - finally have "numeral (num.Bit0 n) div 2 = numeral n * 2 div 2" - by simp - also have "\ = numeral n" - by (rule nonzero_mult_div_cancel_right) simp - finally show ?thesis . -qed - -lemma numeral_Bit1_div_2: - "numeral (num.Bit1 n) div 2 = numeral n" -proof - - have "numeral (num.Bit1 n) = numeral n + numeral n + 1" - by (simp only: numeral.simps) - also have "\ = numeral n * 2 + 1" - by (simp add: mult_2_right) - finally have "numeral (num.Bit1 n) div 2 = (numeral n * 2 + 1) div 2" - by simp - also have "\ = numeral n * 2 div 2 + 1 div 2" - using dvd_triv_right by (rule div_plus_div_distrib_dvd_left) - also have "\ = numeral n * 2 div 2" - by simp - also have "\ = numeral n" - by (rule nonzero_mult_div_cancel_right) simp - finally show ?thesis . -qed - -lemma exp_mod_exp: - \2 ^ m mod 2 ^ n = of_bool (m < n) * 2 ^ m\ -proof - - have \(2::nat) ^ m mod 2 ^ n = of_bool (m < n) * 2 ^ m\ (is \?lhs = ?rhs\) - by (auto simp add: not_less monoid_mult_class.power_add dest!: le_Suc_ex) - then have \of_nat ?lhs = of_nat ?rhs\ - by simp - then show ?thesis - by (simp add: of_nat_mod) -qed - end -class unique_euclidean_ring_with_nat = ring + unique_euclidean_semiring_with_nat +context unique_euclidean_ring_with_nat begin subclass ring_parity .. @@ -739,9 +522,6 @@ subsection \Instance for \<^typ>\int\\ -instance int :: unique_euclidean_ring_with_nat - by standard (simp_all add: dvd_eq_mod_eq_0 divide_int_def division_segment_int_def) - lemma even_diff_iff: "even (k - l) \ even (k + l)" for k l :: int by (fact even_diff)