ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  gcddvds Unicode version
Theorem gcddvds 10355
Description: The gcd of two integers divides each of them. (Contributed by Paul Chapman, 21-Mar-2011.)
Assertion
Ref Expression
gcddvds |- ( ( M e. ZZ /\ N e. ZZ ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
Proof of Theorem gcddvds
Dummy variables n x y z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 0z 8362 . . . . . 6 |- 0 e. ZZ
2 dvds0 10210 . . . . . 6 |- ( 0 e. ZZ -> 0 || 0 )
31, 2ax-mp 7 . . . . 5 |- 0 || 0
4 breq2 3789 . . . . . . 7 |- ( M = 0 -> ( 0 || M <-> 0 || 0 ) )
5 breq2 3789 . . . . . . 7 |- ( N = 0 -> ( 0 || N <-> 0 || 0 ) )
64, 5bi2anan9 570 . . . . . 6 |- ( ( M = 0 /\ N = 0 ) -> ( ( 0 || M /\ 0 || N ) <-> ( 0 || 0 /\ 0 || 0 ) ) )
7 anidm 388 . . . . . 6 |- ( ( 0 || 0 /\ 0 || 0 ) <-> 0 || 0 )
86, 7syl6bb 194 . . . . 5 |- ( ( M = 0 /\ N = 0 ) -> ( ( 0 || M /\ 0 || N ) <-> 0 || 0 ) )
93, 8mpbiri 166 . . . 4 |- ( ( M = 0 /\ N = 0 ) -> ( 0 || M /\ 0 || N ) )
10 oveq12 5541 . . . . . . 7 |- ( ( M = 0 /\ N = 0 ) -> ( M gcd N ) = ( 0 gcd 0 ) )
11 gcd0val 10352 . . . . . . 7 |- ( 0 gcd 0 ) = 0
1210, 11syl6eq 2129 . . . . . 6 |- ( ( M = 0 /\ N = 0 ) -> ( M gcd N ) = 0 )
1312breq1d 3795 . . . . 5 |- ( ( M = 0 /\ N = 0 ) -> ( ( M gcd N ) || M <-> 0 || M ) )
1412breq1d 3795 . . . . 5 |- ( ( M = 0 /\ N = 0 ) -> ( ( M gcd N ) || N <-> 0 || N ) )
1513, 14anbi12d 456 . . . 4 |- ( ( M = 0 /\ N = 0 ) -> ( ( ( M gcd N ) || M /\ ( M gcd N ) || N ) <-> ( 0 || M /\ 0 || N ) ) )
169, 15mpbird 165 . . 3 |- ( ( M = 0 /\ N = 0 ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
1716adantl 271 . 2 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ ( M = 0 /\ N = 0 ) ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
18 gcdn0val 10353 . . . 4 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( M gcd N ) = sup ( { n e. ZZ | ( n || M /\ n || N ) } , RR , < ) )
19 zssre 8358 . . . . . 6 |- ZZ C_ RR
20 gcdsupex 10349 . . . . . 6 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> E. x e. ZZ ( A. y e. { n e. ZZ | ( n || M /\ n || N ) } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ( n || M /\ n || N ) } y < z ) ) )
21 ssrexv 3059 . . . . . 6 |- ( ZZ C_ RR -> ( E. x e. ZZ ( A. y e. { n e. ZZ | ( n || M /\ n || N ) } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ( n || M /\ n || N ) } y < z ) ) -> E. x e. RR ( A. y e. { n e. ZZ | ( n || M /\ n || N ) } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ( n || M /\ n || N ) } y < z ) ) ) )
2219, 20, 21mpsyl 64 . . . . 5 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> E. x e. RR ( A. y e. { n e. ZZ | ( n || M /\ n || N ) } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ( n || M /\ n || N ) } y < z ) ) )
23 ssrab2 3079 . . . . . 6 |- { n e. ZZ | ( n || M /\ n || N ) } C_ ZZ
2423a1i 9 . . . . 5 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> { n e. ZZ | ( n || M /\ n || N ) } C_ ZZ )
2522, 24suprzclex 8445 . . . 4 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> sup ( { n e. ZZ | ( n || M /\ n || N ) } , RR , < ) e. { n e. ZZ | ( n || M /\ n || N ) } )
2618, 25eqeltrd 2155 . . 3 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( M gcd N ) e. { n e. ZZ | ( n || M /\ n || N ) } )
27 gcdn0cl 10354 . . . . 5 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( M gcd N ) e. NN )
2827nnzd 8468 . . . 4 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( M gcd N ) e. ZZ )
29 breq1 3788 . . . . . 6 |- ( n = ( M gcd N ) -> ( n || M <-> ( M gcd N ) || M ) )
30 breq1 3788 . . . . . 6 |- ( n = ( M gcd N ) -> ( n || N <-> ( M gcd N ) || N ) )
3129, 30anbi12d 456 . . . . 5 |- ( n = ( M gcd N ) -> ( ( n || M /\ n || N ) <-> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) ) )
3231elrab3 2750 . . . 4 |- ( ( M gcd N ) e. ZZ -> ( ( M gcd N ) e. { n e. ZZ | ( n || M /\ n || N ) } <-> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) ) )
3328, 32syl 14 . . 3 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( ( M gcd N ) e. { n e. ZZ | ( n || M /\ n || N ) } <-> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) ) )
3426, 33mpbid 145 . 2 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
35 gcdmndc 10340 . . 3 |- ( ( M e. ZZ /\ N e. ZZ ) -> DECID ( M = 0 /\ N = 0 ) )
36 exmiddc 777 . . 3 |- (DECID ( M = 0 /\ N = 0 ) -> ( ( M = 0 /\ N = 0 ) \/ -. ( M = 0 /\ N = 0 ) ) )
3735, 36syl 14 . 2 |- ( ( M e. ZZ /\ N e. ZZ ) -> ( ( M = 0 /\ N = 0 ) \/ -. ( M = 0 /\ N = 0 ) ) )
3817, 34, 37mpjaodan 744 1 |- ( ( M e. ZZ /\ N e. ZZ ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
Colors of variables: wff set class
Syntax hints:   -. wn 3   -> wi 4   /\ wa 102   <-> wb 103   \/ wo 661  DECID wdc 775   = wceq 1284   e. wcel 1433   A.wral 2348   E.wrex 2349   {crab 2352   C_ wss 2973   class class class wbr 3785  (class class class)co 5532   supcsup 6395   RRcr 6980   0cc0 6981   < clt 7153   ZZcz 8351   || cdvds 10195   gcd cgcd 10338
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 576  ax-in2 577  ax-io 662  ax-5 1376  ax-7 1377  ax-gen 1378  ax-ie1 1422  ax-ie2 1423  ax-8 1435  ax-10 1436  ax-11 1437  ax-i12 1438  ax-bndl 1439  ax-4 1440  ax-13 1444  ax-14 1445  ax-17 1459  ax-i9 1463  ax-ial 1467  ax-i5r 1468  ax-ext 2063  ax-coll 3893  ax-sep 3896  ax-nul 3904  ax-pow 3948  ax-pr 3964  ax-un 4188  ax-setind 4280  ax-iinf 4329  ax-cnex 7067  ax-resscn 7068  ax-1cn 7069  ax-1re 7070  ax-icn 7071  ax-addcl 7072  ax-addrcl 7073  ax-mulcl 7074  ax-mulrcl 7075  ax-addcom 7076  ax-mulcom 7077  ax-addass 7078  ax-mulass 7079  ax-distr 7080  ax-i2m1 7081  ax-0lt1 7082  ax-1rid 7083  ax-0id 7084  ax-rnegex 7085  ax-precex 7086  ax-cnre 7087  ax-pre-ltirr 7088  ax-pre-ltwlin 7089  ax-pre-lttrn 7090  ax-pre-apti 7091  ax-pre-ltadd 7092  ax-pre-mulgt0 7093  ax-pre-mulext 7094  ax-arch 7095  ax-caucvg 7096
This theorem depends on definitions:  df-bi 115  df-dc 776  df-3or 920  df-3an 921  df-tru 1287  df-fal 1290  df-nf 1390  df-sb 1686  df-eu 1944  df-mo 1945  df-clab 2068  df-cleq 2074  df-clel 2077  df-nfc 2208  df-ne 2246  df-nel 2340  df-ral 2353  df-rex 2354  df-reu 2355  df-rmo 2356  df-rab 2357  df-v 2603  df-sbc 2816  df-csb 2909  df-dif 2975  df-un 2977  df-in 2979  df-ss 2986  df-nul 3252  df-if 3352  df-pw 3384  df-sn 3404  df-pr 3405  df-op 3407  df-uni 3602  df-int 3637  df-iun 3680  df-br 3786  df-opab 3840  df-mpt 3841  df-tr 3876  df-id 4048  df-po 4051  df-iso 4052  df-iord 4121  df-on 4123  df-suc 4126  df-iom 4332  df-xp 4369  df-rel 4370  df-cnv 4371  df-co 4372  df-dm 4373  df-rn 4374  df-res 4375  df-ima 4376  df-iota 4887  df-fun 4924  df-fn 4925  df-f 4926  df-f1 4927  df-fo 4928  df-f1o 4929  df-fv 4930  df-riota 5488  df-ov 5535  df-oprab 5536  df-mpt2 5537  df-1st 5787  df-2nd 5788  df-recs 5943  df-frec 6001  df-sup 6397  df-pnf 7155  df-mnf 7156  df-xr 7157  df-ltxr 7158  df-le 7159  df-sub 7281  df-neg 7282  df-reap 7675  df-ap 7682  df-div 7761  df-inn 8040  df-2 8098  df-3 8099  df-4 8100  df-n0 8289  df-z 8352  df-uz 8620  df-q 8705  df-rp 8735  df-fz 9030  df-fzo 9153  df-fl 9274  df-mod 9325  df-iseq 9432  df-iexp 9476  df-cj 9729  df-re 9730  df-im 9731  df-rsqrt 9884  df-abs 9885  df-dvds 10196  df-gcd 10339
This theorem is referenced by:  zeqzmulgcd  10362  divgcdz  10363  divgcdnn  10366  gcd0id  10370  gcdneg  10373  gcdaddm  10375  gcd1  10378  dvdsgcdb  10402  dfgcd2  10403  mulgcd  10405  gcdzeq  10411  dvdsmulgcd  10414  sqgcd  10418  dvdssqlem  10419  bezoutr  10421  gcddvdslcm  10455  lcmgcdlem  10459  lcmgcdeq  10465  coprmgcdb  10470  ncoprmgcdne1b  10471  mulgcddvds  10476  rpmulgcd2  10477  qredeu  10479  rpdvds  10481  divgcdcoprm0  10483  divgcdodd  10522  coprm  10523  rpexp  10532
  Copyright terms: Public domain W3C validator