Package natural-divides-lcm-thm: Properties of natural number least common multiple
Information
| name | natural-divides-lcm-thm |
| version | 1.0 |
| description | Properties of natural number least common multiple |
| author | Joe Leslie-Hurd <joe@gilith.com> |
| license | MIT |
| provenance | HOL Light theory extracted on 2014-11-01 |
| checksum | 492b9462ef1667dfab2de59249d4df44d8eca454 |
| requires | base natural-divides-def natural-divides-gcd natural-divides-lcm-def natural-divides-thm |
| show | Data.Bool Number.Natural |
Files
- Package tarball natural-divides-lcm-thm-1.0.tgz
- Theory source file natural-divides-lcm-thm.thy (included in the package tarball)
Theorems
⊦ ∀a. lcm a 0 = 0
⊦ ∀a. lcm a a = a
⊦ ∀a. lcm a 1 = a
⊦ ∀a. lcm 1 a = a
⊦ ∀a b. divides a (lcm a b)
⊦ ∀a b. divides b (lcm a b)
⊦ ∀a b. lcm a b = lcm b a
⊦ ∀a b. lcm a b = a ⇔ divides b a
⊦ ∀a b. lcm b a = a ⇔ divides b a
⊦ ∀a b c. divides a b ⇒ divides a (lcm b c)
⊦ ∀a b c. divides a b ⇒ divides a (lcm c b)
⊦ ∀a b c. lcm (lcm a b) c = lcm a (lcm b c)
⊦ ∀a b. lcm a b = 0 ⇔ a = 0 ∨ b = 0
⊦ ∀a b c. divides (lcm a b) c ⇔ divides a c ∧ divides b c
⊦ ∀a b c. gcd a (lcm b c) = lcm (gcd a b) (gcd a c)
⊦ ∀a b c. lcm a (gcd b c) = gcd (lcm a b) (lcm a c)
⊦ ∀a b c. gcd (lcm b c) a = lcm (gcd b a) (gcd c a)
⊦ ∀a b c. lcm (gcd b c) a = gcd (lcm b a) (lcm c a)
⊦ ∀a b c. lcm (a * b) (a * c) = a * lcm b c
⊦ ∀a b c. lcm (b * a) (c * a) = lcm b c * a
⊦ ∀a b c. divides a c ∧ divides b c ⇒ divides (lcm a b) c
⊦ ∀a b. lcm a b = 1 ⇔ a = 1 ∧ b = 1
⊦ ∀a b l.
divides a l ∧ divides b l ∧
(∀c. divides a c ∧ divides b c ⇒ divides l c) ⇒ lcm a b = l
External Type Operators
- →
- bool
- Number
- Natural
- natural
- Natural
External Constants
- =
- Data
- Bool
- ∀
- ∧
- ⇒
- ∃
- ∨
- ¬
- ⊥
- ⊤
- Bool
- Number
- Natural
- *
- +
- <
- ≤
- bit0
- bit1
- divides
- gcd
- lcm
- suc
- zero
- Natural
Assumptions
⊦ ⊤
⊦ ¬⊥ ⇔ ⊤
⊦ ¬⊤ ⇔ ⊥
⊦ bit0 0 = 0
⊦ ∀t. t ⇒ t
⊦ ∀a. divides a 0
⊦ ∀a. divides a a
⊦ ⊥ ⇔ ∀p. p
⊦ ∀t. t ∨ ¬t
⊦ ∀a. divides 1 a
⊦ (¬) = λp. p ⇒ ⊥
⊦ ∀t. (∀x. t) ⇔ t
⊦ ∀t. (λx. t x) = t
⊦ (∀) = λp. p = λx. ⊤
⊦ ∀t. ¬¬t ⇔ t
⊦ ∀t. ⊥ ∧ t ⇔ ⊥
⊦ ∀t. ⊤ ∧ t ⇔ t
⊦ ∀t. t ∧ t ⇔ t
⊦ ∀t. ⊥ ∨ t ⇔ t
⊦ ∀t. ⊤ ∨ t ⇔ ⊤
⊦ ∀t. t ∨ ⊥ ⇔ t
⊦ ∀n. 0 * n = 0
⊦ ∀m. m * 0 = 0
⊦ ∀n. 0 + n = n
⊦ ∀a. gcd a 0 = a
⊦ ∀a. gcd a a = a
⊦ ∀a. lcm 0 a = 0
⊦ ∀t. (⊥ ⇔ t) ⇔ ¬t
⊦ ∀t. (t ⇔ ⊥) ⇔ ¬t
⊦ ∀t. t ⇒ ⊥ ⇔ ¬t
⊦ ∀n. bit1 n = suc (bit0 n)
⊦ ∀m. m * 1 = m
⊦ ∀a b. divides (gcd a b) a
⊦ ∀a b. divides (gcd a b) b
⊦ (⇒) = λp q. p ∧ q ⇔ p
⊦ ∀t. (t ⇔ ⊤) ∨ (t ⇔ ⊥)
⊦ ∀n. bit0 (suc n) = suc (suc (bit0 n))
⊦ ∀x y. x = y ⇒ y = x
⊦ ∀m n. m * n = n * m
⊦ ∀m n. m + n = n + m
⊦ ∀a b. gcd a b = gcd b a
⊦ ∀a. divides a 1 ⇔ a = 1
⊦ ∀m n. ¬(m ≤ n) ⇔ n < m
⊦ (∧) = λp q. (λf. f p q) = λf. f ⊤ ⊤
⊦ ∀p. ¬(∃x. p x) ⇔ ∀x. ¬p x
⊦ (∃) = λp. ∀q. (∀x. p x ⇒ q) ⇒ q
⊦ ∀m n. m + suc n = suc (m + n)
⊦ ∀m n. suc m + n = suc (m + n)
⊦ ∀t1 t2. ¬(t1 ∧ t2) ⇔ ¬t1 ∨ ¬t2
⊦ ∀a b c. divides a b ⇒ divides a (b * c)
⊦ ∀a b c. divides b a ⇒ divides (gcd c b) a
⊦ ∀a b c. divides (a * b) c ⇒ divides a c
⊦ ∀a b. divides a b ⇔ ∃c. c * a = b
⊦ (∨) = λp q. ∀r. (p ⇒ r) ⇒ (q ⇒ r) ⇒ r
⊦ ∀m n. m ≤ n ∧ n ≤ m ⇔ m = n
⊦ ∀a b. lcm a b * gcd a b = a * b
⊦ ∀a b. divides a b ∧ divides b a ⇒ a = b
⊦ ∀m n. m < n ⇔ ∃d. n = m + suc d
⊦ ∀p q r. p ⇒ q ⇒ r ⇔ p ∧ q ⇒ r
⊦ ∀m n p. m * (n * p) = m * n * p
⊦ ∀a b c. divides a b ∧ divides b c ⇒ divides a c
⊦ ∀m n. m * n = 0 ⇔ m = 0 ∨ n = 0
⊦ ∀a b. gcd a b = 0 ⇔ a = 0 ∧ b = 0
⊦ ∀p. p 0 ∧ (∀n. p n ⇒ p (suc n)) ⇒ ∀n. p n
⊦ ∀a b c. divides c (gcd a b) ⇔ divides c a ∧ divides c b
⊦ ∀a b c. divides (gcd a (b * c)) (gcd a b * gcd a c)
⊦ ∀a b c. gcd (a * b) (a * c) = a * gcd b c
⊦ ∀m n p. m * n = m * p ⇔ m = 0 ∨ n = p
⊦ ∀m n p. m * p = n * p ⇔ m = n ∨ p = 0
⊦ ∀a b c. divides (a * b) (a * c) ⇔ a = 0 ∨ divides b c
⊦ ∀a b c. divides (b * a) (c * a) ⇔ a = 0 ∨ divides b c
⊦ ∀a b c d. divides a c ∧ divides b d ⇒ divides (a * b) (c * d)
⊦ ∀a b c. gcd b c = 1 ∧ divides b a ∧ divides c a ⇒ divides (b * c) a
⊦ ∀p.
p 0 0 ∧ (∀a b. gcd a b = 1 ⇒ p a b) ∧
(∀c a b. ¬(c = 0) ∧ p a b ⇒ p (c * a) (c * b)) ⇒ ∀a b. p a b