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 |