Common — library colibrilib.q_model — module ZModel

A model of the axioms of q.Z: prime_to_one_another is gcd a b = 1, gcd and lcm are those of the integers

341
module ZModel
342
use int.Int
343
use int.Abs as IA
344
use int.EuclideanDivision as E
345
use number.Divisibility as ND
346
use number.Gcd as NG
347
use number.Coprime as NC
348
349
predicate
ddivisible_using
(a:int) (b:int) (c:int) = a = c * b
350
351
predicate
coprime
(a b:int) = NG.gcd a b = 1
352
353
function
lcm
(a b:int) : int =
354
if a = 0 \/ b = 0 then 0 else E.div (IA.abs (a * b)) (NG.gcd a b)
355
Valid (728ms) (colibri2)
356
let ghost
mul
(a m b n: int) : (q:int)
357
requires { coprime a b }
358
requires { a * m = b * n }
359
ensures { ddivisible_using m b q }
360
ensures { ddivisible_using n a q }
361
= assert { NC.coprime b a by NG.gcd b a = NG.gcd a b };
362
assert { ND.divides b (a * m) };
363
assert { ND.divides b m };
364
let q = any int ensures { m = result * b } in
365
if b = 0 then begin
366
assert { NG.gcd a 0 = IA.abs a };
367
assert { m = 0 };
368
a * n
369
end else begin
370
assert { b * (a * q - n) = 0 };
371
q
372
end
373
Valid (59ms) (cvc4)
374
let lemma
prime_div
(a b c:int)
375
requires { coprime a b }
376
requires { ND.divides c a }
377
ensures { coprime c b }
378
= assert { ND.divides (NG.gcd c b) a };
379
assert { ND.divides (NG.gcd c b) (NG.gcd a b) }
380
Valid (403ms) (colibri2 5) (cvc5 2) (split_vc) (depth 1)
381
let lemma
lcm_divides_prod
(a b:int)
382
ensures { ND.divides (lcm a b) (a * b) }
383
= if a <> 0 && b <> 0 then begin
384
let g = NG.gcd a b in
385
assert { 0 < g by g <> 0 };
386
let a' = any int ensures { a = g * result } in
387
assert { IA.abs (a * b) = g * IA.abs (a' * b) };
388
assert { lcm a b = IA.abs (a' * b)
389
by E.div (g * IA.abs (a' * b)) g = IA.abs (a' * b) };
390
if a' * b < 0 then assert { a * b = (- g) * (IA.abs (a' * b)) }
391
else assert { a * b = g * (IA.abs (a' * b)) }
392
end
393
Valid (30ms) (colibri2)
394
let lemma
prime_mul
(a b c:int)
395
requires { coprime a b }
396
requires { coprime a c }
397
ensures { coprime a (b * c) }
398
= assert { NC.coprime a b };
399
assert { NG.gcd a (b * c) = NG.gcd a c }
400
Valid (41ms) (colibri2)
401
let lemma
gcd3
(a b c:int)
402
requires { coprime a b }
403
requires { coprime a c }
404
ensures { coprime a (lcm b c) }
405
= prime_mul a b c;
406
assert { coprime (b * c) a by NG.gcd (b * c) a = NG.gcd a (b * c) };
407
prime_div (b * c) a (lcm b c);
408
assert { NG.gcd a (lcm b c) = NG.gcd (lcm b c) a }
409
Valid (34ms) (colibri2)
410
let lemma
gcd4
(a b c:int)
411
requires { coprime a b }
412
requires { coprime c b }
413
ensures { coprime (lcm a c) b }
414
= assert { coprime b a by NG.gcd b a = NG.gcd a b };
415
assert { coprime b c by NG.gcd b c = NG.gcd c b };
416
gcd3 b a c;
417
assert { NG.gcd (lcm a c) b = NG.gcd b (lcm a c) }
418
419
clone 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
}
with
420
function gcd = NG.gcd, function lcm = lcm,
421
predicate prime_to_one_another = coprime,
422
val prime_to_one_another_mul = mul,
423
lemma prime_to_one_another_one, lemma GCD1, lemma GCD2, lemma GCD3,
424
lemma GCD4, lemma GCD_comm
425
end