Theorem dvdsle 12321

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		simpr 110	. . 3 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑀 ≤ 𝑁) → 𝑀 ≤ 𝑁)
2	1	a1d 22	. 2 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑀 ≤ 𝑁) → (𝑀 ∥ 𝑁 → 𝑀 ≤ 𝑁))
3		simplll 533	. . . . . . 7 ⊢ ((((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → 𝑀 ∈ ℤ)
4		simpllr 534	. . . . . . 7 ⊢ ((((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → 𝑁 ∈ ℕ)
5		simpr 110	. . . . . . 7 ⊢ ((((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → 𝑛 ∈ ℤ)
6		simplr 528	. . . . . . 7 ⊢ ((((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → 𝑁 < 𝑀)
7	3, 4, 5, 6	dvdslelemd 12320	. . . . . 6 ⊢ ((((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → (𝑛 · 𝑀) ≠ 𝑁)
8	7	neneqd 2401	. . . . 5 ⊢ ((((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) ∧ 𝑛 ∈ ℤ) → ¬ (𝑛 · 𝑀) = 𝑁)
9	8	nrexdv 2603	. . . 4 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) → ¬ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)
10		simpll 527	. . . . 5 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) → 𝑀 ∈ ℤ)
11		simplr 528	. . . . . 6 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) → 𝑁 ∈ ℕ)
12	11	nnzd 9536	. . . . 5 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) → 𝑁 ∈ ℤ)
13		divides 12266	. . . . 5 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
14	10, 12, 13	syl2anc 411	. . . 4 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁))
15	9, 14	mtbird 677	. . 3 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) → ¬ 𝑀 ∥ 𝑁)
16	15	pm2.21d 622	. 2 ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ 𝑁 < 𝑀) → (𝑀 ∥ 𝑁 → 𝑀 ≤ 𝑁))
17		nnz 9433	. . 3 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℤ)
18		zlelttric 9459	. . 3 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ≤ 𝑁 ∨ 𝑁 < 𝑀))
19	17, 18	sylan2 286	. 2 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀 ≤ 𝑁 ∨ 𝑁 < 𝑀))
20	2, 16, 19	mpjaodan 802	1 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑀 ∥ 𝑁 → 𝑀 ≤ 𝑁))

Syntax hints:   → wi 4   ∧ wa 104   ↔ wb 105   ∨ wo 712   = wceq 1375   ∈ wcel 2180  ∃wrex 2489   class class class wbr 4062  (class class class)co 5974   · cmul 7972   < clt 8149   ≤ cle 8150  ℕcn 9078  ℤcz 9414   ∥ cdvds 12264

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 617  ax-in2 618  ax-io 713  ax-5 1473  ax-7 1474  ax-gen 1475  ax-ie1 1519  ax-ie2 1520  ax-8 1530  ax-10 1531  ax-11 1532  ax-i12 1533  ax-bndl 1535  ax-4 1536  ax-17 1552  ax-i9 1556  ax-ial 1560  ax-i5r 1561  ax-13 2182  ax-14 2183  ax-ext 2191  ax-sep 4181  ax-pow 4237  ax-pr 4272  ax-un 4501  ax-setind 4606  ax-cnex 8058  ax-resscn 8059  ax-1cn 8060  ax-1re 8061  ax-icn 8062  ax-addcl 8063  ax-addrcl 8064  ax-mulcl 8065  ax-mulrcl 8066  ax-addcom 8067  ax-mulcom 8068  ax-addass 8069  ax-mulass 8070  ax-distr 8071  ax-i2m1 8072  ax-0lt1 8073  ax-1rid 8074  ax-0id 8075  ax-rnegex 8076  ax-precex 8077  ax-cnre 8078  ax-pre-ltirr 8079  ax-pre-ltwlin 8080  ax-pre-lttrn 8081  ax-pre-apti 8082  ax-pre-ltadd 8083  ax-pre-mulgt0 8084  ax-pre-mulext 8085

This theorem depends on definitions:  df-bi 117  df-3or 984  df-3an 985  df-tru 1378  df-fal 1381  df-nf 1487  df-sb 1789  df-eu 2060  df-mo 2061  df-clab 2196  df-cleq 2202  df-clel 2205  df-nfc 2341  df-ne 2381  df-nel 2476  df-ral 2493  df-rex 2494  df-reu 2495  df-rmo 2496  df-rab 2497  df-v 2781  df-sbc 3009  df-csb 3105  df-dif 3179  df-un 3181  df-in 3183  df-ss 3190  df-pw 3631  df-sn 3652  df-pr 3653  df-op 3655  df-uni 3868  df-int 3903  df-iun 3946  df-br 4063  df-opab 4125  df-mpt 4126  df-id 4361  df-po 4364  df-iso 4365  df-xp 4702  df-rel 4703  df-cnv 4704  df-co 4705  df-dm 4706  df-rn 4707  df-res 4708  df-ima 4709  df-iota 5254  df-fun 5296  df-fn 5297  df-f 5298  df-fv 5302  df-riota 5927  df-ov 5977  df-oprab 5978  df-mpo 5979  df-1st 6256  df-2nd 6257  df-pnf 8151  df-mnf 8152  df-xr 8153  df-ltxr 8154  df-le 8155  df-sub 8287  df-neg 8288  df-reap 8690  df-ap 8697  df-div 8788  df-inn 9079  df-n0 9338  df-z 9415  df-q 9783  df-dvds 12265

This theorem is referenced by:  dvdsleabs  12322  dvdsssfz1  12329  fzm1ndvds  12333  fzo0dvdseq  12334  n2dvds1  12389  gcd1  12474  bezoutlemle  12495  dfgcd2  12501  gcdzeq  12509  bezoutr1  12520  lcmgcdlem  12565  ncoprmgcdne1b  12577  qredeq  12584  isprm3  12606  prmdvdsfz  12627  isprm5lem  12629  isprm6  12635  prmfac1  12640  pcpre1  12781  pcidlem  12812  pcprod  12835  pcfac  12839  pockthg  12846  1arith  12856  4sqlem11  12890  znidomb  14587  lgsdir  15679  lgsdilem2  15680  lgsne0  15682  lgsquadlem2  15722  2sqlem8  15767