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

Theorem dvdsle 15255
Description: The divisors of a positive integer are bounded by it. The proof does not use /. (Contributed by Paul Chapman, 21-Mar-2011.)
Assertion
Ref Expression
dvdsle ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀𝑁𝑀𝑁))

Proof of Theorem dvdsle
Dummy variable 𝑛 is distinct from all other variables.
StepHypRef Expression
1 breq2 4848 . . . . . . . . . . . . 13 (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑁 < 𝑀𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1)))
2 oveq2 6882 . . . . . . . . . . . . . 14 (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · 𝑀) = (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)))
32neeq1d 3037 . . . . . . . . . . . . 13 (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → ((𝑛 · 𝑀) ≠ 𝑁 ↔ (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁))
41, 3imbi12d 335 . . . . . . . . . . . 12 (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → ((𝑁 < 𝑀 → (𝑛 · 𝑀) ≠ 𝑁) ↔ (𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁)))
5 breq1 4847 . . . . . . . . . . . . 13 (𝑁 = if(𝑁 ∈ ℕ, 𝑁, 1) → (𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1) ↔ if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1)))
6 neeq2 3041 . . . . . . . . . . . . 13 (𝑁 = if(𝑁 ∈ ℕ, 𝑁, 1) → ((𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁 ↔ (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1)))
75, 6imbi12d 335 . . . . . . . . . . . 12 (𝑁 = if(𝑁 ∈ ℕ, 𝑁, 1) → ((𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁) ↔ (if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1))))
8 oveq1 6881 . . . . . . . . . . . . . 14 (𝑛 = if(𝑛 ∈ ℤ, 𝑛, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) = (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)))
98neeq1d 3037 . . . . . . . . . . . . 13 (𝑛 = if(𝑛 ∈ ℤ, 𝑛, 1) → ((𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1) ↔ (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1)))
109imbi2d 331 . . . . . . . . . . . 12 (𝑛 = if(𝑛 ∈ ℤ, 𝑛, 1) → ((if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1)) ↔ (if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1))))
11 1z 11673 . . . . . . . . . . . . . 14 1 ∈ ℤ
1211elimel 4346 . . . . . . . . . . . . 13 if(𝑀 ∈ ℤ, 𝑀, 1) ∈ ℤ
13 1nn 11316 . . . . . . . . . . . . . 14 1 ∈ ℕ
1413elimel 4346 . . . . . . . . . . . . 13 if(𝑁 ∈ ℕ, 𝑁, 1) ∈ ℕ
1511elimel 4346 . . . . . . . . . . . . 13 if(𝑛 ∈ ℤ, 𝑛, 1) ∈ ℤ
1612, 14, 15dvdslelem 15254 . . . . . . . . . . . 12 (if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1))
174, 7, 10, 16dedth3h 4337 . . . . . . . . . . 11 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑛 ∈ ℤ) → (𝑁 < 𝑀 → (𝑛 · 𝑀) ≠ 𝑁))
18173expia 1143 . . . . . . . . . 10 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑛 ∈ ℤ → (𝑁 < 𝑀 → (𝑛 · 𝑀) ≠ 𝑁)))
1918com23 86 . . . . . . . . 9 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑁 < 𝑀 → (𝑛 ∈ ℤ → (𝑛 · 𝑀) ≠ 𝑁)))
20193impia 1138 . . . . . . . 8 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → (𝑛 ∈ ℤ → (𝑛 · 𝑀) ≠ 𝑁))
2120imp 395 . . . . . . 7 (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → (𝑛 · 𝑀) ≠ 𝑁)
2221neneqd 2983 . . . . . 6 (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → ¬ (𝑛 · 𝑀) = 𝑁)
2322nrexdv 3188 . . . . 5 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → ¬ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)
24 nnz 11665 . . . . . . 7 (𝑁 ∈ ℕ → 𝑁 ∈ ℤ)
25 divides 15205 . . . . . . 7 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
2624, 25sylan2 582 . . . . . 6 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
27263adant3 1155 . . . . 5 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → (𝑀𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
2823, 27mtbird 316 . . . 4 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → ¬ 𝑀𝑁)
29283expia 1143 . . 3 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑁 < 𝑀 → ¬ 𝑀𝑁))
3029con2d 131 . 2 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀𝑁 → ¬ 𝑁 < 𝑀))
31 zre 11647 . . 3 (𝑀 ∈ ℤ → 𝑀 ∈ ℝ)
32 nnre 11312 . . 3 (𝑁 ∈ ℕ → 𝑁 ∈ ℝ)
33 lenlt 10401 . . 3 ((𝑀 ∈ ℝ ∧ 𝑁 ∈ ℝ) → (𝑀𝑁 ↔ ¬ 𝑁 < 𝑀))
3431, 32, 33syl2an 585 . 2 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀𝑁 ↔ ¬ 𝑁 < 𝑀))
3530, 34sylibrd 250 1 ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀𝑁𝑀𝑁))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 197  wa 384  w3a 1100   = wceq 1637  wcel 2156  wne 2978  wrex 3097  ifcif 4279   class class class wbr 4844  (class class class)co 6874  cr 10220  1c1 10222   · cmul 10226   < clt 10359  cle 10360  cn 11305  cz 11643  cdvds 15203
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 2068  ax-7 2104  ax-8 2158  ax-9 2165  ax-10 2185  ax-11 2201  ax-12 2214  ax-13 2420  ax-ext 2784  ax-sep 4975  ax-nul 4983  ax-pow 5035  ax-pr 5096  ax-un 7179  ax-resscn 10278  ax-1cn 10279  ax-icn 10280  ax-addcl 10281  ax-addrcl 10282  ax-mulcl 10283  ax-mulrcl 10284  ax-mulcom 10285  ax-addass 10286  ax-mulass 10287  ax-distr 10288  ax-i2m1 10289  ax-1ne0 10290  ax-1rid 10291  ax-rnegex 10292  ax-rrecex 10293  ax-cnre 10294  ax-pre-lttri 10295  ax-pre-lttrn 10296  ax-pre-ltadd 10297  ax-pre-mulgt0 10298
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2061  df-eu 2634  df-mo 2635  df-clab 2793  df-cleq 2799  df-clel 2802  df-nfc 2937  df-ne 2979  df-nel 3082  df-ral 3101  df-rex 3102  df-reu 3103  df-rab 3105  df-v 3393  df-sbc 3634  df-csb 3729  df-dif 3772  df-un 3774  df-in 3776  df-ss 3783  df-pss 3785  df-nul 4117  df-if 4280  df-pw 4353  df-sn 4371  df-pr 4373  df-tp 4375  df-op 4377  df-uni 4631  df-iun 4714  df-br 4845  df-opab 4907  df-mpt 4924  df-tr 4947  df-id 5219  df-eprel 5224  df-po 5232  df-so 5233  df-fr 5270  df-we 5272  df-xp 5317  df-rel 5318  df-cnv 5319  df-co 5320  df-dm 5321  df-rn 5322  df-res 5323  df-ima 5324  df-pred 5893  df-ord 5939  df-on 5940  df-lim 5941  df-suc 5942  df-iota 6064  df-fun 6103  df-fn 6104  df-f 6105  df-f1 6106  df-fo 6107  df-f1o 6108  df-fv 6109  df-riota 6835  df-ov 6877  df-oprab 6878  df-mpt2 6879  df-om 7296  df-wrecs 7642  df-recs 7704  df-rdg 7742  df-er 7979  df-en 8193  df-dom 8194  df-sdom 8195  df-pnf 10361  df-mnf 10362  df-xr 10363  df-ltxr 10364  df-le 10365  df-sub 10553  df-neg 10554  df-nn 11306  df-n0 11560  df-z 11644  df-dvds 15204
This theorem is referenced by:  dvdsleabs  15256  dvdsssfz1  15263  fzm1ndvds  15267  fzo0dvdseq  15268  n2dvds1  15324  gcd1  15468  bezoutlem4  15478  dfgcd2  15482  gcdzeq  15490  bezoutr1  15501  lcmgcdlem  15538  qredeq  15589  isprm3  15614  prmdvdsfz  15634  isprm5  15636  maxprmfct  15638  isprm6  15643  prmfac1  15648  ncoprmlnprm  15653  pcpre1  15764  pcidlem  15793  pcprod  15816  pcfac  15820  pockthg  15827  prmreclem1  15837  prmreclem3  15839  prmreclem5  15841  1arith  15848  4sqlem11  15876  prmolelcmf  15969  gexcl2  18205  sylow1lem1  18214  sylow1lem5  18218  gexex  18457  ablfac1eu  18674  ablfaclem3  18688  znidomb  20117  dvdsflsumcom  25128  chtublem  25150  vmasum  25155  logfac2  25156  bposlem6  25228  lgsdir  25271  lgsdilem2  25272  lgsne0  25274  lgsqrlem2  25286  lgsquadlem2  25320  2sqlem8  25365  2sqblem  25370  2sqmod  29973  oddpwdc  30741  nn0prpw  32639  nznngen  39015  etransclem41  40971
  Copyright terms: Public domain W3C validator