893 thus "\<exists>(i'::int) j::int. real i/real n = real i'/real j \<and> j \<noteq> 0" by blast |
893 thus "\<exists>(i'::int) j::int. real i/real n = real i'/real j \<and> j \<noteq> 0" by blast |
894 qed |
894 qed |
895 |
895 |
896 lemma Rats_abs_nat_div_natE: |
896 lemma Rats_abs_nat_div_natE: |
897 assumes "x \<in> \<rat>" |
897 assumes "x \<in> \<rat>" |
898 obtains m n where "n \<noteq> 0" and "\<bar>x\<bar> = real m / real n" and "gcd m n = 1" |
898 obtains m n :: nat |
|
899 where "n \<noteq> 0" and "\<bar>x\<bar> = real m / real n" and "gcd m n = 1" |
899 proof - |
900 proof - |
900 from `x \<in> \<rat>` obtain i::int and n::nat where "n \<noteq> 0" and "x = real i / real n" |
901 from `x \<in> \<rat>` obtain i::int and n::nat where "n \<noteq> 0" and "x = real i / real n" |
901 by(auto simp add: Rats_eq_int_div_nat) |
902 by(auto simp add: Rats_eq_int_div_nat) |
902 hence "\<bar>x\<bar> = real(nat(abs i)) / real n" by simp |
903 hence "\<bar>x\<bar> = real(nat(abs i)) / real n" by simp |
903 then obtain m :: nat where x_rat: "\<bar>x\<bar> = real m / real n" by blast |
904 then obtain m :: nat where x_rat: "\<bar>x\<bar> = real m / real n" by blast |
904 let ?gcd = "gcd m n" |
905 let ?gcd = "gcd m n" |
905 from `n\<noteq>0` have gcd: "?gcd \<noteq> 0" by (simp add: gcd_zero) |
906 from `n\<noteq>0` have gcd: "?gcd \<noteq> 0" by simp |
906 let ?k = "m div ?gcd" |
907 let ?k = "m div ?gcd" |
907 let ?l = "n div ?gcd" |
908 let ?l = "n div ?gcd" |
908 let ?gcd' = "gcd ?k ?l" |
909 let ?gcd' = "gcd ?k ?l" |
909 have "?gcd dvd m" .. then have gcd_k: "?gcd * ?k = m" |
910 have "?gcd dvd m" .. then have gcd_k: "?gcd * ?k = m" |
910 by (rule dvd_mult_div_cancel) |
911 by (rule dvd_mult_div_cancel) |
922 qed |
923 qed |
923 moreover |
924 moreover |
924 have "?gcd' = 1" |
925 have "?gcd' = 1" |
925 proof - |
926 proof - |
926 have "?gcd * ?gcd' = gcd (?gcd * ?k) (?gcd * ?l)" |
927 have "?gcd * ?gcd' = gcd (?gcd * ?k) (?gcd * ?l)" |
927 by (rule gcd_mult_distrib2) |
928 by (rule nat_gcd_mult_distrib) |
928 with gcd_k gcd_l have "?gcd * ?gcd' = ?gcd" by simp |
929 with gcd_k gcd_l have "?gcd * ?gcd' = ?gcd" by simp |
929 with gcd show ?thesis by simp |
930 with gcd show ?thesis by auto |
930 qed |
931 qed |
931 ultimately show ?thesis .. |
932 ultimately show ?thesis .. |
932 qed |
933 qed |
933 |
934 |
934 |
935 |