Common — library colibrilib.q — module Z
10
module Z
11
12
use int.Int
13
14
val
fdiv
(a:int) (b:int) : (d:int)
15
requires { 0 < b }
16
ensures { 0 <= a - d*b < b }
17
18
val
cdiv
(a:int) (b:int) : (d:int)
19
requires { 0 < b }
20
ensures { 0 <= d*b - a < b }
21
22
predicate
ddivisible_using
(a:int) (b:int) (c:int) =
23
a = c * b
24
25
predicate
ddivisible
(a:int) (b:int) =
26
exists d. ddivisible_using a b d
27
28
val
divisible
(a:int) (b:int) : (r:bool,ghost d: int)
29
ensures { (not r) -> forall c. not (ddivisible_using a b c) }
30
ensures { r -> ddivisible_using a b d }
31
32
function
gcd
(a b:int): int
33
34
val
gcd
(a b:int) : (c:int,ghost a':int,ghost b':int)
35
ensures { gcd a b = c }
36
ensures { c * a' = a }
37
ensures { c * b' = b }
38
ensures { forall r d. ddivisible_using r a d -> ddivisible_using r c (d*a')}
39
ensures { forall r d. ddivisible_using r b d -> ddivisible_using r c (d*b')}
40
41
function
lcm
(a b:int): int
42
43
val
lcm
(a b:int) : (c:int, ghost a':int, ghost b':int, ghost fa : int -> int)
44
requires { a <> 0 } requires { b <> 0 }
45
ensures { c <> 0 } ensures { lcm a b = c }
46
ensures { c = a' * a } ensures { c = b' * b }
47
ensures { forall r da db. ddivisible_using r a da -> ddivisible_using r b db ->
48
(da = a' * fa da /\ ddivisible_using r c (fa da)) }
49
ensures { forall r da. ddivisible_using a r da -> ddivisible_using c r (da*a') }

gcd a b = 1: the axioms below are satisfied by this definition (q_model.ZModel)

54
predicate
prime_to_one_another
(a b:int)
55
56
axiom
prime_to_one_another_one
: prime_to_one_another 1 1
57
58
val ghost
prime_to_one_another_mul
(a m b n: int) : (q:int)
59
requires { prime_to_one_another a b }
60
requires { a * m = b * n } (* a * b * q = b * a * q *)
61
ensures { ddivisible_using m b q (* m = b * q *) }
62
ensures { ddivisible_using n a q (* n = a * q *) }
63
64
axiom
GCD1
: forall a b c. prime_to_one_another a b -> prime_to_one_another (gcd a c) b
65
axiom
GCD2
: forall a b c. prime_to_one_another a b -> prime_to_one_another a (gcd b c)
66
axiom
GCD3
: forall a b c. prime_to_one_another a b -> prime_to_one_another a c
67
-> prime_to_one_another a (lcm b c)
68
axiom
GCD4
: forall a b c. prime_to_one_another a b -> prime_to_one_another c b
69
-> prime_to_one_another (lcm a c) b
70
axiom
GCD_comm
: forall a b. gcd a b = gcd b a
71
72
end