library colibrilib.q — module Zmodule Z1011use int.Int1213val fdiv (a:int) (b:int) : (d:int)14requires { 0 < b }15ensures { 0 <= a - d*b < b }1617val cdiv (a:int) (b:int) : (d:int)18requires { 0 < b }19ensures { 0 <= d*b - a < b }2021predicate ddivisible_using (a:int) (b:int) (c:int) =22a = c * b2324predicate ddivisible (a:int) (b:int) =25exists d. ddivisible_using a b d2627val divisible (a:int) (b:int) : (r:bool,ghost d: int)28ensures { (not r) -> forall c. not (ddivisible_using a b c) }29ensures { r -> ddivisible_using a b d }3031function gcd (a b:int): int3233val gcd (a b:int) : (c:int,ghost a':int,ghost b':int)34ensures { gcd a b = c }35ensures { c * a' = a }36ensures { c * b' = b }37ensures { forall r d. ddivisible_using r a d -> ddivisible_using r c (d*a')}38ensures { forall r d. ddivisible_using r b d -> ddivisible_using r c (d*b')}3940function lcm (a b:int): int4142val lcm (a b:int) : (c:int, ghost a':int, ghost b':int, ghost fa : int -> int)43requires { a <> 0 } requires { b <> 0 }44ensures { c <> 0 } ensures { lcm a b = c }45ensures { c = a' * a } ensures { c = b' * b }46ensures { forall r da db. ddivisible_using r a da -> ddivisible_using r b db ->47(da = a' * fa da /\ ddivisible_using r c (fa da)) }48ensures { forall r da. ddivisible_using a r da -> ddivisible_using c r (da*a') }49
gcd a b = 1: the axioms below are satisfied by this definition (q_model.ZModel)
predicate prime_to_one_another (a b:int)5455axiom prime_to_one_another_one: prime_to_one_another 1 15657val ghost prime_to_one_another_mul (a m b n: int) : (q:int)58requires { prime_to_one_another a b }59requires { a * m = b * n } (* a * b * q = b * a * q *)60ensures { ddivisible_using m b q (* m = b * q *) }61ensures { ddivisible_using n a q (* n = a * q *) }6263axiom GCD1: forall a b c. prime_to_one_another a b -> prime_to_one_another (gcd a c) b64axiom GCD2: forall a b c. prime_to_one_another a b -> prime_to_one_another a (gcd b c)65axiom GCD3: forall a b c. prime_to_one_another a b -> prime_to_one_another a c66-> prime_to_one_another a (lcm b c)67axiom GCD4: forall a b c. prime_to_one_another a b -> prime_to_one_another c b68-> prime_to_one_another (lcm a c) b69axiom GCD_comm: forall a b. gcd a b = gcd b a7071end72