src/ZF/ex/Primes.thy
changeset 61798 27f3c10b0b50
parent 60770 240563fbf41d
child 65449 c82e63b11b8b
equal deleted inserted replaced
61797:458b4e3720ab 61798:27f3c10b0b50
    10 definition
    10 definition
    11   divides :: "[i,i]=>o"              (infixl "dvd" 50)  where
    11   divides :: "[i,i]=>o"              (infixl "dvd" 50)  where
    12     "m dvd n == m \<in> nat & n \<in> nat & (\<exists>k \<in> nat. n = m#*k)"
    12     "m dvd n == m \<in> nat & n \<in> nat & (\<exists>k \<in> nat. n = m#*k)"
    13 
    13 
    14 definition
    14 definition
    15   is_gcd  :: "[i,i,i]=>o"     --\<open>definition of great common divisor\<close>  where
    15   is_gcd  :: "[i,i,i]=>o"     \<comment>\<open>definition of great common divisor\<close>  where
    16     "is_gcd(p,m,n) == ((p dvd m) & (p dvd n))   &
    16     "is_gcd(p,m,n) == ((p dvd m) & (p dvd n))   &
    17                        (\<forall>d\<in>nat. (d dvd m) & (d dvd n) \<longrightarrow> d dvd p)"
    17                        (\<forall>d\<in>nat. (d dvd m) & (d dvd n) \<longrightarrow> d dvd p)"
    18 
    18 
    19 definition
    19 definition
    20   gcd     :: "[i,i]=>i"       --\<open>Euclid's algorithm for the gcd\<close>  where
    20   gcd     :: "[i,i]=>i"       \<comment>\<open>Euclid's algorithm for the gcd\<close>  where
    21     "gcd(m,n) == transrec(natify(n),
    21     "gcd(m,n) == transrec(natify(n),
    22                         %n f. \<lambda>m \<in> nat.
    22                         %n f. \<lambda>m \<in> nat.
    23                                 if n=0 then m else f`(m mod n)`n) ` natify(m)"
    23                                 if n=0 then m else f`(m mod n)`n) ` natify(m)"
    24 
    24 
    25 definition
    25 definition
    26   coprime :: "[i,i]=>o"       --\<open>the coprime relation\<close>  where
    26   coprime :: "[i,i]=>o"       \<comment>\<open>the coprime relation\<close>  where
    27     "coprime(m,n) == gcd(m,n) = 1"
    27     "coprime(m,n) == gcd(m,n) = 1"
    28   
    28   
    29 definition
    29 definition
    30   prime   :: i                --\<open>the set of prime numbers\<close>  where
    30   prime   :: i                \<comment>\<open>the set of prime numbers\<close>  where
    31    "prime == {p \<in> nat. 1<p & (\<forall>m \<in> nat. m dvd p \<longrightarrow> m=1 | m=p)}"
    31    "prime == {p \<in> nat. 1<p & (\<forall>m \<in> nat. m dvd p \<longrightarrow> m=1 | m=p)}"
    32 
    32 
    33 
    33 
    34 subsection\<open>The Divides Relation\<close>
    34 subsection\<open>The Divides Relation\<close>
    35 
    35