src/HOL/Old_Number_Theory/Int2.thy
changeset 44766 d4d33a4d7548
parent 41541 1fa4725c4656
child 57512 cc97b347b301
equal deleted inserted replaced
44765:d96550db3d77 44766:d4d33a4d7548
    49 proof -
    49 proof -
    50   from `0 < z` have modth: "x mod z \<ge> 0" by simp
    50   from `0 < z` have modth: "x mod z \<ge> 0" by simp
    51   have "(x div z) * z \<le> (x div z) * z" by simp
    51   have "(x div z) * z \<le> (x div z) * z" by simp
    52   then have "(x div z) * z \<le> (x div z) * z + x mod z" using modth by arith 
    52   then have "(x div z) * z \<le> (x div z) * z + x mod z" using modth by arith 
    53   also have "\<dots> = x"
    53   also have "\<dots> = x"
    54     by (auto simp add: zmod_zdiv_equality [symmetric] zmult_ac)
    54     by (auto simp add: zmod_zdiv_equality [symmetric] mult_ac)
    55   also note `x < y * z`
    55   also note `x < y * z`
    56   finally show ?thesis
    56   finally show ?thesis
    57     apply (auto simp add: mult_less_cancel_right)
    57     apply (auto simp add: mult_less_cancel_right)
    58     using assms apply arith
    58     using assms apply arith
    59     done
    59     done
   113   apply (auto simp add: int_distrib)
   113   apply (auto simp add: int_distrib)
   114   done
   114   done
   115 
   115 
   116 lemma zcong_zmult_prop2: "[a = b](mod m) ==>
   116 lemma zcong_zmult_prop2: "[a = b](mod m) ==>
   117     ([c = d * a](mod m) = [c = d * b] (mod m))"
   117     ([c = d * a](mod m) = [c = d * b] (mod m))"
   118   by (auto simp add: zmult_ac zcong_zmult_prop1)
   118   by (auto simp add: mult_ac zcong_zmult_prop1)
   119 
   119 
   120 lemma zcong_zmult_prop3: "[| zprime p; ~[x = 0] (mod p);
   120 lemma zcong_zmult_prop3: "[| zprime p; ~[x = 0] (mod p);
   121     ~[y = 0] (mod p) |] ==> ~[x * y = 0] (mod p)"
   121     ~[y = 0] (mod p) |] ==> ~[x * y = 0] (mod p)"
   122   apply (auto simp add: zcong_def)
   122   apply (auto simp add: zcong_def)
   123   apply (drule zprime_zdvd_zmult_better, auto)
   123   apply (drule zprime_zdvd_zmult_better, auto)
   124   done
   124   done
   125 
   125 
   126 lemma zcong_less_eq: "[| 0 < x; 0 < y; 0 < m; [x = y] (mod m);
   126 lemma zcong_less_eq: "[| 0 < x; 0 < y; 0 < m; [x = y] (mod m);
   127     x < m; y < m |] ==> x = y"
   127     x < m; y < m |] ==> x = y"
   128   by (metis zcong_not zcong_sym zless_linear)
   128   by (metis zcong_not zcong_sym less_linear)
   129 
   129 
   130 lemma zcong_neg_1_impl_ne_1:
   130 lemma zcong_neg_1_impl_ne_1:
   131   assumes "2 < p" and "[x = -1] (mod p)"
   131   assumes "2 < p" and "[x = -1] (mod p)"
   132   shows "~([x = 1] (mod p))"
   132   shows "~([x = 1] (mod p))"
   133 proof
   133 proof
   196   finally (zcong_trans) show "[x * x ^ nat (p - 2) = 1] (mod p)" .
   196   finally (zcong_trans) show "[x * x ^ nat (p - 2) = 1] (mod p)" .
   197 qed
   197 qed
   198 
   198 
   199 lemma MultInv_prop2a: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==>
   199 lemma MultInv_prop2a: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==>
   200     [(MultInv p x) * x = 1] (mod p)"
   200     [(MultInv p x) * x = 1] (mod p)"
   201   by (auto simp add: MultInv_prop2 zmult_ac)
   201   by (auto simp add: MultInv_prop2 mult_ac)
   202 
   202 
   203 lemma aux_1: "2 < p ==> ((nat p) - 2) = (nat (p - 2))"
   203 lemma aux_1: "2 < p ==> ((nat p) - 2) = (nat (p - 2))"
   204   by (simp add: nat_diff_distrib)
   204   by (simp add: nat_diff_distrib)
   205 
   205 
   206 lemma aux_2: "2 < p ==> 0 < nat (p - 2)"
   206 lemma aux_2: "2 < p ==> 0 < nat (p - 2)"
   225     [(x * (MultInv p x) * (MultInv p (MultInv p x))) = x] (mod p)"
   225     [(x * (MultInv p x) * (MultInv p (MultInv p x))) = x] (mod p)"
   226   apply (frule MultInv_prop3, auto)
   226   apply (frule MultInv_prop3, auto)
   227   apply (insert MultInv_prop2 [of p "MultInv p x"], auto)
   227   apply (insert MultInv_prop2 [of p "MultInv p x"], auto)
   228   apply (drule MultInv_prop2, auto)
   228   apply (drule MultInv_prop2, auto)
   229   apply (drule_tac k = x in zcong_scalar2, auto)
   229   apply (drule_tac k = x in zcong_scalar2, auto)
   230   apply (auto simp add: zmult_ac)
   230   apply (auto simp add: mult_ac)
   231   done
   231   done
   232 
   232 
   233 lemma MultInv_prop4: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==>
   233 lemma MultInv_prop4: "[| 2 < p; zprime p; ~([x = 0](mod p)) |] ==>
   234     [(MultInv p (MultInv p x)) = x] (mod p)"
   234     [(MultInv p (MultInv p x)) = x] (mod p)"
   235   apply (frule aux__1, auto)
   235   apply (frule aux__1, auto)
   242     [x = y] (mod p)"
   242     [x = y] (mod p)"
   243   apply (drule_tac a = "MultInv p x" and b = "MultInv p y" and
   243   apply (drule_tac a = "MultInv p x" and b = "MultInv p y" and
   244     m = p and k = x in zcong_scalar)
   244     m = p and k = x in zcong_scalar)
   245   apply (insert MultInv_prop2 [of p x], simp)
   245   apply (insert MultInv_prop2 [of p x], simp)
   246   apply (auto simp only: zcong_sym [of "MultInv p x * x"])
   246   apply (auto simp only: zcong_sym [of "MultInv p x * x"])
   247   apply (auto simp add:  zmult_ac)
   247   apply (auto simp add: mult_ac)
   248   apply (drule zcong_trans, auto)
   248   apply (drule zcong_trans, auto)
   249   apply (drule_tac a = "x * MultInv p y" and k = y in zcong_scalar, auto)
   249   apply (drule_tac a = "x * MultInv p y" and k = y in zcong_scalar, auto)
   250   apply (insert MultInv_prop2a [of p y], auto simp add: zmult_ac)
   250   apply (insert MultInv_prop2a [of p y], auto simp add: mult_ac)
   251   apply (insert zcong_zmult_prop2 [of "y * MultInv p y" 1 p y x])
   251   apply (insert zcong_zmult_prop2 [of "y * MultInv p y" 1 p y x])
   252   apply (auto simp add: zcong_sym)
   252   apply (auto simp add: zcong_sym)
   253   done
   253   done
   254 
   254 
   255 lemma MultInv_zcong_prop1: "[| 2 < p; [j = k] (mod p) |] ==>
   255 lemma MultInv_zcong_prop1: "[| 2 < p; [j = k] (mod p) |] ==>
   262 
   262 
   263 lemma aux___2: "[|2 < p; zprime p; ~([k = 0](mod p));
   263 lemma aux___2: "[|2 < p; zprime p; ~([k = 0](mod p));
   264     [j * k = a * MultInv p k * k] (mod p) |] ==> [j * k = a] (mod p)"
   264     [j * k = a * MultInv p k * k] (mod p) |] ==> [j * k = a] (mod p)"
   265   apply (insert MultInv_prop2a [of p k] zcong_zmult_prop2
   265   apply (insert MultInv_prop2a [of p k] zcong_zmult_prop2
   266     [of "MultInv p k * k" 1 p "j * k" a])
   266     [of "MultInv p k * k" 1 p "j * k" a])
   267   apply (auto simp add: zmult_ac)
   267   apply (auto simp add: mult_ac)
   268   done
   268   done
   269 
   269 
   270 lemma aux___3: "[j * k = a] (mod p) ==> [(MultInv p j) * j * k =
   270 lemma aux___3: "[j * k = a] (mod p) ==> [(MultInv p j) * j * k =
   271      (MultInv p j) * a] (mod p)"
   271      (MultInv p j) * a] (mod p)"
   272   by (auto simp add: zmult_assoc zcong_scalar2)
   272   by (auto simp add: mult_assoc zcong_scalar2)
   273 
   273 
   274 lemma aux___4: "[|2 < p; zprime p; ~([j = 0](mod p));
   274 lemma aux___4: "[|2 < p; zprime p; ~([j = 0](mod p));
   275     [(MultInv p j) * j * k = (MultInv p j) * a] (mod p) |]
   275     [(MultInv p j) * j * k = (MultInv p j) * a] (mod p) |]
   276        ==> [k = a * (MultInv p j)] (mod p)"
   276        ==> [k = a * (MultInv p j)] (mod p)"
   277   apply (insert MultInv_prop2a [of p j] zcong_zmult_prop1
   277   apply (insert MultInv_prop2a [of p j] zcong_zmult_prop1
   278     [of "MultInv p j * j" 1 p "MultInv p j * a" k])
   278     [of "MultInv p j * j" 1 p "MultInv p j * a" k])
   279   apply (auto simp add: zmult_ac zcong_sym)
   279   apply (auto simp add: mult_ac zcong_sym)
   280   done
   280   done
   281 
   281 
   282 lemma MultInv_zcong_prop2: "[| 2 < p; zprime p; ~([k = 0](mod p));
   282 lemma MultInv_zcong_prop2: "[| 2 < p; zprime p; ~([k = 0](mod p));
   283     ~([j = 0](mod p)); [j = a * MultInv p k] (mod p) |] ==>
   283     ~([j = 0](mod p)); [j = a * MultInv p k] (mod p) |] ==>
   284     [k = a * MultInv p j] (mod p)"
   284     [k = a * MultInv p j] (mod p)"