src/HOL/NumberTheory/Chinese.thy
changeset 21404 eb85850d3eb7
parent 20432 07ec57376051
child 23315 df3a7e9ebadb
equal deleted inserted replaced
21403:dd58f13a8eb4 21404:eb85850d3eb7
    30 primrec
    30 primrec
    31   "funsum f i 0 = f i"
    31   "funsum f i 0 = f i"
    32   "funsum f i (Suc n) = f (Suc (i + n)) + funsum f i n"
    32   "funsum f i (Suc n) = f (Suc (i + n)) + funsum f i n"
    33 
    33 
    34 definition
    34 definition
    35   m_cond :: "nat => (nat => int) => bool"
    35   m_cond :: "nat => (nat => int) => bool" where
    36   "m_cond n mf =
    36   "m_cond n mf =
    37     ((\<forall>i. i \<le> n --> 0 < mf i) \<and>
    37     ((\<forall>i. i \<le> n --> 0 < mf i) \<and>
    38       (\<forall>i j. i \<le> n \<and> j \<le> n \<and> i \<noteq> j --> zgcd (mf i, mf j) = 1))"
    38       (\<forall>i j. i \<le> n \<and> j \<le> n \<and> i \<noteq> j --> zgcd (mf i, mf j) = 1))"
    39 
    39 
    40   km_cond :: "nat => (nat => int) => (nat => int) => bool"
    40 definition
       
    41   km_cond :: "nat => (nat => int) => (nat => int) => bool" where
    41   "km_cond n kf mf = (\<forall>i. i \<le> n --> zgcd (kf i, mf i) = 1)"
    42   "km_cond n kf mf = (\<forall>i. i \<le> n --> zgcd (kf i, mf i) = 1)"
    42 
    43 
       
    44 definition
    43   lincong_sol ::
    45   lincong_sol ::
    44     "nat => (nat => int) => (nat => int) => (nat => int) => int => bool"
    46     "nat => (nat => int) => (nat => int) => (nat => int) => int => bool" where
    45   "lincong_sol n kf bf mf x = (\<forall>i. i \<le> n --> zcong (kf i * x) (bf i) (mf i))"
    47   "lincong_sol n kf bf mf x = (\<forall>i. i \<le> n --> zcong (kf i * x) (bf i) (mf i))"
    46 
    48 
    47   mhf :: "(nat => int) => nat => nat => int"
    49 definition
       
    50   mhf :: "(nat => int) => nat => nat => int" where
    48   "mhf mf n i =
    51   "mhf mf n i =
    49     (if i = 0 then funprod mf (Suc 0) (n - Suc 0)
    52     (if i = 0 then funprod mf (Suc 0) (n - Suc 0)
    50      else if i = n then funprod mf 0 (n - Suc 0)
    53      else if i = n then funprod mf 0 (n - Suc 0)
    51      else funprod mf 0 (i - Suc 0) * funprod mf (Suc i) (n - Suc 0 - i))"
    54      else funprod mf 0 (i - Suc 0) * funprod mf (Suc i) (n - Suc 0 - i))"
    52 
    55 
       
    56 definition
    53   xilin_sol ::
    57   xilin_sol ::
    54     "nat => nat => (nat => int) => (nat => int) => (nat => int) => int"
    58     "nat => nat => (nat => int) => (nat => int) => (nat => int) => int" where
    55   "xilin_sol i n kf bf mf =
    59   "xilin_sol i n kf bf mf =
    56     (if 0 < n \<and> i \<le> n \<and> m_cond n mf \<and> km_cond n kf mf then
    60     (if 0 < n \<and> i \<le> n \<and> m_cond n mf \<and> km_cond n kf mf then
    57         (SOME x. 0 \<le> x \<and> x < mf i \<and> zcong (kf i * mhf mf n i * x) (bf i) (mf i))
    61         (SOME x. 0 \<le> x \<and> x < mf i \<and> zcong (kf i * mhf mf n i * x) (bf i) (mf i))
    58      else 0)"
    62      else 0)"
    59 
    63 
    60   x_sol :: "nat => (nat => int) => (nat => int) => (nat => int) => int"
    64 definition
       
    65   x_sol :: "nat => (nat => int) => (nat => int) => (nat => int) => int" where
    61   "x_sol n kf bf mf = funsum (\<lambda>i. xilin_sol i n kf bf mf * mhf mf n i) 0 n"
    66   "x_sol n kf bf mf = funsum (\<lambda>i. xilin_sol i n kf bf mf * mhf mf n i) 0 n"
    62 
    67 
    63 
    68 
    64 text {* \medskip @{term funprod} and @{term funsum} *}
    69 text {* \medskip @{term funprod} and @{term funsum} *}
    65 
    70