def gcd_mul_lcm

bend-collections-laws-math@1.0.0.0 · proofs/math/natural/lcm.bend:169

import Base
import bend-collections-laws-math@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend as A
import bend-collections-laws-math@1.0.0.0/src/math/natural.bend as M
import bend-collections-laws-math@1.0.0.0/proofs/math/natural/gcd.bend as G

169# gcd(a, b) lcm(a, b) == a b   (Mathlib Nat.gcd_mul_lcm)
170def gcd_mul_lcm(+a: Nat, +b: Nat) -> {Nat.mul(M.gcd(a, b), M.lcm(a, b)) == Nat.mul(a, b) : Nat}:
171  match a b:
172    case 0n b0:
173      A.mul_zero(M.gcd(0n, b0))
174    case 1n+ +ap 0n:
175      Equal.trans(Nat, Nat.mul(M.gcd(1n+ap, 0n), 0n), 0n, Nat.mul(1n+ap, 0n), A.mul_zero(M.gcd(1n+ap, 0n)), Equal.sym(Nat, Nat.mul(1n+ap, 0n), 0n, A.mul_zero(1n+ap)))
176    case 1n+ +ap 1n+ +bp:
177      +g = M.gcd(1n+ap, 1n+bp)
178      +la = G.wl(G.ws(1n+bp, 1n+ap, 1n+bp))
179      %Equal.sym(Nat, M.lcm(1n+ap, 1n+bp), Nat.mul(la, 1n+bp), lcm_pos(ap, bp)) : {Nat.mul(g, _) == Nat.mul(1n+ap, 1n+bp) : Nat}
180      %Equal.sym(Nat, Nat.mul(g, Nat.mul(la, 1n+bp)), Nat.mul(Nat.mul(g, la), 1n+bp), Equal.sym(Nat, Nat.mul(Nat.mul(g, la), 1n+bp), Nat.mul(g, Nat.mul(la, 1n+bp)), A.mul_assoc(g, la, 1n+bp))) : {_ == Nat.mul(1n+ap, 1n+bp) : Nat}
181      %Equal.sym(Nat, Nat.mul(g, la), Nat.mul(la, g), A.mul_comm(g, la)) : {Nat.mul(_, 1n+bp) == Nat.mul(1n+ap, 1n+bp) : Nat}
182      Equal.cong(Nat, Nat, z => Nat.mul(z, 1n+bp), Nat.mul(la, g), 1n+ap, Equal.sym(Nat, 1n+ap, Nat.mul(la, g), G.gcd_dvd_left(1n+ap, 1n+bp)))