library colibrilib.q_model — module ZModelA model of the axioms of q.Z: prime_to_one_another is gcd a b = 1, gcd and lcm are those of the integers
module ZModel341use int.Int342use int.Abs as IA343use int.EuclideanDivision as E344use number.Divisibility as ND345use number.Gcd as NG346use number.Coprime as NC347348predicate ddivisible_using (a:int) (b:int) (c:int) = a = c * b349350predicate coprime (a b:int) = NG.gcd a b = 1351352function lcm (a b:int) : int =353if a = 0 \/ b = 0 then 0 else E.div (IA.abs (a * b)) (NG.gcd a b)354Valid (728ms) (colibri2)355let ghost mul (a m b n: int) : (q:int)356requires { coprime a b }357requires { a * m = b * n }358ensures { ddivisible_using m b q }359ensures { ddivisible_using n a q }360= assert { NC.coprime b a by NG.gcd b a = NG.gcd a b };361assert { ND.divides b (a * m) };362assert { ND.divides b m };363let q = any int ensures { m = result * b } in364if b = 0 then begin365assert { NG.gcd a 0 = IA.abs a };366assert { m = 0 };367a * n368end else begin369assert { b * (a * q - n) = 0 };370q371end372Valid (59ms) (cvc4)373let lemma prime_div (a b c:int)374requires { coprime a b }375requires { ND.divides c a }376ensures { coprime c b }377= assert { ND.divides (NG.gcd c b) a };378assert { ND.divides (NG.gcd c b) (NG.gcd a b) }379Valid (403ms) (colibri2 5) (cvc5 2) (split_vc) (depth 1)380let lemma lcm_divides_prod (a b:int)381ensures { ND.divides (lcm a b) (a * b) }382= if a <> 0 && b <> 0 then begin383let g = NG.gcd a b in384assert { 0 < g by g <> 0 };385let a' = any int ensures { a = g * result } in386assert { IA.abs (a * b) = g * IA.abs (a' * b) };387assert { lcm a b = IA.abs (a' * b)388by E.div (g * IA.abs (a' * b)) g = IA.abs (a' * b) };389if a' * b < 0 then assert { a * b = (- g) * (IA.abs (a' * b)) }390else assert { a * b = g * (IA.abs (a' * b)) }391end392Valid (30ms) (colibri2)393let lemma prime_mul (a b c:int)394requires { coprime a b }395requires { coprime a c }396ensures { coprime a (b * c) }397= assert { NC.coprime a b };398assert { NG.gcd a (b * c) = NG.gcd a c }399Valid (41ms) (colibri2)400let lemma gcd3 (a b c:int)401requires { coprime a b }402requires { coprime a c }403ensures { coprime a (lcm b c) }404= prime_mul a b c;405assert { coprime (b * c) a by NG.gcd (b * c) a = NG.gcd a (b * c) };406prime_div (b * c) a (lcm b c);407assert { NG.gcd a (lcm b c) = NG.gcd (lcm b c) a }408Valid (34ms) (colibri2)409let lemma gcd4 (a b c:int)410requires { coprime a b }411requires { coprime c b }412ensures { coprime (lcm a c) b }413= assert { coprime b a by NG.gcd b a = NG.gcd a b };414assert { coprime b c by NG.gcd b c = NG.gcd c b };415gcd3 b a c;416assert { NG.gcd (lcm a c) b = NG.gcd b (lcm a c) }417418clone colibrilib.q.Z {… begin (* cloned colibrilib.q.Z *) val Z.fdiv int int : int val Z.cdiv int int : int predicate Z.ddivisible_using int int int predicate Z.ddivisible int int val Z.divisible int int : bool,int val Z.gcd int int : int,int,int val Z.lcm int int : int,int,int,(int -> int) Valid (80ms) (cvc5) lemma Z.prime_to_one_another_one Valid (36ms) (colibri2) lemma Z.GCD1 Valid (678ms) (cvc5) lemma Z.GCD2 Valid (32ms) (colibri2) lemma Z.GCD3 Valid (34ms) (colibri2) lemma Z.GCD4 Valid (32ms) (colibri2) lemma Z.GCD_comm end } with419function gcd = NG.gcd, function lcm = lcm,420predicate prime_to_one_another = coprime,421val prime_to_one_another_mul = mul,422lemma prime_to_one_another_one, lemma GCD1, lemma GCD2, lemma GCD3,423lemma GCD4, lemma GCD_comm424end425