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

Theorem dvdsle 12888
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  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( M  ||  N  ->  M  <_  N )
)

Proof of Theorem dvdsle
Dummy variable  n is distinct from all other variables.
StepHypRef Expression
1 breq2 4209 . . . . . . . . . . . . 13  |-  ( M  =  if ( M  e.  ZZ ,  M ,  1 )  -> 
( N  <  M  <->  N  <  if ( M  e.  ZZ ,  M ,  1 ) ) )
2 oveq2 6082 . . . . . . . . . . . . . 14  |-  ( M  =  if ( M  e.  ZZ ,  M ,  1 )  -> 
( n  x.  M
)  =  ( n  x.  if ( M  e.  ZZ ,  M ,  1 ) ) )
32neeq1d 2612 . . . . . . . . . . . . 13  |-  ( M  =  if ( M  e.  ZZ ,  M ,  1 )  -> 
( ( n  x.  M )  =/=  N  <->  ( n  x.  if ( M  e.  ZZ ,  M ,  1 ) )  =/=  N ) )
41, 3imbi12d 312 . . . . . . . . . . . 12  |-  ( M  =  if ( M  e.  ZZ ,  M ,  1 )  -> 
( ( N  < 
M  ->  ( n  x.  M )  =/=  N
)  <->  ( N  < 
if ( M  e.  ZZ ,  M , 
1 )  ->  (
n  x.  if ( M  e.  ZZ ,  M ,  1 ) )  =/=  N ) ) )
5 breq1 4208 . . . . . . . . . . . . 13  |-  ( N  =  if ( N  e.  NN ,  N ,  1 )  -> 
( N  <  if ( M  e.  ZZ ,  M ,  1 )  <-> 
if ( N  e.  NN ,  N , 
1 )  <  if ( M  e.  ZZ ,  M ,  1 ) ) )
6 neeq2 2608 . . . . . . . . . . . . 13  |-  ( N  =  if ( N  e.  NN ,  N ,  1 )  -> 
( ( n  x.  if ( M  e.  ZZ ,  M , 
1 ) )  =/= 
N  <->  ( n  x.  if ( M  e.  ZZ ,  M , 
1 ) )  =/= 
if ( N  e.  NN ,  N , 
1 ) ) )
75, 6imbi12d 312 . . . . . . . . . . . 12  |-  ( N  =  if ( N  e.  NN ,  N ,  1 )  -> 
( ( N  < 
if ( M  e.  ZZ ,  M , 
1 )  ->  (
n  x.  if ( M  e.  ZZ ,  M ,  1 ) )  =/=  N )  <-> 
( if ( N  e.  NN ,  N ,  1 )  < 
if ( M  e.  ZZ ,  M , 
1 )  ->  (
n  x.  if ( M  e.  ZZ ,  M ,  1 ) )  =/=  if ( N  e.  NN ,  N ,  1 ) ) ) )
8 oveq1 6081 . . . . . . . . . . . . . 14  |-  ( n  =  if ( n  e.  ZZ ,  n ,  1 )  -> 
( n  x.  if ( M  e.  ZZ ,  M ,  1 ) )  =  ( if ( n  e.  ZZ ,  n ,  1 )  x.  if ( M  e.  ZZ ,  M ,  1 ) ) )
98neeq1d 2612 . . . . . . . . . . . . 13  |-  ( n  =  if ( n  e.  ZZ ,  n ,  1 )  -> 
( ( n  x.  if ( M  e.  ZZ ,  M , 
1 ) )  =/= 
if ( N  e.  NN ,  N , 
1 )  <->  ( if ( n  e.  ZZ ,  n ,  1 )  x.  if ( M  e.  ZZ ,  M ,  1 ) )  =/=  if ( N  e.  NN ,  N ,  1 ) ) )
109imbi2d 308 . . . . . . . . . . . 12  |-  ( n  =  if ( n  e.  ZZ ,  n ,  1 )  -> 
( ( if ( N  e.  NN ,  N ,  1 )  <  if ( M  e.  ZZ ,  M ,  1 )  -> 
( n  x.  if ( M  e.  ZZ ,  M ,  1 ) )  =/=  if ( N  e.  NN ,  N ,  1 ) )  <->  ( if ( N  e.  NN ,  N ,  1 )  <  if ( M  e.  ZZ ,  M ,  1 )  -> 
( if ( n  e.  ZZ ,  n ,  1 )  x.  if ( M  e.  ZZ ,  M , 
1 ) )  =/= 
if ( N  e.  NN ,  N , 
1 ) ) ) )
11 1z 10304 . . . . . . . . . . . . . 14  |-  1  e.  ZZ
1211elimel 3784 . . . . . . . . . . . . 13  |-  if ( M  e.  ZZ ,  M ,  1 )  e.  ZZ
13 1nn 10004 . . . . . . . . . . . . . 14  |-  1  e.  NN
1413elimel 3784 . . . . . . . . . . . . 13  |-  if ( N  e.  NN ,  N ,  1 )  e.  NN
1511elimel 3784 . . . . . . . . . . . . 13  |-  if ( n  e.  ZZ ,  n ,  1 )  e.  ZZ
1612, 14, 15dvdslelem 12887 . . . . . . . . . . . 12  |-  ( if ( N  e.  NN ,  N ,  1 )  <  if ( M  e.  ZZ ,  M ,  1 )  -> 
( if ( n  e.  ZZ ,  n ,  1 )  x.  if ( M  e.  ZZ ,  M , 
1 ) )  =/= 
if ( N  e.  NN ,  N , 
1 ) )
174, 7, 10, 16dedth3h 3775 . . . . . . . . . . 11  |-  ( ( M  e.  ZZ  /\  N  e.  NN  /\  n  e.  ZZ )  ->  ( N  <  M  ->  (
n  x.  M )  =/=  N ) )
18173expia 1155 . . . . . . . . . 10  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( n  e.  ZZ  ->  ( N  <  M  ->  ( n  x.  M
)  =/=  N ) ) )
1918com23 74 . . . . . . . . 9  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( N  <  M  ->  ( n  e.  ZZ  ->  ( n  x.  M
)  =/=  N ) ) )
20193impia 1150 . . . . . . . 8  |-  ( ( M  e.  ZZ  /\  N  e.  NN  /\  N  <  M )  ->  (
n  e.  ZZ  ->  ( n  x.  M )  =/=  N ) )
2120imp 419 . . . . . . 7  |-  ( ( ( M  e.  ZZ  /\  N  e.  NN  /\  N  <  M )  /\  n  e.  ZZ )  ->  ( n  x.  M
)  =/=  N )
2221neneqd 2615 . . . . . 6  |-  ( ( ( M  e.  ZZ  /\  N  e.  NN  /\  N  <  M )  /\  n  e.  ZZ )  ->  -.  ( n  x.  M )  =  N )
2322nrexdv 2802 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  NN  /\  N  <  M )  ->  -.  E. n  e.  ZZ  (
n  x.  M )  =  N )
24 nnz 10296 . . . . . . 7  |-  ( N  e.  NN  ->  N  e.  ZZ )
25 divides 12847 . . . . . . 7  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( M  ||  N  <->  E. n  e.  ZZ  (
n  x.  M )  =  N ) )
2624, 25sylan2 461 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( M  ||  N  <->  E. n  e.  ZZ  (
n  x.  M )  =  N ) )
27263adant3 977 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  NN  /\  N  <  M )  ->  ( M  ||  N  <->  E. n  e.  ZZ  ( n  x.  M )  =  N ) )
2823, 27mtbird 293 . . . 4  |-  ( ( M  e.  ZZ  /\  N  e.  NN  /\  N  <  M )  ->  -.  M  ||  N )
29283expia 1155 . . 3  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( N  <  M  ->  -.  M  ||  N
) )
3029con2d 109 . 2  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( M  ||  N  ->  -.  N  <  M
) )
31 zre 10279 . . 3  |-  ( M  e.  ZZ  ->  M  e.  RR )
32 nnre 10000 . . 3  |-  ( N  e.  NN  ->  N  e.  RR )
33 lenlt 9147 . . 3  |-  ( ( M  e.  RR  /\  N  e.  RR )  ->  ( M  <_  N  <->  -.  N  <  M ) )
3431, 32, 33syl2an 464 . 2  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( M  <_  N  <->  -.  N  <  M ) )
3530, 34sylibrd 226 1  |-  ( ( M  e.  ZZ  /\  N  e.  NN )  ->  ( M  ||  N  ->  M  <_  N )
)
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 177    /\ wa 359    /\ w3a 936    = wceq 1652    e. wcel 1725    =/= wne 2599   E.wrex 2699   ifcif 3732   class class class wbr 4205  (class class class)co 6074   RRcr 8982   1c1 8984    x. cmul 8988    < clt 9113    <_ cle 9114   NNcn 9993   ZZcz 10275    || cdivides 12845
This theorem is referenced by:  dvdsleabs  12889  dvdseq  12890  fzm1ndvds  12894  fzo0dvdseq  12895  bitsfzolem  12939  bitsfzo  12940  bitsinv1lem  12946  gcd1  13025  bezoutlem4  13034  gcdeq  13045  isprm3  13081  qredeq  13099  isprm6  13102  isprm5  13105  maxprmfct  13106  prmfac1  13111  pcpre1  13209  pcidlem  13238  pcprod  13257  pcfac  13261  pockthg  13267  prmreclem1  13277  prmreclem3  13279  prmreclem5  13281  1arith  13288  4sqlem11  13316  gexcl2  15216  sylow1lem1  15225  sylow1lem5  15229  gexex  15461  ablfac1eu  15624  ablfaclem3  15638  znidomb  16835  sgmss  20882  dvdsflsumcom  20966  chtublem  20988  vmasum  20993  logfac2  20994  bposlem6  21066  lgsdir  21107  lgsdilem2  21108  lgsne0  21110  lgsqrlem2  21119  lgsquadlem2  21132  2sqlem8  21149  2sqblem  21154  nn0prpw  26318  bezoutr1  27043
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1555  ax-5 1566  ax-17 1626  ax-9 1666  ax-8 1687  ax-13 1727  ax-14 1729  ax-6 1744  ax-7 1749  ax-11 1761  ax-12 1950  ax-ext 2417  ax-sep 4323  ax-nul 4331  ax-pow 4370  ax-pr 4396  ax-un 4694  ax-resscn 9040  ax-1cn 9041  ax-icn 9042  ax-addcl 9043  ax-addrcl 9044  ax-mulcl 9045  ax-mulrcl 9046  ax-mulcom 9047  ax-addass 9048  ax-mulass 9049  ax-distr 9050  ax-i2m1 9051  ax-1ne0 9052  ax-1rid 9053  ax-rnegex 9054  ax-rrecex 9055  ax-cnre 9056  ax-pre-lttri 9057  ax-pre-lttrn 9058  ax-pre-ltadd 9059  ax-pre-mulgt0 9060
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1328  df-ex 1551  df-nf 1554  df-sb 1659  df-eu 2285  df-mo 2286  df-clab 2423  df-cleq 2429  df-clel 2432  df-nfc 2561  df-ne 2601  df-nel 2602  df-ral 2703  df-rex 2704  df-reu 2705  df-rab 2707  df-v 2951  df-sbc 3155  df-csb 3245  df-dif 3316  df-un 3318  df-in 3320  df-ss 3327  df-pss 3329  df-nul 3622  df-if 3733  df-pw 3794  df-sn 3813  df-pr 3814  df-tp 3815  df-op 3816  df-uni 4009  df-iun 4088  df-br 4206  df-opab 4260  df-mpt 4261  df-tr 4296  df-eprel 4487  df-id 4491  df-po 4496  df-so 4497  df-fr 4534  df-we 4536  df-ord 4577  df-on 4578  df-lim 4579  df-suc 4580  df-om 4839  df-xp 4877  df-rel 4878  df-cnv 4879  df-co 4880  df-dm 4881  df-rn 4882  df-res 4883  df-ima 4884  df-iota 5411  df-fun 5449  df-fn 5450  df-f 5451  df-f1 5452  df-fo 5453  df-f1o 5454  df-fv 5455  df-ov 6077  df-oprab 6078  df-mpt2 6079  df-riota 6542  df-recs 6626  df-rdg 6661  df-er 6898  df-en 7103  df-dom 7104  df-sdom 7105  df-pnf 9115  df-mnf 9116  df-xr 9117  df-ltxr 9118  df-le 9119  df-sub 9286  df-neg 9287  df-nn 9994  df-z 10276  df-dvds 12846
  Copyright terms: Public domain W3C validator