src/HOL/NumberTheory/Residues.thy
author haftmann
Wed Sep 26 20:27:55 2007 +0200 (2007-09-26)
changeset 24728 e2b3a1065676
parent 21404 eb85850d3eb7
child 29948 cdf12a1cb963
permissions -rw-r--r--
moved Finite_Set before Datatype
     1 (*  Title:      HOL/Quadratic_Reciprocity/Residues.thy
     2     ID:         $Id$
     3     Authors:    Jeremy Avigad, David Gray, and Adam Kramer
     4 *)
     5 
     6 header {* Residue Sets *}
     7 
     8 theory Residues imports Int2 begin
     9 
    10 text {*
    11   \medskip Define the residue of a set, the standard residue,
    12   quadratic residues, and prove some basic properties. *}
    13 
    14 definition
    15   ResSet      :: "int => int set => bool" where
    16   "ResSet m X = (\<forall>y1 y2. (y1 \<in> X & y2 \<in> X & [y1 = y2] (mod m) --> y1 = y2))"
    17 
    18 definition
    19   StandardRes :: "int => int => int" where
    20   "StandardRes m x = x mod m"
    21 
    22 definition
    23   QuadRes     :: "int => int => bool" where
    24   "QuadRes m x = (\<exists>y. ([(y ^ 2) = x] (mod m)))"
    25 
    26 definition
    27   Legendre    :: "int => int => int" where
    28   "Legendre a p = (if ([a = 0] (mod p)) then 0
    29                      else if (QuadRes p a) then 1
    30                      else -1)"
    31 
    32 definition
    33   SR          :: "int => int set" where
    34   "SR p = {x. (0 \<le> x) & (x < p)}"
    35 
    36 definition
    37   SRStar      :: "int => int set" where
    38   "SRStar p = {x. (0 < x) & (x < p)}"
    39 
    40 
    41 subsection {* Some useful properties of StandardRes *}
    42 
    43 lemma StandardRes_prop1: "[x = StandardRes m x] (mod m)"
    44   by (auto simp add: StandardRes_def zcong_zmod)
    45 
    46 lemma StandardRes_prop2: "0 < m ==> (StandardRes m x1 = StandardRes m x2)
    47       = ([x1 = x2] (mod m))"
    48   by (auto simp add: StandardRes_def zcong_zmod_eq)
    49 
    50 lemma StandardRes_prop3: "(~[x = 0] (mod p)) = (~(StandardRes p x = 0))"
    51   by (auto simp add: StandardRes_def zcong_def zdvd_iff_zmod_eq_0)
    52 
    53 lemma StandardRes_prop4: "2 < m 
    54      ==> [StandardRes m x * StandardRes m y = (x * y)] (mod m)"
    55   by (auto simp add: StandardRes_def zcong_zmod_eq 
    56                      zmod_zmult_distrib [of x y m])
    57 
    58 lemma StandardRes_lbound: "0 < p ==> 0 \<le> StandardRes p x"
    59   by (auto simp add: StandardRes_def pos_mod_sign)
    60 
    61 lemma StandardRes_ubound: "0 < p ==> StandardRes p x < p"
    62   by (auto simp add: StandardRes_def pos_mod_bound)
    63 
    64 lemma StandardRes_eq_zcong: 
    65    "(StandardRes m x = 0) = ([x = 0](mod m))"
    66   by (auto simp add: StandardRes_def zcong_eq_zdvd_prop dvd_def) 
    67 
    68 
    69 subsection {* Relations between StandardRes, SRStar, and SR *}
    70 
    71 lemma SRStar_SR_prop: "x \<in> SRStar p ==> x \<in> SR p"
    72   by (auto simp add: SRStar_def SR_def)
    73 
    74 lemma StandardRes_SR_prop: "x \<in> SR p ==> StandardRes p x = x"
    75   by (auto simp add: SR_def StandardRes_def mod_pos_pos_trivial)
    76 
    77 lemma StandardRes_SRStar_prop1: "2 < p ==> (StandardRes p x \<in> SRStar p) 
    78      = (~[x = 0] (mod p))"
    79   apply (auto simp add: StandardRes_prop3 StandardRes_def
    80                         SRStar_def pos_mod_bound)
    81   apply (subgoal_tac "0 < p")
    82   apply (drule_tac a = x in pos_mod_sign, arith, simp)
    83   done
    84 
    85 lemma StandardRes_SRStar_prop1a: "x \<in> SRStar p ==> ~([x = 0] (mod p))"
    86   by (auto simp add: SRStar_def zcong_def zdvd_not_zless)
    87 
    88 lemma StandardRes_SRStar_prop2: "[| 2 < p; zprime p; x \<in> SRStar p |] 
    89      ==> StandardRes p (MultInv p x) \<in> SRStar p"
    90   apply (frule_tac x = "(MultInv p x)" in StandardRes_SRStar_prop1, simp)
    91   apply (rule MultInv_prop3)
    92   apply (auto simp add: SRStar_def zcong_def zdvd_not_zless)
    93   done
    94 
    95 lemma StandardRes_SRStar_prop3: "x \<in> SRStar p ==> StandardRes p x = x"
    96   by (auto simp add: SRStar_SR_prop StandardRes_SR_prop)
    97 
    98 lemma StandardRes_SRStar_prop4: "[| zprime p; 2 < p; x \<in> SRStar p |] 
    99      ==> StandardRes p x \<in> SRStar p"
   100   by (frule StandardRes_SRStar_prop3, auto)
   101 
   102 lemma SRStar_mult_prop1: "[| zprime p; 2 < p; x \<in> SRStar p; y \<in> SRStar p|] 
   103      ==> (StandardRes p (x * y)):SRStar p"
   104   apply (frule_tac x = x in StandardRes_SRStar_prop4, auto)
   105   apply (frule_tac x = y in StandardRes_SRStar_prop4, auto)
   106   apply (auto simp add: StandardRes_SRStar_prop1 zcong_zmult_prop3)
   107   done
   108 
   109 lemma SRStar_mult_prop2: "[| zprime p; 2 < p; ~([a = 0](mod p)); 
   110      x \<in> SRStar p |] 
   111      ==> StandardRes p (a * MultInv p x) \<in> SRStar p"
   112   apply (frule_tac x = x in StandardRes_SRStar_prop2, auto)
   113   apply (frule_tac x = "MultInv p x" in StandardRes_SRStar_prop1)
   114   apply (auto simp add: StandardRes_SRStar_prop1 zcong_zmult_prop3)
   115   done
   116 
   117 lemma SRStar_card: "2 < p ==> int(card(SRStar p)) = p - 1"
   118   by (auto simp add: SRStar_def int_card_bdd_int_set_l_l)
   119 
   120 lemma SRStar_finite: "2 < p ==> finite( SRStar p)"
   121   by (auto simp add: SRStar_def bdd_int_set_l_l_finite)
   122 
   123 
   124 subsection {* Properties relating ResSets with StandardRes *}
   125 
   126 lemma aux: "x mod m = y mod m ==> [x = y] (mod m)"
   127   apply (subgoal_tac "x = y ==> [x = y](mod m)")
   128   apply (subgoal_tac "[x mod m = y mod m] (mod m) ==> [x = y] (mod m)")
   129   apply (auto simp add: zcong_zmod [of x y m])
   130   done
   131 
   132 lemma StandardRes_inj_on_ResSet: "ResSet m X ==> (inj_on (StandardRes m) X)"
   133   apply (auto simp add: ResSet_def StandardRes_def inj_on_def)
   134   apply (drule_tac m = m in aux, auto)
   135   done
   136 
   137 lemma StandardRes_Sum: "[| finite X; 0 < m |] 
   138      ==> [setsum f X = setsum (StandardRes m o f) X](mod m)" 
   139   apply (rule_tac F = X in finite_induct)
   140   apply (auto intro!: zcong_zadd simp add: StandardRes_prop1)
   141   done
   142 
   143 lemma SR_pos: "0 < m ==> (StandardRes m ` X) \<subseteq> {x. 0 \<le> x & x < m}"
   144   by (auto simp add: StandardRes_ubound StandardRes_lbound)
   145 
   146 lemma ResSet_finite: "0 < m ==> ResSet m X ==> finite X"
   147   apply (rule_tac f = "StandardRes m" in finite_imageD) 
   148   apply (rule_tac B = "{x. (0 :: int) \<le> x & x < m}" in finite_subset)
   149   apply (auto simp add: StandardRes_inj_on_ResSet bdd_int_set_l_finite SR_pos)
   150   done
   151 
   152 lemma mod_mod_is_mod: "[x = x mod m](mod m)"
   153   by (auto simp add: zcong_zmod)
   154 
   155 lemma StandardRes_prod: "[| finite X; 0 < m |] 
   156      ==> [setprod f X = setprod (StandardRes m o f) X] (mod m)"
   157   apply (rule_tac F = X in finite_induct)
   158   apply (auto intro!: zcong_zmult simp add: StandardRes_prop1)
   159   done
   160 
   161 lemma ResSet_image:
   162   "[| 0 < m; ResSet m A; \<forall>x \<in> A. \<forall>y \<in> A. ([f x = f y](mod m) --> x = y) |] ==>
   163     ResSet m (f ` A)"
   164   by (auto simp add: ResSet_def)
   165 
   166 
   167 subsection {* Property for SRStar *}
   168 
   169 lemma ResSet_SRStar_prop: "ResSet p (SRStar p)"
   170   by (auto simp add: SRStar_def ResSet_def zcong_zless_imp_eq)
   171 
   172 end