src/HOL/NumberTheory/Quadratic_Reciprocity.thy
changeset 21404 eb85850d3eb7
parent 21288 2c7d3d120418
child 23365 f31794033ae1
equal deleted inserted replaced
21403:dd58f13a8eb4 21404:eb85850d3eb7
   166   assumes q_g_2: "2 < q"
   166   assumes q_g_2: "2 < q"
   167   assumes p_neq_q:      "p \<noteq> q"
   167   assumes p_neq_q:      "p \<noteq> q"
   168 begin
   168 begin
   169 
   169 
   170 definition
   170 definition
   171   P_set :: "int set"
   171   P_set :: "int set" where
   172   "P_set = {x. 0 < x & x \<le> ((p - 1) div 2) }"
   172   "P_set = {x. 0 < x & x \<le> ((p - 1) div 2) }"
   173 
   173 
   174   Q_set :: "int set"
   174 definition
       
   175   Q_set :: "int set" where
   175   "Q_set = {x. 0 < x & x \<le> ((q - 1) div 2) }"
   176   "Q_set = {x. 0 < x & x \<le> ((q - 1) div 2) }"
   176   
   177   
   177   S :: "(int * int) set"
   178 definition
       
   179   S :: "(int * int) set" where
   178   "S = P_set <*> Q_set"
   180   "S = P_set <*> Q_set"
   179 
   181 
   180   S1 :: "(int * int) set"
   182 definition
       
   183   S1 :: "(int * int) set" where
   181   "S1 = { (x, y). (x, y):S & ((p * y) < (q * x)) }"
   184   "S1 = { (x, y). (x, y):S & ((p * y) < (q * x)) }"
   182 
   185 
   183   S2 :: "(int * int) set"
   186 definition
       
   187   S2 :: "(int * int) set" where
   184   "S2 = { (x, y). (x, y):S & ((q * x) < (p * y)) }"
   188   "S2 = { (x, y). (x, y):S & ((q * x) < (p * y)) }"
   185 
   189 
   186   f1 :: "int => (int * int) set"
   190 definition
       
   191   f1 :: "int => (int * int) set" where
   187   "f1 j = { (j1, y). (j1, y):S & j1 = j & (y \<le> (q * j) div p) }"
   192   "f1 j = { (j1, y). (j1, y):S & j1 = j & (y \<le> (q * j) div p) }"
   188 
   193 
   189   f2 :: "int => (int * int) set"
   194 definition
       
   195   f2 :: "int => (int * int) set" where
   190   "f2 j = { (x, j1). (x, j1):S & j1 = j & (x \<le> (p * j) div q) }"
   196   "f2 j = { (x, j1). (x, j1):S & j1 = j & (x \<le> (p * j) div q) }"
   191 
   197 
   192 lemma p_fact: "0 < (p - 1) div 2"
   198 lemma p_fact: "0 < (p - 1) div 2"
   193 proof -
   199 proof -
   194   from p_g_2 have "2 \<le> p - 1" by arith
   200   from p_g_2 have "2 \<le> p - 1" by arith