Theorem dvdsle 16448

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.

Step	Hyp	Ref	Expression
1		breq2 5106	. . . . . . . . . . . . 13 ⊢ (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑁 < 𝑀 ↔ 𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1)))
2		oveq2 7416	. . . . . . . . . . . . . 14 ⊢ (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · 𝑀) = (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)))
3	2	neeq1d 3014	. . . . . . . . . . . . 13 ⊢ (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → ((𝑛 · 𝑀) ≠ 𝑁 ↔ (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁))
4	1, 3	imbi12d 347	. . . . . . . . . . . 12 ⊢ (𝑀 = if(𝑀 ∈ ℤ, 𝑀, 1) → ((𝑁 < 𝑀 → (𝑛 · 𝑀) ≠ 𝑁) ↔ (𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁)))
5		breq1 5105	. . . . . . . . . . . . 13 ⊢ (𝑁 = if(𝑁 ∈ ℕ, 𝑁, 1) → (𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1) ↔ if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1)))
6		neeq2 3018	. . . . . . . . . . . . 13 ⊢ (𝑁 = if(𝑁 ∈ ℕ, 𝑁, 1) → ((𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁 ↔ (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1)))
7	5, 6	imbi12d 347	. . . . . . . . . . . 12 ⊢ (𝑁 = if(𝑁 ∈ ℕ, 𝑁, 1) → ((𝑁 < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ 𝑁) ↔ (if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1))))
8		oveq1 7415	. . . . . . . . . . . . . 14 ⊢ (𝑛 = if(𝑛 ∈ ℤ, 𝑛, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) = (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)))
9	8	neeq1d 3014	. . . . . . . . . . . . 13 ⊢ (𝑛 = if(𝑛 ∈ ℤ, 𝑛, 1) → ((𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1) ↔ (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1)))
10	9	imbi2d 343	. . . . . . . . . . . 12 ⊢ (𝑛 = if(𝑛 ∈ ℤ, 𝑛, 1) → ((if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (𝑛 · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1)) ↔ (if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1))))
11		1z 12696	. . . . . . . . . . . . . 14 ⊢ 1 ∈ ℤ
12	11	elimel 4551	. . . . . . . . . . . . 13 ⊢ if(𝑀 ∈ ℤ, 𝑀, 1) ∈ ℤ
13		1nn 12316	. . . . . . . . . . . . . 14 ⊢ 1 ∈ ℕ
14	13	elimel 4551	. . . . . . . . . . . . 13 ⊢ if(𝑁 ∈ ℕ, 𝑁, 1) ∈ ℕ
15	11	elimel 4551	. . . . . . . . . . . . 13 ⊢ if(𝑛 ∈ ℤ, 𝑛, 1) ∈ ℤ
16	12, 14, 15	dvdslelem 16447	. . . . . . . . . . . 12 ⊢ (if(𝑁 ∈ ℕ, 𝑁, 1) < if(𝑀 ∈ ℤ, 𝑀, 1) → (if(𝑛 ∈ ℤ, 𝑛, 1) · if(𝑀 ∈ ℤ, 𝑀, 1)) ≠ if(𝑁 ∈ ℕ, 𝑁, 1))
17	4, 7, 10, 16	dedth3h 4542	. . . . . . . . . . 11 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑛 ∈ ℤ) → (𝑁 < 𝑀 → (𝑛 · 𝑀) ≠ 𝑁))
18	17	3expia 1139	. . . . . . . . . 10 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑛 ∈ ℤ → (𝑁 < 𝑀 → (𝑛 · 𝑀) ≠ 𝑁)))
19	18	com23 87	. . . . . . . . 9 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑁 < 𝑀 → (𝑛 ∈ ℤ → (𝑛 · 𝑀) ≠ 𝑁)))
20	19	3impia 1135	. . . . . . . 8 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → (𝑛 ∈ ℤ → (𝑛 · 𝑀) ≠ 𝑁))
21	20	imp 412	. . . . . . 7 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → (𝑛 · 𝑀) ≠ 𝑁)
22	21	neneqd 2960	. . . . . 6 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → ¬ (𝑛 · 𝑀) = 𝑁)
23	22	nrexdv 3157	. . . . 5 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → ¬ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)
24		nnz 12684	. . . . . . 7 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℤ)
25		divides 16392	. . . . . . 7 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
26	24, 25	sylan2 605	. . . . . 6 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
27	26	3adant3 1150	. . . . 5 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
28	23, 27	mtbird 328	. . . 4 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ 𝑁 < 𝑀) → ¬ 𝑀 ∥ 𝑁)
29	28	3expia 1139	. . 3 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑁 < 𝑀 → ¬ 𝑀 ∥ 𝑁))
30	29	con2d 135	. 2 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀 ∥ 𝑁 → ¬ 𝑁 < 𝑀))
31		zre 12667	. . 3 ⊢ (𝑀 ∈ ℤ → 𝑀 ∈ ℝ)
32		nnre 12312	. . 3 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℝ)
33		lenlt 11360	. . 3 ⊢ ((𝑀 ∈ ℝ ∧ 𝑁 ∈ ℝ) → (𝑀 ≤ 𝑁 ↔ ¬ 𝑁 < 𝑀))
34	31, 32, 33	syl2an 608	. 2 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀 ≤ 𝑁 ↔ ¬ 𝑁 < 𝑀))
35	30, 34	sylibrd 262	1 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀 ∥ 𝑁 → 𝑀 ≤ 𝑁))

