src/HOL/Old_Number_Theory/Legacy_GCD.thy
changeset 57514 bdc2c6b40bf2
parent 57512 cc97b347b301
child 58623 2db1df2c8467
equal deleted inserted replaced
57513:55b2afc5ddfc 57514:bdc2c6b40bf2
   349           from H (3) have "a * ((b - 1) * y) + d * (b - 1 + 1) = d + x*b*(b - 1)" by algebra
   349           from H (3) have "a * ((b - 1) * y) + d * (b - 1 + 1) = d + x*b*(b - 1)" by algebra
   350           hence "a * ((b - 1) * y) = d + x*b*(b - 1) - d*b" using bp by simp
   350           hence "a * ((b - 1) * y) = d + x*b*(b - 1) - d*b" using bp by simp
   351           hence "a * ((b - 1) * y) = d + (x*b*(b - 1) - d*b)" 
   351           hence "a * ((b - 1) * y) = d + (x*b*(b - 1) - d*b)" 
   352             by (simp only: diff_add_assoc[OF dble, of d, symmetric])
   352             by (simp only: diff_add_assoc[OF dble, of d, symmetric])
   353           hence "a * ((b - 1) * y) = b*(x*(b - 1) - d) + d"
   353           hence "a * ((b - 1) * y) = b*(x*(b - 1) - d) + d"
   354             by (simp only: diff_mult_distrib2 add.commute mult_ac)
   354             by (simp only: diff_mult_distrib2 add.commute ac_simps)
   355           hence ?thesis using H(1,2)
   355           hence ?thesis using H(1,2)
   356             apply -
   356             apply -
   357             apply (rule exI[where x=d], simp)
   357             apply (rule exI[where x=d], simp)
   358             apply (rule exI[where x="(b - 1) * y"])
   358             apply (rule exI[where x="(b - 1) * y"])
   359             by (rule exI[where x="x*(b - 1) - d"], simp)}
   359             by (rule exI[where x="x*(b - 1) - d"], simp)}
   490   from assms obtain p where k_m: "k = m * p" using dvd_def by blast
   490   from assms obtain p where k_m: "k = m * p" using dvd_def by blast
   491   from assms obtain q where k_n: "k = n * q" using dvd_def by blast
   491   from assms obtain q where k_n: "k = n * q" using dvd_def by blast
   492   from pos_k k_m have pos_p: "p > 0" by auto
   492   from pos_k k_m have pos_p: "p > 0" by auto
   493   from pos_k k_n have pos_q: "q > 0" by auto
   493   from pos_k k_n have pos_q: "q > 0" by auto
   494   have "k * k * gcd q p = k * gcd (k * q) (k * p)"
   494   have "k * k * gcd q p = k * gcd (k * q) (k * p)"
   495     by (simp add: mult_ac gcd_mult_distrib2)
   495     by (simp add: ac_simps gcd_mult_distrib2)
   496   also have "\<dots> = k * gcd (m * p * q) (n * q * p)"
   496   also have "\<dots> = k * gcd (m * p * q) (n * q * p)"
   497     by (simp add: k_m [symmetric] k_n [symmetric])
   497     by (simp add: k_m [symmetric] k_n [symmetric])
   498   also have "\<dots> = k * p * q * gcd m n"
   498   also have "\<dots> = k * p * q * gcd m n"
   499     by (simp add: mult_ac gcd_mult_distrib2)
   499     by (simp add: ac_simps gcd_mult_distrib2)
   500   finally have "(m * p) * (n * q) * gcd q p = k * p * q * gcd m n"
   500   finally have "(m * p) * (n * q) * gcd q p = k * p * q * gcd m n"
   501     by (simp only: k_m [symmetric] k_n [symmetric])
   501     by (simp only: k_m [symmetric] k_n [symmetric])
   502   then have "p * q * m * n * gcd q p = p * q * k * gcd m n"
   502   then have "p * q * m * n * gcd q p = p * q * k * gcd m n"
   503     by (simp add: mult_ac)
   503     by (simp add: ac_simps)
   504   with pos_p pos_q have "m * n * gcd q p = k * gcd m n"
   504   with pos_p pos_q have "m * n * gcd q p = k * gcd m n"
   505     by simp
   505     by simp
   506   with prod_gcd_lcm [of m n]
   506   with prod_gcd_lcm [of m n]
   507   have "lcm m n * gcd q p * gcd m n = k * gcd m n"
   507   have "lcm m n * gcd q p * gcd m n = k * gcd m n"
   508     by (simp add: mult_ac)
   508     by (simp add: ac_simps)
   509   with pos_gcd have "lcm m n * gcd q p = k" by simp
   509   with pos_gcd have "lcm m n * gcd q p = k" by simp
   510   then show ?thesis using dvd_def by auto
   510   then show ?thesis using dvd_def by auto
   511 qed
   511 qed
   512 
   512 
   513 lemma lcm_dvd1 [iff]:
   513 lemma lcm_dvd1 [iff]:
   523   next
   523   next
   524     case (Suc _)
   524     case (Suc _)
   525     then have npos: "n > 0" by simp
   525     then have npos: "n > 0" by simp
   526     have "gcd m n dvd n" by simp
   526     have "gcd m n dvd n" by simp
   527     then obtain k where "n = gcd m n * k" using dvd_def by auto
   527     then obtain k where "n = gcd m n * k" using dvd_def by auto
   528     then have "m * n div gcd m n = m * (gcd m n * k) div gcd m n" by (simp add: mult_ac)
   528     then have "m * n div gcd m n = m * (gcd m n * k) div gcd m n" by (simp add: ac_simps)
   529     also have "\<dots> = m * k" using mpos npos gcd_zero by simp
   529     also have "\<dots> = m * k" using mpos npos gcd_zero by simp
   530     finally show ?thesis by (simp add: lcm_def)
   530     finally show ?thesis by (simp add: lcm_def)
   531   qed
   531   qed
   532 qed
   532 qed
   533 
   533 
   544   next
   544   next
   545     case (Suc _)
   545     case (Suc _)
   546     then have mpos: "m > 0" by simp
   546     then have mpos: "m > 0" by simp
   547     have "gcd m n dvd m" by simp
   547     have "gcd m n dvd m" by simp
   548     then obtain k where "m = gcd m n * k" using dvd_def by auto
   548     then obtain k where "m = gcd m n * k" using dvd_def by auto
   549     then have "m * n div gcd m n = (gcd m n * k) * n div gcd m n" by (simp add: mult_ac)
   549     then have "m * n div gcd m n = (gcd m n * k) * n div gcd m n" by (simp add: ac_simps)
   550     also have "\<dots> = n * k" using mpos npos gcd_zero by simp
   550     also have "\<dots> = n * k" using mpos npos gcd_zero by simp
   551     finally show ?thesis by (simp add: lcm_def)
   551     finally show ?thesis by (simp add: lcm_def)
   552   qed
   552   qed
   553 qed
   553 qed
   554 
   554