library colibrilib.stdq — module ZFactsFacts on the integers for the proof of Std.Q.gcd and Std.Q.lcm
module ZFacts6use int.Int7use int.Abs8use int.EuclideanDivision as E9use number.Divisibility10use number.Gcd11use number.Coprime12use colibrilib.zarith.Z as Z13
Bezout, by Euclid
Valid (55ms) (colibri2 9) (split_vc) (depth 1)let rec ghost bezout_nonneg (a b:int) : (u:int, v:int)16requires { 0 <= a /\ 0 <= b }17ensures { gcd a b = u * a + v * b }18variant { b }19= if b = 0 then (1, 0)20else begin21let q = E.div a b in22let r = E.mod a b in23assert { a = q * b + r /\ 0 <= r < b };24assert { gcd a b = gcd b r by gcd b a = gcd b (a - q * b) };25let (u, v) = bezout_nonneg b r in26assert { v * a = v * (q * b) + v * r };27assert { (u - v * q) * b = u * b - v * (q * b) };28(v, u - v * q)29end30Valid (509ms) (colibri2 14) (cvc5 2) (split_vc 5) (depth 3)31let ghost bezout (a b:int) : (u:int, v:int)32ensures { gcd a b = u * a + v * b }33= let (u, v) = bezout_nonneg (abs a) (abs b) in34assert { gcd a b = gcd (abs a) (abs b)35by gcd a b = gcd (-a) b /\ gcd b a = gcd (-b) a };36let u' = if a < 0 then begin37assert { abs a = - a }; assert { u * abs a = u * (- a) };38assert { u * (- a) = (- u) * a }; - u39end else u in40let v' = if b < 0 then begin41assert { abs b = - b }; assert { v * abs b = v * (- b) };42assert { v * (- b) = (- v) * b }; - v43end else v in44assert { u * abs a = u' * a };45assert { v * abs b = v' * b };46assert { gcd a b = u * abs a + v * abs b };47(u', v')48
A divisor of a coprime with b
Valid (365ms) (cvc4)let ghost coprime_div (a b c:int) : unit51requires { coprime a b }52requires { divides c a }53ensures { coprime c b }54= {proof…} assert { divides (gcd c b) a };55assert { divides (gcd c b) (gcd a b) };56assert { gcd c b >= 0 } {qed}57Valid (26ms) (colibri2)58let ghost coprime_sym (a b:int) : unit59requires { coprime a b }60ensures { coprime b a }61= ()62
gcd (c * a) b = gcd a b when c is coprime with b
Valid (31ms) (colibri2)let ghost gcd_cancel (a b c:int) : unit65requires { coprime c b }66ensures { gcd (c * a) b = gcd a b }67= {proof…} assert { coprime b c };68assert { gcd b (c * a) = gcd b a } {qed}69
coprime c (a * b) from coprime c a and coprime c b
Valid (34ms) (colibri2)let ghost coprime_mul (a b c:int) : unit72requires { coprime c a }73requires { coprime c b }74ensures { coprime c (a * b) }75= {proof…} assert { gcd c (a * b) = gcd c b } {qed}76
|a * b| = lcm a b * gcd a b
Valid (129ms) (colibri2 4) (cvc5 2) (split_vc) (depth 1)let ghost lcm_gcd (a b:int) : unit79ensures { abs (a * b) = Z.lcm a b * gcd a b }80ensures { 0 <= Z.lcm a b }81= {proof…} if a <> 0 && b <> 0 then begin82let g = gcd a b in83assert { 0 < g by g <> 0 };84let a' = any int ensures { a = g * result } in85assert { abs (a * b) = g * abs (a' * b) };86assert { E.div (g * abs (a' * b)) g = abs (a' * b) }87end {qed}88
a and b divide lcm a b
Valid (267ms) (colibri2 9) (cvc5 6) (split_vc 3) (depth 2)let ghost lcm_multiple (a b:int) : unit91ensures { divides a (Z.lcm a b) /\ divides b (Z.lcm a b) }92= {proof…} if a <> 0 && b <> 0 then begin93let g = gcd a b in94assert { 0 < g by g <> 0 };95let a' = any int ensures { a = g * result } in96let b' = any int ensures { b = g * result } in97assert { abs (a * b) = g * abs (a' * b) };98assert { Z.lcm a b = abs (a' * b) by E.div (g * abs (a' * b)) g = abs (a' * b) };99assert { abs (a' * b) = abs (a * b') };100if a' * b < 0 then assert { abs (a' * b) = (- a') * b }101else assert { abs (a' * b) = a' * b };102assert { divides b (abs (a' * b)) };103if a * b' < 0 then assert { abs (a * b') = (- b') * a }104else assert { abs (a * b') = b' * a };105assert { divides a (abs (a * b')) }106end {qed}107
A common multiple of a and b is a multiple of lcm a b
Valid (4.2s) (colibri2 19) (cvc5 6) (split_vc 5) (depth 3)let ghost lcm_least (a b r:int) : unit110requires { divides a r /\ divides b r }111ensures { divides (Z.lcm a b) r }112= {proof…} if a <> 0 && b <> 0 then begin113let g = gcd a b in114assert { 0 < g by g <> 0 };115assert { divides g a /\ divides g b };116let a' = any int ensures { a = g * result } in117let b' = any int ensures { b = g * result } in118assert { gcd (g * a') (g * b') = g * gcd a' b' };119assert { coprime b' a' };120let p = any int ensures { r = result * a } in121assert { divides (g * b') (g * (a' * p)) };122let w = any int ensures { g * (a' * p) = result * (g * b') } in123assert { g * (a' * p - w * b') = 0 };124assert { a' * p = w * b' };125assert { divides b' (a' * p) };126assert { divides b' p };127let q = any int ensures { p = result * b' } in128assert { r = q * (g * a' * b') };129assert { abs (a * b) = g * abs (a' * b) };130assert { Z.lcm a b = abs (a' * b) by E.div (g * abs (a' * b)) g = abs (a' * b) };131assert { abs (a' * b) = abs (g * a' * b') };132assert { divides (g * a' * b') r }133end else begin134assert { r = 0 }135end {qed}136
The decomposition d1 = g * x, d2 = g * y with g = gcd d1 d2 and the least common multiple g * x * y
Valid (116ms) (colibri2 8) (cvc4) (cvc5 2) (split_vc) (depth 1)let ghost lcm_decomp (d1 d2:int) : (x:int, y:int)140requires { 0 < d1 /\ 0 < d2 }141ensures { d1 = gcd d1 d2 * x /\ d2 = gcd d1 d2 * y }142ensures { 0 < x /\ 0 < y /\ coprime x y }143ensures { Z.lcm d1 d2 = gcd d1 d2 * x * y }144= {proof…} let g = gcd d1 d2 in145assert { 0 < g by g <> 0 };146let x = any int ensures { d1 = g * result } in147let y = any int ensures { d2 = g * result } in148assert { 0 < x /\ 0 < y };149assert { gcd (g * x) (g * y) = g * gcd x y };150assert { gcd x y = 1 };151assert { abs (d1 * d2) = (g * x * y) * g };152assert { E.div (abs (d1 * d2)) g = g * x * y };153(x, y) {qed}154end155