src/HOL/Number_Theory/UniqueFactorization.thy
changeset 62430 9527ff088c15
parent 62429 25271ff79171
child 63534 523b488b15c9
equal deleted inserted replaced
62429:25271ff79171 62430:9527ff088c15
    91     then show ?thesis
    91     then show ?thesis
    92       by (subst (1) b, subst setprod.union_disjoint, auto)
    92       by (subst (1) b, subst setprod.union_disjoint, auto)
    93   next
    93   next
    94     case False
    94     case False
    95     then show ?thesis
    95     then show ?thesis
    96       by auto
    96       by (auto simp add: not_in_iff)
    97   qed
    97   qed
    98   finally have "a ^ count M a dvd a ^ count N a * (\<Prod>i \<in> (set_mset N - {a}). i ^ count N i)" .
    98   finally have "a ^ count M a dvd a ^ count N a * (\<Prod>i \<in> (set_mset N - {a}). i ^ count N i)" .
    99   moreover
    99   moreover
   100   have "coprime (a ^ count M a) (\<Prod>i \<in> (set_mset N - {a}). i ^ count N i)"
   100   have "coprime (a ^ count M a) (\<Prod>i \<in> (set_mset N - {a}). i ^ count N i)"
   101     apply (subst gcd.commute)
   101     apply (subst gcd.commute)
   109   with a show ?thesis
   109   with a show ?thesis
   110     using power_dvd_imp_le prime_def by blast
   110     using power_dvd_imp_le prime_def by blast
   111 next
   111 next
   112   case False
   112   case False
   113   then show ?thesis
   113   then show ?thesis
   114     by auto
   114     by (auto simp add: not_in_iff)
   115 qed
   115 qed
   116 
   116 
   117 lemma multiset_prime_factorization_unique:
   117 lemma multiset_prime_factorization_unique:
   118   assumes "\<forall>p::nat \<in> set_mset M. prime p"
   118   assumes "\<forall>p::nat \<in> set_mset M. prime p"
   119     and "\<forall>p \<in> set_mset N. prime p"
   119     and "\<forall>p \<in> set_mset N. prime p"
   435   fixes p n :: nat
   435   fixes p n :: nat
   436   shows "\<not> prime p \<Longrightarrow> multiplicity p n = 0"
   436   shows "\<not> prime p \<Longrightarrow> multiplicity p n = 0"
   437   apply (cases "n = 0")
   437   apply (cases "n = 0")
   438   apply auto
   438   apply auto
   439   apply (frule multiset_prime_factorization)
   439   apply (frule multiset_prime_factorization)
   440   apply (auto simp add: set_mset_def multiplicity_nat_def)
   440   apply (auto simp add: multiplicity_nat_def count_eq_zero_iff)
   441   done
   441   done
   442 
   442 
   443 lemma multiplicity_not_factor_nat [simp]:
   443 lemma multiplicity_not_factor_nat [simp]:
   444   fixes p n :: nat
   444   fixes p n :: nat
   445   shows "p \<notin> prime_factors n \<Longrightarrow> multiplicity p n = 0"
   445   shows "p \<notin> prime_factors n \<Longrightarrow> multiplicity p n = 0"