Common — library colibrilib.stdq — module ZFacts

Facts on the integers for the proof of Std.Q.gcd and Std.Q.lcm

6
module ZFacts
7
use int.Int
8
use int.Abs
9
use int.EuclideanDivision as E
10
use number.Divisibility
11
use number.Gcd
12
use number.Coprime
13
use colibrilib.zarith.Z as Z

Bezout, by Euclid

  Valid (55ms) (colibri2 9) (split_vc) (depth 1)
16
let rec ghost
bezout_nonneg
(a b:int) : (u:int, v:int)
17
requires { 0 <= a /\ 0 <= b }
18
ensures { gcd a b = u * a + v * b }
19
variant { b }
20
= if b = 0 then (1, 0)
21
else begin
22
let q = E.div a b in
23
let r = E.mod a b in
24
assert { a = q * b + r /\ 0 <= r < b };
25
assert { gcd a b = gcd b r by gcd b a = gcd b (a - q * b) };
26
let (u, v) = bezout_nonneg b r in
27
assert { v * a = v * (q * b) + v * r };
28
assert { (u - v * q) * b = u * b - v * (q * b) };
29
(v, u - v * q)
30
end
31
Valid (509ms) (colibri2 14) (cvc5 2) (split_vc 5) (depth 3)
32
let ghost
bezout
(a b:int) : (u:int, v:int)
33
ensures { gcd a b = u * a + v * b }
34
= let (u, v) = bezout_nonneg (abs a) (abs b) in
35
assert { gcd a b = gcd (abs a) (abs b)
36
by gcd a b = gcd (-a) b /\ gcd b a = gcd (-b) a };
37
let u' = if a < 0 then begin
38
assert { abs a = - a }; assert { u * abs a = u * (- a) };
39
assert { u * (- a) = (- u) * a }; - u
40
end else u in
41
let v' = if b < 0 then begin
42
assert { abs b = - b }; assert { v * abs b = v * (- b) };
43
assert { v * (- b) = (- v) * b }; - v
44
end else v in
45
assert { u * abs a = u' * a };
46
assert { v * abs b = v' * b };
47
assert { gcd a b = u * abs a + v * abs b };
48
(u', v')

A divisor of a coprime with b

  Valid (365ms) (cvc4)
51
let ghost
coprime_div
(a b c:int) : unit
52
requires { coprime a b }
53
requires { divides c a }
54
ensures { coprime c b }
55
= {proof…} assert { divides (gcd c b) a };
56
assert { divides (gcd c b) (gcd a b) };
57
assert { gcd c b >= 0 } {qed}
58
Valid (26ms) (colibri2)
59
let ghost
coprime_sym
(a b:int) : unit
60
requires { coprime a b }
61
ensures { coprime b a }
62
= ()

gcd (c * a) b = gcd a b when c is coprime with b

  Valid (31ms) (colibri2)
65
let ghost
gcd_cancel
(a b c:int) : unit
66
requires { coprime c b }
67
ensures { gcd (c * a) b = gcd a b }
68
= {proof…} assert { coprime b c };
69
assert { gcd b (c * a) = gcd b a } {qed}

coprime c (a * b) from coprime c a and coprime c b

  Valid (34ms) (colibri2)
72
let ghost
coprime_mul
(a b c:int) : unit
73
requires { coprime c a }
74
requires { coprime c b }
75
ensures { coprime c (a * b) }
76
= {proof…} assert { gcd c (a * b) = gcd c b } {qed}

|a * b| = lcm a b * gcd a b

  Valid (129ms) (colibri2 4) (cvc5 2) (split_vc) (depth 1)
79
let ghost
lcm_gcd
(a b:int) : unit
80
ensures { abs (a * b) = Z.lcm a b * gcd a b }
81
ensures { 0 <= Z.lcm a b }
82
= {proof…} if a <> 0 && b <> 0 then begin
83
let g = gcd a b in
84
assert { 0 < g by g <> 0 };
85
let a' = any int ensures { a = g * result } in
86
assert { abs (a * b) = g * abs (a' * b) };
87
assert { E.div (g * abs (a' * b)) g = abs (a' * b) }
88
end {qed}

a and b divide lcm a b

  Valid (267ms) (colibri2 9) (cvc5 6) (split_vc 3) (depth 2)
91
let ghost
lcm_multiple
(a b:int) : unit
92
ensures { divides a (Z.lcm a b) /\ divides b (Z.lcm a b) }
93
= {proof…} if a <> 0 && b <> 0 then begin
94
let g = gcd a b in
95
assert { 0 < g by g <> 0 };
96
let a' = any int ensures { a = g * result } in
97
let b' = any int ensures { b = g * result } in
98
assert { abs (a * b) = g * abs (a' * b) };
99
assert { Z.lcm a b = abs (a' * b) by E.div (g * abs (a' * b)) g = abs (a' * b) };
100
assert { abs (a' * b) = abs (a * b') };
101
if a' * b < 0 then assert { abs (a' * b) = (- a') * b }
102
else assert { abs (a' * b) = a' * b };
103
assert { divides b (abs (a' * b)) };
104
if a * b' < 0 then assert { abs (a * b') = (- b') * a }
105
else assert { abs (a * b') = b' * a };
106
assert { divides a (abs (a * b')) }
107
end {qed}

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)
110
let ghost
lcm_least
(a b r:int) : unit
111
requires { divides a r /\ divides b r }
112
ensures { divides (Z.lcm a b) r }
113
= {proof…} if a <> 0 && b <> 0 then begin
114
let g = gcd a b in
115
assert { 0 < g by g <> 0 };
116
assert { divides g a /\ divides g b };
117
let a' = any int ensures { a = g * result } in
118
let b' = any int ensures { b = g * result } in
119
assert { gcd (g * a') (g * b') = g * gcd a' b' };
120
assert { coprime b' a' };
121
let p = any int ensures { r = result * a } in
122
assert { divides (g * b') (g * (a' * p)) };
123
let w = any int ensures { g * (a' * p) = result * (g * b') } in
124
assert { g * (a' * p - w * b') = 0 };
125
assert { a' * p = w * b' };
126
assert { divides b' (a' * p) };
127
assert { divides b' p };
128
let q = any int ensures { p = result * b' } in
129
assert { r = q * (g * a' * b') };
130
assert { abs (a * b) = g * abs (a' * b) };
131
assert { Z.lcm a b = abs (a' * b) by E.div (g * abs (a' * b)) g = abs (a' * b) };
132
assert { abs (a' * b) = abs (g * a' * b') };
133
assert { divides (g * a' * b') r }
134
end else begin
135
assert { r = 0 }
136
end {qed}

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)
140
let ghost
lcm_decomp
(d1 d2:int) : (x:int, y:int)
141
requires { 0 < d1 /\ 0 < d2 }
142
ensures { d1 = gcd d1 d2 * x /\ d2 = gcd d1 d2 * y }
143
ensures { 0 < x /\ 0 < y /\ coprime x y }
144
ensures { Z.lcm d1 d2 = gcd d1 d2 * x * y }
145
= {proof…} let g = gcd d1 d2 in
146
assert { 0 < g by g <> 0 };
147
let x = any int ensures { d1 = g * result } in
148
let y = any int ensures { d2 = g * result } in
149
assert { 0 < x /\ 0 < y };
150
assert { gcd (g * x) (g * y) = g * gcd x y };
151
assert { gcd x y = 1 };
152
assert { abs (d1 * d2) = (g * x * y) * g };
153
assert { E.div (abs (d1 * d2)) g = g * x * y };
154
(x, y) {qed}
155
end