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