src/HOL/Computational_Algebra/Euclidean_Algorithm.thy
changeset 69884 dec7cc38a5dc
parent 69064 5840724b1d71
child 71398 e0237f2eb49d
equal deleted inserted replaced
69883:f8293bf510a0 69884:dec7cc38a5dc
   233         let ?fctrs = "\<lambda>x. {p. p dvd x \<and> normalize p = p}"
   233         let ?fctrs = "\<lambda>x. {p. p dvd x \<and> normalize p = p}"
   234         from y have x: "x = y * z" by (simp add: z_def)
   234         from y have x: "x = y * z" by (simp add: z_def)
   235         with less.prems have "y \<noteq> 0" "z \<noteq> 0" by auto
   235         with less.prems have "y \<noteq> 0" "z \<noteq> 0" by auto
   236         have normalized_factors_product:
   236         have normalized_factors_product:
   237           "{p. p dvd a * b \<and> normalize p = p} = 
   237           "{p. p dvd a * b \<and> normalize p = p} = 
   238              (\<lambda>(x,y). x * y) ` ({p. p dvd a \<and> normalize p = p} \<times> {p. p dvd b \<and> normalize p = p})" for a b
   238              (\<lambda>(x,y). x * y) ` ({p. p dvd a \<and> normalize p = p} \<times> {p. p dvd b \<and> normalize p = p})"
       
   239           for a b
   239         proof safe
   240         proof safe
   240           fix p assume p: "p dvd a * b" "normalize p = p"
   241           fix p assume p: "p dvd a * b" "normalize p = p"
   241           from dvd_productE[OF p(1)] guess x y . note xy = this
   242           from p(1) obtain x y where xy: "p = x * y" "x dvd a" "y dvd b"
       
   243             by (rule dvd_productE)
   242           define x' y' where "x' = normalize x" and "y' = normalize y"
   244           define x' y' where "x' = normalize x" and "y' = normalize y"
   243           have "p = x' * y'"
   245           have "p = x' * y'"
   244             by (subst p(2) [symmetric]) (simp add: xy x'_def y'_def normalize_mult)
   246             by (subst p(2) [symmetric]) (simp add: xy x'_def y'_def normalize_mult)
   245           moreover from xy have "normalize x' = x'" "normalize y' = y'" "x' dvd a" "y' dvd b" 
   247           moreover from xy have "normalize x' = x'" "normalize y' = y'" "x' dvd a" "y' dvd b" 
   246             by (simp_all add: x'_def y'_def)
   248             by (simp_all add: x'_def y'_def)