src/HOL/Number_Theory/Factorial_Ring.thy
changeset 63040 eb4ddd18d635
parent 62499 4a5b81ff5992
child 63060 293ede07b775
equal deleted inserted replaced
63039:1a20fd9cf281 63040:eb4ddd18d635
   256       by simp
   256       by simp
   257     then have "p dvd a * b"
   257     then have "p dvd a * b"
   258       by (rule dvd_mult_left)
   258       by (rule dvd_mult_left)
   259     with Suc \<open>is_prime p\<close> \<open>\<not> p dvd a\<close> have "p dvd b"
   259     with Suc \<open>is_prime p\<close> \<open>\<not> p dvd a\<close> have "p dvd b"
   260       by (simp add: prime_dvd_mult_iff)
   260       by (simp add: prime_dvd_mult_iff)
   261     moreover def c \<equiv> "b div p"
   261     moreover define c where "c = b div p"
   262     ultimately have b: "b = p * c" by simp
   262     ultimately have b: "b = p * c" by simp
   263     with * have "p * p ^ n dvd p * (a * c)"
   263     with * have "p * p ^ n dvd p * (a * c)"
   264       by (simp add: ac_simps)
   264       by (simp add: ac_simps)
   265     with \<open>p \<noteq> 0\<close> have "p ^ n dvd a * c"
   265     with \<open>p \<noteq> 0\<close> have "p ^ n dvd a * c"
   266       by simp
   266       by simp
   369     from \<open>insert p F = ?prime_factors a\<close>
   369     from \<open>insert p F = ?prime_factors a\<close>
   370     have "?prime_factors a = insert p F"
   370     have "?prime_factors a = insert p F"
   371       by simp
   371       by simp
   372     then have "p dvd a" and "is_prime p" and "normalize p = p" and "p \<noteq> 0"
   372     then have "p dvd a" and "is_prime p" and "normalize p = p" and "p \<noteq> 0"
   373       by (auto intro!: is_prime_not_zeroI)
   373       by (auto intro!: is_prime_not_zeroI)
   374     def n \<equiv> "Max {n. p ^ n dvd a}"
   374     define n where "n = Max {n. p ^ n dvd a}"
   375     then have "n > 0" and "p ^ n dvd a" and "\<not> p ^ Suc n dvd a" 
   375     then have "n > 0" and "p ^ n dvd a" and "\<not> p ^ Suc n dvd a" 
   376     proof -
   376     proof -
   377       def N \<equiv> "{n. p ^ n dvd a}"
   377       define N where "N = {n. p ^ n dvd a}"
   378       then have n_M: "n = Max N" by (simp add: n_def)
   378       then have n_M: "n = Max N" by (simp add: n_def)
   379       from is_prime_inj_power \<open>is_prime p\<close> have "inj (op ^ p)" .
   379       from is_prime_inj_power \<open>is_prime p\<close> have "inj (op ^ p)" .
   380       then have "inj_on (op ^ p) U" for U
   380       then have "inj_on (op ^ p) U" for U
   381         by (rule subset_inj_on) simp
   381         by (rule subset_inj_on) simp
   382       moreover have "op ^ p ` N \<subseteq> {b. b dvd a \<and> normalize b = b}"
   382       moreover have "op ^ p ` N \<subseteq> {b. b dvd a \<and> normalize b = b}"
   400       then have "\<not> p ^ Suc (Max N) dvd a"
   400       then have "\<not> p ^ Suc (Max N) dvd a"
   401         by auto
   401         by auto
   402       then show "\<not> p ^ Suc n dvd a"
   402       then show "\<not> p ^ Suc n dvd a"
   403         by (simp add: n_M)
   403         by (simp add: n_M)
   404     qed
   404     qed
   405     def b \<equiv> "a div p ^ n"
   405     define b where "b = a div p ^ n"
   406     with \<open>p ^ n dvd a\<close> have a: "a = p ^ n * b"
   406     with \<open>p ^ n dvd a\<close> have a: "a = p ^ n * b"
   407       by simp
   407       by simp
   408     with \<open>\<not> p ^ Suc n dvd a\<close> have "\<not> p dvd b" and "b \<noteq> 0"
   408     with \<open>\<not> p ^ Suc n dvd a\<close> have "\<not> p dvd b" and "b \<noteq> 0"
   409       by (auto elim: dvdE simp add: ac_simps)
   409       by (auto elim: dvdE simp add: ac_simps)
   410     have "?prime_factors a = insert p (?prime_factors b)"
   410     have "?prime_factors a = insert p (?prime_factors b)"
   464       qed
   464       qed
   465       then show
   465       then show
   466         "replicate_mset (Max {n. q ^ n dvd a}) q = replicate_mset (Max {n. q ^ n dvd b}) q"
   466         "replicate_mset (Max {n. q ^ n dvd a}) q = replicate_mset (Max {n. q ^ n dvd b}) q"
   467         by simp
   467         by simp
   468     qed
   468     qed
   469     def Q \<equiv> "the (factorization b)"
   469     define Q where "Q = the (factorization b)"
   470     with \<open>b \<noteq> 0\<close> have [simp]: "factorization b = Some Q"
   470     with \<open>b \<noteq> 0\<close> have [simp]: "factorization b = Some Q"
   471       by simp
   471       by simp
   472     from \<open>a \<noteq> 0\<close> have "factorization a =
   472     from \<open>a \<noteq> 0\<close> have "factorization a =
   473       Some (\<Sum>p\<in>?prime_factors a. replicate_mset (Max {n. p ^ n dvd a}) p)"
   473       Some (\<Sum>p\<in>?prime_factors a. replicate_mset (Max {n. p ^ n dvd a}) p)"
   474       by (simp add: factorization_def)
   474       by (simp add: factorization_def)