src/HOL/Old_Number_Theory/IntPrimes.thy
author wenzelm
Sun Sep 18 20:33:48 2016 +0200 (2016-09-18)
changeset 63915 bab633745c7f
parent 63167 0909deb8059b
child 64240 eabf80376aab
permissions -rw-r--r--
tuned proofs;
     1 (*  Title:      HOL/Old_Number_Theory/IntPrimes.thy
     2     Author:     Thomas M. Rasmussen
     3     Copyright   2000  University of Cambridge
     4 *)
     5 
     6 section \<open>Divisibility and prime numbers (on integers)\<close>
     7 
     8 theory IntPrimes
     9 imports Primes
    10 begin
    11 
    12 text \<open>
    13   The \<open>dvd\<close> relation, GCD, Euclid's extended algorithm, primes,
    14   congruences (all on the Integers).  Comparable to theory \<open>Primes\<close>, but \<open>dvd\<close> is included here as it is not present in
    15   main HOL.  Also includes extended GCD and congruences not present in
    16   \<open>Primes\<close>.
    17 \<close>
    18 
    19 
    20 subsection \<open>Definitions\<close>
    21 
    22 fun xzgcda :: "int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int => (int * int * int)"
    23 where
    24   "xzgcda m n r' r s' s t' t =
    25         (if r \<le> 0 then (r', s', t')
    26          else xzgcda m n r (r' mod r) 
    27                       s (s' - (r' div r) * s) 
    28                       t (t' - (r' div r) * t))"
    29 
    30 definition zprime :: "int \<Rightarrow> bool"
    31   where "zprime p = (1 < p \<and> (\<forall>m. 0 <= m & m dvd p --> m = 1 \<or> m = p))"
    32 
    33 definition xzgcd :: "int => int => int * int * int"
    34   where "xzgcd m n = xzgcda m n m n 1 0 0 1"
    35 
    36 definition zcong :: "int => int => int => bool"  ("(1[_ = _] '(mod _'))")
    37   where "[a = b] (mod m) = (m dvd (a - b))"
    38 
    39 
    40 subsection \<open>Euclid's Algorithm and GCD\<close>
    41 
    42 
    43 lemma zrelprime_zdvd_zmult_aux:
    44      "zgcd n k = 1 ==> k dvd m * n ==> 0 \<le> m ==> k dvd m"
    45     by (metis abs_of_nonneg dvd_triv_right zgcd_greatest_iff zgcd_zmult_distrib2_abs mult_1_right)
    46 
    47 lemma zrelprime_zdvd_zmult: "zgcd n k = 1 ==> k dvd m * n ==> k dvd m"
    48   apply (case_tac "0 \<le> m")
    49    apply (blast intro: zrelprime_zdvd_zmult_aux)
    50   apply (subgoal_tac "k dvd -m")
    51    apply (rule_tac [2] zrelprime_zdvd_zmult_aux, auto)
    52   done
    53 
    54 lemma zgcd_geq_zero: "0 <= zgcd x y"
    55   by (auto simp add: zgcd_def)
    56 
    57 text\<open>This is merely a sanity check on zprime, since the previous version
    58       denoted the empty set.\<close>
    59 lemma "zprime 2"
    60   apply (auto simp add: zprime_def) 
    61   apply (frule zdvd_imp_le, simp) 
    62   apply (auto simp add: order_le_less dvd_def) 
    63   done
    64 
    65 lemma zprime_imp_zrelprime:
    66     "zprime p ==> \<not> p dvd n ==> zgcd n p = 1"
    67   apply (auto simp add: zprime_def)
    68   apply (metis zgcd_geq_zero zgcd_zdvd1 zgcd_zdvd2)
    69   done
    70 
    71 lemma zless_zprime_imp_zrelprime:
    72     "zprime p ==> 0 < n ==> n < p ==> zgcd n p = 1"
    73   apply (erule zprime_imp_zrelprime)
    74   apply (erule zdvd_not_zless, assumption)
    75   done
    76 
    77 lemma zprime_zdvd_zmult:
    78     "0 \<le> (m::int) ==> zprime p ==> p dvd m * n ==> p dvd m \<or> p dvd n"
    79   by (metis zgcd_zdvd1 zgcd_zdvd2 zgcd_pos zprime_def zrelprime_dvd_mult)
    80 
    81 lemma zgcd_zadd_zmult [simp]: "zgcd (m + n * k) n = zgcd m n"
    82   apply (rule zgcd_eq [THEN trans])
    83   apply (simp add: mod_add_eq)
    84   apply (rule zgcd_eq [symmetric])
    85   done
    86 
    87 lemma zgcd_zdvd_zgcd_zmult: "zgcd m n dvd zgcd (k * m) n"
    88 by (simp add: zgcd_greatest_iff)
    89 
    90 lemma zgcd_zmult_zdvd_zgcd:
    91     "zgcd k n = 1 ==> zgcd (k * m) n dvd zgcd m n"
    92   apply (simp add: zgcd_greatest_iff)
    93   apply (rule_tac n = k in zrelprime_zdvd_zmult)
    94    prefer 2
    95    apply (simp add: mult.commute)
    96   apply (metis zgcd_1 zgcd_commute zgcd_left_commute)
    97   done
    98 
    99 lemma zgcd_zmult_cancel: "zgcd k n = 1 ==> zgcd (k * m) n = zgcd m n"
   100   by (simp add: zgcd_def nat_abs_mult_distrib gcd_mult_cancel)
   101 
   102 lemma zgcd_zgcd_zmult:
   103     "zgcd k m = 1 ==> zgcd n m = 1 ==> zgcd (k * n) m = 1"
   104   by (simp add: zgcd_zmult_cancel)
   105 
   106 lemma zdvd_iff_zgcd: "0 < m ==> m dvd n \<longleftrightarrow> zgcd n m = m"
   107   by (metis abs_of_pos dvd_mult_div_cancel zgcd_0 zgcd_commute zgcd_geq_zero zgcd_zdvd2 zgcd_zmult_eq_self)
   108 
   109 
   110 
   111 subsection \<open>Congruences\<close>
   112 
   113 lemma zcong_1 [simp]: "[a = b] (mod 1)"
   114   by (unfold zcong_def, auto)
   115 
   116 lemma zcong_refl [simp]: "[k = k] (mod m)"
   117   by (unfold zcong_def, auto)
   118 
   119 lemma zcong_sym: "[a = b] (mod m) = [b = a] (mod m)"
   120   unfolding zcong_def minus_diff_eq [of a, symmetric] dvd_minus_iff ..
   121 
   122 lemma zcong_zadd:
   123     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a + c = b + d] (mod m)"
   124   apply (unfold zcong_def)
   125   apply (rule_tac s = "(a - b) + (c - d)" in subst)
   126    apply (rule_tac [2] dvd_add, auto)
   127   done
   128 
   129 lemma zcong_zdiff:
   130     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a - c = b - d] (mod m)"
   131   apply (unfold zcong_def)
   132   apply (rule_tac s = "(a - b) - (c - d)" in subst)
   133    apply (rule_tac [2] dvd_diff, auto)
   134   done
   135 
   136 lemma zcong_trans:
   137   "[a = b] (mod m) ==> [b = c] (mod m) ==> [a = c] (mod m)"
   138 unfolding zcong_def by (auto elim!: dvdE simp add: algebra_simps)
   139 
   140 lemma zcong_zmult:
   141     "[a = b] (mod m) ==> [c = d] (mod m) ==> [a * c = b * d] (mod m)"
   142   apply (rule_tac b = "b * c" in zcong_trans)
   143    apply (unfold zcong_def)
   144   apply (metis right_diff_distrib dvd_mult mult.commute)
   145   apply (metis right_diff_distrib dvd_mult)
   146   done
   147 
   148 lemma zcong_scalar: "[a = b] (mod m) ==> [a * k = b * k] (mod m)"
   149   by (rule zcong_zmult, simp_all)
   150 
   151 lemma zcong_scalar2: "[a = b] (mod m) ==> [k * a = k * b] (mod m)"
   152   by (rule zcong_zmult, simp_all)
   153 
   154 lemma zcong_zmult_self: "[a * m = b * m] (mod m)"
   155   apply (unfold zcong_def)
   156   apply (rule dvd_diff, simp_all)
   157   done
   158 
   159 lemma zcong_square:
   160    "[| zprime p;  0 < a;  [a * a = 1] (mod p)|]
   161     ==> [a = 1] (mod p) \<or> [a = p - 1] (mod p)"
   162   apply (unfold zcong_def)
   163   apply (rule zprime_zdvd_zmult)
   164     apply (rule_tac [3] s = "a * a - 1 + p * (1 - a)" in subst)
   165      prefer 4
   166      apply (simp add: zdvd_reduce)
   167     apply (simp_all add: left_diff_distrib mult.commute right_diff_distrib)
   168   done
   169 
   170 lemma zcong_cancel:
   171   "0 \<le> m ==>
   172     zgcd k m = 1 ==> [a * k = b * k] (mod m) = [a = b] (mod m)"
   173   apply safe
   174    prefer 2
   175    apply (blast intro: zcong_scalar)
   176   apply (case_tac "b < a")
   177    prefer 2
   178    apply (subst zcong_sym)
   179    apply (unfold zcong_def)
   180    apply (rule_tac [!] zrelprime_zdvd_zmult)
   181      apply (simp_all add: left_diff_distrib)
   182   apply (subgoal_tac "m dvd (-(a * k - b * k))")
   183    apply simp
   184   apply (subst dvd_minus_iff, assumption)
   185   done
   186 
   187 lemma zcong_cancel2:
   188   "0 \<le> m ==>
   189     zgcd k m = 1 ==> [k * a = k * b] (mod m) = [a = b] (mod m)"
   190   by (simp add: mult.commute zcong_cancel)
   191 
   192 lemma zcong_zgcd_zmult_zmod:
   193   "[a = b] (mod m) ==> [a = b] (mod n) ==> zgcd m n = 1
   194     ==> [a = b] (mod m * n)"
   195   apply (auto simp add: zcong_def dvd_def)
   196   apply (subgoal_tac "m dvd n * ka")
   197    apply (subgoal_tac "m dvd ka")
   198     apply (case_tac [2] "0 \<le> ka")
   199   apply (metis dvd_mult_div_cancel dvd_refl dvd_mult_left mult.commute zrelprime_zdvd_zmult)
   200   apply (metis abs_dvd_iff abs_of_nonneg add_0 zgcd_0_left zgcd_commute zgcd_zadd_zmult zgcd_zdvd_zgcd_zmult zgcd_zmult_distrib2_abs mult_1_right mult.commute)
   201   apply (metis mult_le_0_iff  zdvd_mono zdvd_mult_cancel dvd_triv_left zero_le_mult_iff order_antisym linorder_linear order_refl mult.commute zrelprime_zdvd_zmult)
   202   apply (metis dvd_triv_left)
   203   done
   204 
   205 lemma zcong_zless_imp_eq:
   206   "0 \<le> a ==>
   207     a < m ==> 0 \<le> b ==> b < m ==> [a = b] (mod m) ==> a = b"
   208   apply (unfold zcong_def dvd_def, auto)
   209   apply (drule_tac f = "\<lambda>z. z mod m" in arg_cong)
   210   apply (metis diff_add_cancel mod_pos_pos_trivial add_0 add.commute zmod_eq_0_iff mod_add_right_eq)
   211   done
   212 
   213 lemma zcong_square_zless:
   214   "zprime p ==> 0 < a ==> a < p ==>
   215     [a * a = 1] (mod p) ==> a = 1 \<or> a = p - 1"
   216   apply (cut_tac p = p and a = a in zcong_square)
   217      apply (simp add: zprime_def)
   218     apply (auto intro: zcong_zless_imp_eq)
   219   done
   220 
   221 lemma zcong_not:
   222     "0 < a ==> a < m ==> 0 < b ==> b < a ==> \<not> [a = b] (mod m)"
   223   apply (unfold zcong_def)
   224   apply (rule zdvd_not_zless, auto)
   225   done
   226 
   227 lemma zcong_zless_0:
   228     "0 \<le> a ==> a < m ==> [a = 0] (mod m) ==> a = 0"
   229   apply (unfold zcong_def dvd_def, auto)
   230   apply (metis div_pos_pos_trivial linorder_not_less div_mult_self1_is_id)
   231   done
   232 
   233 lemma zcong_zless_unique:
   234     "0 < m ==> (\<exists>!b. 0 \<le> b \<and> b < m \<and> [a = b] (mod m))"
   235   apply auto
   236    prefer 2 apply (metis zcong_sym zcong_trans zcong_zless_imp_eq)
   237   apply (unfold zcong_def dvd_def)
   238   apply (rule_tac x = "a mod m" in exI, auto)
   239   apply (metis zmult_div_cancel)
   240   done
   241 
   242 lemma zcong_iff_lin: "([a = b] (mod m)) = (\<exists>k. b = a + m * k)"
   243   unfolding zcong_def
   244   apply (auto elim!: dvdE simp add: algebra_simps)
   245   apply (rule_tac x = "-k" in exI) apply simp
   246   done
   247 
   248 lemma zgcd_zcong_zgcd:
   249   "0 < m ==>
   250     zgcd a m = 1 ==> [a = b] (mod m) ==> zgcd b m = 1"
   251   by (auto simp add: zcong_iff_lin)
   252 
   253 lemma zcong_zmod_aux:
   254      "a - b = (m::int) * (a div m - b div m) + (a mod m - b mod m)"
   255   by(simp add: right_diff_distrib add_diff_eq eq_diff_eq ac_simps)
   256 
   257 lemma zcong_zmod: "[a = b] (mod m) = [a mod m = b mod m] (mod m)"
   258   apply (unfold zcong_def)
   259   apply (rule_tac t = "a - b" in ssubst)
   260   apply (rule_tac m = m in zcong_zmod_aux)
   261   apply (rule trans)
   262    apply (rule_tac [2] k = m and m = "a div m - b div m" in zdvd_reduce)
   263   apply (simp add: add.commute)
   264   done
   265 
   266 lemma zcong_zmod_eq: "0 < m ==> [a = b] (mod m) = (a mod m = b mod m)"
   267   apply auto
   268   apply (metis pos_mod_conj zcong_zless_imp_eq zcong_zmod)
   269   apply (metis zcong_refl zcong_zmod)
   270   done
   271 
   272 lemma zcong_zminus [iff]: "[a = b] (mod -m) = [a = b] (mod m)"
   273   by (auto simp add: zcong_def)
   274 
   275 lemma zcong_zero [iff]: "[a = b] (mod 0) = (a = b)"
   276   by (auto simp add: zcong_def)
   277 
   278 lemma "[a = b] (mod m) = (a mod m = b mod m)"
   279   apply (cases "m = 0", simp)
   280   apply (simp add: linorder_neq_iff)
   281   apply (erule disjE)  
   282    prefer 2 apply (simp add: zcong_zmod_eq)
   283   txt\<open>Remainding case: @{term "m<0"}\<close>
   284   apply (rule_tac t = m in minus_minus [THEN subst])
   285   apply (subst zcong_zminus)
   286   apply (subst zcong_zmod_eq, arith)
   287   apply (frule neg_mod_bound [of _ a], frule neg_mod_bound [of _ b]) 
   288   apply (simp add: zmod_zminus2_eq_if del: neg_mod_bound)
   289   done
   290 
   291 subsection \<open>Modulo\<close>
   292 
   293 lemma zmod_zdvd_zmod:
   294     "0 < (m::int) ==> m dvd b ==> (a mod b mod m) = (a mod m)"
   295   by (rule mod_mod_cancel) 
   296 
   297 
   298 subsection \<open>Extended GCD\<close>
   299 
   300 declare xzgcda.simps [simp del]
   301 
   302 lemma xzgcd_correct_aux1:
   303   "zgcd r' r = k --> 0 < r -->
   304     (\<exists>sn tn. xzgcda m n r' r s' s t' t = (k, sn, tn))"
   305   apply (induct m n r' r s' s t' t rule: xzgcda.induct)
   306   apply (subst zgcd_eq)
   307   apply (subst xzgcda.simps, auto)
   308   apply (case_tac "r' mod r = 0")
   309    prefer 2
   310    apply (frule_tac a = "r'" in pos_mod_sign, auto)
   311   apply (rule exI)
   312   apply (rule exI)
   313   apply (subst xzgcda.simps, auto)
   314   done
   315 
   316 lemma xzgcd_correct_aux2:
   317   "(\<exists>sn tn. xzgcda m n r' r s' s t' t = (k, sn, tn)) --> 0 < r -->
   318     zgcd r' r = k"
   319   apply (induct m n r' r s' s t' t rule: xzgcda.induct)
   320   apply (subst zgcd_eq)
   321   apply (subst xzgcda.simps)
   322   apply (auto simp add: linorder_not_le)
   323   apply (case_tac "r' mod r = 0")
   324    prefer 2
   325    apply (frule_tac a = "r'" in pos_mod_sign, auto)
   326   apply (metis prod.inject xzgcda.simps order_refl)
   327   done
   328 
   329 lemma xzgcd_correct:
   330     "0 < n ==> (zgcd m n = k) = (\<exists>s t. xzgcd m n = (k, s, t))"
   331   apply (unfold xzgcd_def)
   332   apply (rule iffI)
   333    apply (rule_tac [2] xzgcd_correct_aux2 [THEN mp, THEN mp])
   334     apply (rule xzgcd_correct_aux1 [THEN mp, THEN mp], auto)
   335   done
   336 
   337 
   338 text \<open>\medskip @{term xzgcd} linear\<close>
   339 
   340 lemma xzgcda_linear_aux1:
   341   "(a - r * b) * m + (c - r * d) * (n::int) =
   342    (a * m + c * n) - r * (b * m + d * n)"
   343   by (simp add: left_diff_distrib distrib_left mult.assoc)
   344 
   345 lemma xzgcda_linear_aux2:
   346   "r' = s' * m + t' * n ==> r = s * m + t * n
   347     ==> (r' mod r) = (s' - (r' div r) * s) * m + (t' - (r' div r) * t) * (n::int)"
   348   apply (rule trans)
   349    apply (rule_tac [2] xzgcda_linear_aux1 [symmetric])
   350   apply (simp add: eq_diff_eq mult.commute)
   351   done
   352 
   353 lemma order_le_neq_implies_less: "(x::'a::order) \<le> y ==> x \<noteq> y ==> x < y"
   354   by (rule iffD2 [OF order_less_le conjI])
   355 
   356 lemma xzgcda_linear [rule_format]:
   357   "0 < r --> xzgcda m n r' r s' s t' t = (rn, sn, tn) -->
   358     r' = s' * m + t' * n -->  r = s * m + t * n --> rn = sn * m + tn * n"
   359   apply (induct m n r' r s' s t' t rule: xzgcda.induct)
   360   apply (subst xzgcda.simps)
   361   apply (simp (no_asm))
   362   apply (rule impI)+
   363   apply (case_tac "r' mod r = 0")
   364    apply (simp add: xzgcda.simps, clarify)
   365   apply (subgoal_tac "0 < r' mod r")
   366    apply (rule_tac [2] order_le_neq_implies_less)
   367    apply (rule_tac [2] pos_mod_sign)
   368     apply (cut_tac m = m and n = n and r' = r' and r = r and s' = s' and
   369       s = s and t' = t' and t = t in xzgcda_linear_aux2, auto)
   370   done
   371 
   372 lemma xzgcd_linear:
   373     "0 < n ==> xzgcd m n = (r, s, t) ==> r = s * m + t * n"
   374   apply (unfold xzgcd_def)
   375   apply (erule xzgcda_linear, assumption, auto)
   376   done
   377 
   378 lemma zgcd_ex_linear:
   379     "0 < n ==> zgcd m n = k ==> (\<exists>s t. k = s * m + t * n)"
   380   apply (simp add: xzgcd_correct, safe)
   381   apply (rule exI)+
   382   apply (erule xzgcd_linear, auto)
   383   done
   384 
   385 lemma zcong_lineq_ex:
   386     "0 < n ==> zgcd a n = 1 ==> \<exists>x. [a * x = 1] (mod n)"
   387   apply (cut_tac m = a and n = n and k = 1 in zgcd_ex_linear, safe)
   388   apply (rule_tac x = s in exI)
   389   apply (rule_tac b = "s * a + t * n" in zcong_trans)
   390    prefer 2
   391    apply simp
   392   apply (unfold zcong_def)
   393   apply (simp (no_asm) add: mult.commute)
   394   done
   395 
   396 lemma zcong_lineq_unique:
   397   "0 < n ==>
   398     zgcd a n = 1 ==> \<exists>!x. 0 \<le> x \<and> x < n \<and> [a * x = b] (mod n)"
   399   apply auto
   400    apply (rule_tac [2] zcong_zless_imp_eq)
   401        apply (tactic \<open>stac @{context} (@{thm zcong_cancel2} RS sym) 6\<close>)
   402          apply (rule_tac [8] zcong_trans)
   403           apply (simp_all (no_asm_simp))
   404    prefer 2
   405    apply (simp add: zcong_sym)
   406   apply (cut_tac a = a and n = n in zcong_lineq_ex, auto)
   407   apply (rule_tac x = "x * b mod n" in exI, safe)
   408     apply (simp_all (no_asm_simp))
   409   apply (metis zcong_scalar zcong_zmod mod_mult_right_eq mult_1 mult.assoc)
   410   done
   411 
   412 end