This proof depends on syntax axioms:  ¬ wn 3   → wi 4   ↔ wb 209   ∧ wa 401   ∧ w3a 1103   = wceq 1570   ∈ wcel 2145   ≠ wne 2955  ∃wrex 3086  ifcif 4481   class class class wbr 5102  (class class class)co 7408  ℝcr 11171  1c1 11173   · cmul 11177   < clt 11315   ≤ cle 11316  ℕcn 12305  ℤcz 12663   ∥ cdvds 16390

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1943  ax-6 2000  ax-7 2041  ax-8 2147  ax-9 2155  ax-10 2178  ax-11 2194  ax-12 2213  ax-ext 2732  ax-sep 5248  ax-nul 5259  ax-pow 5326  ax-pr 5390  ax-un 7734  ax-resscn 11229  ax-1cn 11230  ax-icn 11231  ax-addcl 11232  ax-addrcl 11233  ax-mulcl 11234  ax-mulrcl 11235  ax-mulcom 11236  ax-addass 11237  ax-mulass 11238  ax-distr 11239  ax-i2m1 11240  ax-1ne0 11241  ax-1rid 11242  ax-rnegex 11243  ax-rrecex 11244  ax-cnre 11245  ax-pre-lttri 11246  ax-pre-lttrn 11247  ax-pre-ltadd 11248  ax-pre-mulgt0 11249

This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1104  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2100  df-mo 2564  df-eu 2594  df-clab 2739  df-cleq 2752  df-clel 2835  df-nfc 2909  df-ne 2956  df-nel 3062  df-ral 3077  df-rex 3087  df-reu 3366  df-rab 3413  df-v 3452  df-sbc 3739  df-csb 3847  df-dif 3901  df-un 3903  df-in 3905  df-ss 3915  df-pss 3918  df-nul 4279  df-if 4482  df-pw 4558  df-sn 4584  df-pr 4586  df-op 4590  df-uni 4867  df-iun 4952  df-br 5103  df-opab 5167  df-mpt 5186  df-tr 5212  df-id 5542  df-eprel 5547  df-po 5555  df-so 5556  df-fr 5600  df-we 5602  df-xp 5653  df-rel 5654  df-cnv 5655  df-co 5656  df-dm 5657  df-rn 5658  df-res 5659  df-ima 5660  df-pred 6293  df-ord 6354  df-on 6355  df-lim 6356  df-suc 6357  df-iota 6483  df-fun 6529  df-fn 6530  df-f 6531  df-f1 6532  df-fo 6533  df-f1o 6534  df-fv 6535  df-riota 7365  df-ov 7411  df-oprab 7412  df-mpo 7413  df-om 7861  df-2nd 7985  df-frecs 8277  df-wrecs 8308  df-recs 8357  df-rdg 8396  df-er 8695  df-en 8952  df-dom 8953  df-sdom 8954  df-pnf 11317  df-mnf 11318  df-xr 11319  df-ltxr 11320  df-le 11321  df-sub 11515  df-neg 11516  df-nn 12306  df-n0 12577  df-z 12664  df-dvds 16391

This theorem is used by:  dvdsleabs  16449  dvdsssfz1  16456  fzm1ndvds  16460  fzo0dvdseq  16461  gcd1  16666  bezoutlem4  16680  dfgcd2  16684  gcdzeq  16690  bezoutr1  16707  lcmgcdlem  16744  qredeq  16795  isprm3  16821  prmdvdsfz  16844  isprm5  16846  maxprmfct  16848  isprm6  16853  prmfac1  16859  ncoprmlnprm  16867  pcpre1  16982  pcidlem  17012  pcprod  17035  pcfac  17039  pockthg  17046  prmreclem1  17056  prmreclem3  17058  prmreclem5  17060  1arith  17067  4sqlem11  17095  prmolelcmf  17188  gexcl2  19765  sylow1lem1  19774  sylow1lem5  19778  gexex  20029  ablfac1eu  20251  ablfaclem3  20265  znidomb  21829  dvdsflsumcom  27479  chtublem  27502  vmasum  27507  logfac2  27508  bposlem6  27580  lgsdir  27623  lgsdilem2  27624  lgsne0  27626  lgsqrlem2  27638  lgsquadlem2  27672  2sqlem8  27717  2sqblem  27722  2sqmod  27727  oddpwdc  34921  nn0prpw  37033  lcmineqlem20  43018  lcmineqlem22  43020  aks4d1p3  43048  aks4d1p6  43051  aks4d1p8d2  43055  aks4d1p8  43057  primrootlekpowne0  43075  aks6d1c2lem4  43097  grpods  43164  unitscyglem2  43166  unitscyglem4  43168  gcdle1d  43309  gcdle2d  43310  nznngen  45244  etransclem41  47207