MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  lcmf Structured version   Visualization version   GIF version

Theorem lcmf 15572
Description: Characterization of the least common multiple of a set of integers (without 0): A positiven integer is the least common multiple of a set of integers iff it divides each of the elements of the set and every integer which divides each of the elements of the set is greater than or equal to this integer. (Contributed by AV, 22-Aug-2020.)
Assertion
Ref Expression
lcmf ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 = (lcm𝑍) ↔ (∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘))))
Distinct variable groups:   𝑘,𝐾,𝑚   𝑘,𝑍,𝑚

Proof of Theorem lcmf
StepHypRef Expression
1 dvdslcmf 15570 . . . . . 6 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin) → ∀𝑚𝑍 𝑚 ∥ (lcm𝑍))
213adant3 1155 . . . . 5 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → ∀𝑚𝑍 𝑚 ∥ (lcm𝑍))
3 lcmfledvds 15571 . . . . . . 7 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → ((𝑘 ∈ ℕ ∧ ∀𝑚𝑍 𝑚𝑘) → (lcm𝑍) ≤ 𝑘))
43expdimp 442 . . . . . 6 (((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) ∧ 𝑘 ∈ ℕ) → (∀𝑚𝑍 𝑚𝑘 → (lcm𝑍) ≤ 𝑘))
54ralrimiva 3165 . . . . 5 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘 → (lcm𝑍) ≤ 𝑘))
62, 5jca 503 . . . 4 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → (∀𝑚𝑍 𝑚 ∥ (lcm𝑍) ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘 → (lcm𝑍) ≤ 𝑘)))
76adantl 469 . . 3 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (∀𝑚𝑍 𝑚 ∥ (lcm𝑍) ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘 → (lcm𝑍) ≤ 𝑘)))
8 breq2 4859 . . . . 5 (𝐾 = (lcm𝑍) → (𝑚𝐾𝑚 ∥ (lcm𝑍)))
98ralbidv 3185 . . . 4 (𝐾 = (lcm𝑍) → (∀𝑚𝑍 𝑚𝐾 ↔ ∀𝑚𝑍 𝑚 ∥ (lcm𝑍)))
10 breq1 4858 . . . . . 6 (𝐾 = (lcm𝑍) → (𝐾𝑘 ↔ (lcm𝑍) ≤ 𝑘))
1110imbi2d 331 . . . . 5 (𝐾 = (lcm𝑍) → ((∀𝑚𝑍 𝑚𝑘𝐾𝑘) ↔ (∀𝑚𝑍 𝑚𝑘 → (lcm𝑍) ≤ 𝑘)))
1211ralbidv 3185 . . . 4 (𝐾 = (lcm𝑍) → (∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘) ↔ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘 → (lcm𝑍) ≤ 𝑘)))
139, 12anbi12d 618 . . 3 (𝐾 = (lcm𝑍) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) ↔ (∀𝑚𝑍 𝑚 ∥ (lcm𝑍) ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘 → (lcm𝑍) ≤ 𝑘))))
147, 13syl5ibrcom 238 . 2 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 = (lcm𝑍) → (∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘))))
15 lcmfn0cl 15565 . . . . . 6 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → (lcm𝑍) ∈ ℕ)
1615adantl 469 . . . . 5 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (lcm𝑍) ∈ ℕ)
17 breq2 4859 . . . . . . . 8 (𝑘 = (lcm𝑍) → (𝑚𝑘𝑚 ∥ (lcm𝑍)))
1817ralbidv 3185 . . . . . . 7 (𝑘 = (lcm𝑍) → (∀𝑚𝑍 𝑚𝑘 ↔ ∀𝑚𝑍 𝑚 ∥ (lcm𝑍)))
19 breq2 4859 . . . . . . 7 (𝑘 = (lcm𝑍) → (𝐾𝑘𝐾 ≤ (lcm𝑍)))
2018, 19imbi12d 335 . . . . . 6 (𝑘 = (lcm𝑍) → ((∀𝑚𝑍 𝑚𝑘𝐾𝑘) ↔ (∀𝑚𝑍 𝑚 ∥ (lcm𝑍) → 𝐾 ≤ (lcm𝑍))))
2120rspcv 3509 . . . . 5 ((lcm𝑍) ∈ ℕ → (∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘) → (∀𝑚𝑍 𝑚 ∥ (lcm𝑍) → 𝐾 ≤ (lcm𝑍))))
2216, 21syl 17 . . . 4 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘) → (∀𝑚𝑍 𝑚 ∥ (lcm𝑍) → 𝐾 ≤ (lcm𝑍))))
2322adantld 480 . . 3 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → (∀𝑚𝑍 𝑚 ∥ (lcm𝑍) → 𝐾 ≤ (lcm𝑍))))
242adantl 469 . . . . 5 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ∀𝑚𝑍 𝑚 ∥ (lcm𝑍))
25 nnre 11319 . . . . . . . 8 (𝐾 ∈ ℕ → 𝐾 ∈ ℝ)
2615nnred 11327 . . . . . . . 8 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → (lcm𝑍) ∈ ℝ)
2725, 26anim12i 602 . . . . . . 7 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 ∈ ℝ ∧ (lcm𝑍) ∈ ℝ))
28 leloe 10416 . . . . . . 7 ((𝐾 ∈ ℝ ∧ (lcm𝑍) ∈ ℝ) → (𝐾 ≤ (lcm𝑍) ↔ (𝐾 < (lcm𝑍) ∨ 𝐾 = (lcm𝑍))))
2927, 28syl 17 . . . . . 6 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 ≤ (lcm𝑍) ↔ (𝐾 < (lcm𝑍) ∨ 𝐾 = (lcm𝑍))))
30 lcmfledvds 15571 . . . . . . . . . . . . 13 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → ((𝐾 ∈ ℕ ∧ ∀𝑚𝑍 𝑚𝐾) → (lcm𝑍) ≤ 𝐾))
3130expd 402 . . . . . . . . . . . 12 ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → (𝐾 ∈ ℕ → (∀𝑚𝑍 𝑚𝐾 → (lcm𝑍) ≤ 𝐾)))
3231impcom 396 . . . . . . . . . . 11 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (∀𝑚𝑍 𝑚𝐾 → (lcm𝑍) ≤ 𝐾))
33 lenlt 10408 . . . . . . . . . . . . 13 (((lcm𝑍) ∈ ℝ ∧ 𝐾 ∈ ℝ) → ((lcm𝑍) ≤ 𝐾 ↔ ¬ 𝐾 < (lcm𝑍)))
3426, 25, 33syl2anr 586 . . . . . . . . . . . 12 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((lcm𝑍) ≤ 𝐾 ↔ ¬ 𝐾 < (lcm𝑍)))
35 pm2.21 121 . . . . . . . . . . . 12 𝐾 < (lcm𝑍) → (𝐾 < (lcm𝑍) → 𝐾 = (lcm𝑍)))
3634, 35syl6bi 244 . . . . . . . . . . 11 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((lcm𝑍) ≤ 𝐾 → (𝐾 < (lcm𝑍) → 𝐾 = (lcm𝑍))))
3732, 36syldc 48 . . . . . . . . . 10 (∀𝑚𝑍 𝑚𝐾 → ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 < (lcm𝑍) → 𝐾 = (lcm𝑍))))
3837adantr 468 . . . . . . . . 9 ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 < (lcm𝑍) → 𝐾 = (lcm𝑍))))
3938com13 88 . . . . . . . 8 (𝐾 < (lcm𝑍) → ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → 𝐾 = (lcm𝑍))))
40 2a1 28 . . . . . . . 8 (𝐾 = (lcm𝑍) → ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → 𝐾 = (lcm𝑍))))
4139, 40jaoi 875 . . . . . . 7 ((𝐾 < (lcm𝑍) ∨ 𝐾 = (lcm𝑍)) → ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → 𝐾 = (lcm𝑍))))
4241com12 32 . . . . . 6 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((𝐾 < (lcm𝑍) ∨ 𝐾 = (lcm𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → 𝐾 = (lcm𝑍))))
4329, 42sylbid 231 . . . . 5 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 ≤ (lcm𝑍) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → 𝐾 = (lcm𝑍))))
4424, 43embantd 59 . . . 4 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((∀𝑚𝑍 𝑚 ∥ (lcm𝑍) → 𝐾 ≤ (lcm𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → 𝐾 = (lcm𝑍))))
4544com23 86 . . 3 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → ((∀𝑚𝑍 𝑚 ∥ (lcm𝑍) → 𝐾 ≤ (lcm𝑍)) → 𝐾 = (lcm𝑍))))
4623, 45mpdd 43 . 2 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → ((∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘)) → 𝐾 = (lcm𝑍)))
4714, 46impbid 203 1 ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 = (lcm𝑍) ↔ (∀𝑚𝑍 𝑚𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚𝑍 𝑚𝑘𝐾𝑘))))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 197  wa 384  wo 865  w3a 1100   = wceq 1637  wcel 2157  wnel 3092  wral 3107  wss 3780   class class class wbr 4855  cfv 6108  Fincfn 8199  cr 10227  0cc0 10228   < clt 10366  cle 10367  cn 11312  cz 11650  cdvds 15210  lcmclcmf 15528
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2069  ax-7 2105  ax-8 2159  ax-9 2166  ax-10 2186  ax-11 2202  ax-12 2215  ax-13 2422  ax-ext 2795  ax-rep 4975  ax-sep 4986  ax-nul 4994  ax-pow 5046  ax-pr 5107  ax-un 7186  ax-inf2 8792  ax-cnex 10284  ax-resscn 10285  ax-1cn 10286  ax-icn 10287  ax-addcl 10288  ax-addrcl 10289  ax-mulcl 10290  ax-mulrcl 10291  ax-mulcom 10292  ax-addass 10293  ax-mulass 10294  ax-distr 10295  ax-i2m1 10296  ax-1ne0 10297  ax-1rid 10298  ax-rnegex 10299  ax-rrecex 10300  ax-cnre 10301  ax-pre-lttri 10302  ax-pre-lttrn 10303  ax-pre-ltadd 10304  ax-pre-mulgt0 10305  ax-pre-sup 10306
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-fal 1651  df-ex 1860  df-nf 1864  df-sb 2062  df-mo 2635  df-eu 2642  df-clab 2804  df-cleq 2810  df-clel 2813  df-nfc 2948  df-ne 2990  df-nel 3093  df-ral 3112  df-rex 3113  df-reu 3114  df-rmo 3115  df-rab 3116  df-v 3404  df-sbc 3645  df-csb 3740  df-dif 3783  df-un 3785  df-in 3787  df-ss 3794  df-pss 3796  df-nul 4128  df-if 4291  df-pw 4364  df-sn 4382  df-pr 4384  df-tp 4386  df-op 4388  df-uni 4642  df-int 4681  df-iun 4725  df-br 4856  df-opab 4918  df-mpt 4935  df-tr 4958  df-id 5230  df-eprel 5235  df-po 5243  df-so 5244  df-fr 5281  df-se 5282  df-we 5283  df-xp 5328  df-rel 5329  df-cnv 5330  df-co 5331  df-dm 5332  df-rn 5333  df-res 5334  df-ima 5335  df-pred 5904  df-ord 5950  df-on 5951  df-lim 5952  df-suc 5953  df-iota 6071  df-fun 6110  df-fn 6111  df-f 6112  df-f1 6113  df-fo 6114  df-f1o 6115  df-fv 6116  df-isom 6117  df-riota 6842  df-ov 6884  df-oprab 6885  df-mpt2 6886  df-om 7303  df-1st 7405  df-2nd 7406  df-wrecs 7649  df-recs 7711  df-rdg 7749  df-1o 7803  df-oadd 7807  df-er 7986  df-en 8200  df-dom 8201  df-sdom 8202  df-fin 8203  df-sup 8594  df-inf 8595  df-oi 8661  df-card 9055  df-pnf 10368  df-mnf 10369  df-xr 10370  df-ltxr 10371  df-le 10372  df-sub 10560  df-neg 10561  df-div 10977  df-nn 11313  df-2 11371  df-3 11372  df-n0 11567  df-z 11651  df-uz 11912  df-rp 12054  df-fz 12557  df-fzo 12697  df-seq 13032  df-exp 13091  df-hash 13345  df-cj 14069  df-re 14070  df-im 14071  df-sqrt 14205  df-abs 14206  df-clim 14449  df-prod 14864  df-dvds 15211  df-lcmf 15530
This theorem is referenced by:  lcmftp  15575  lcmfunsnlem2lem2  15578
  Copyright terms: Public domain W3C validator