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 |