ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  gcddvds Unicode version
Theorem gcddvds 11881
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 9193 . . . . . 6 |- 0 e. ZZ
2 dvds0 11732 . . . . . 6 |- ( 0 e. ZZ -> 0 || 0 )
31, 2ax-mp 5 . . . . 5 |- 0 || 0
4 breq2 3980 . . . . . . 7 |- ( M = 0 -> ( 0 || M <-> 0 || 0 ) )
5 breq2 3980 . . . . . . 7 |- ( N = 0 -> ( 0 || N <-> 0 || 0 ) )
64, 5bi2anan9 596 . . . . . 6 |- ( ( M = 0 /\ N = 0 ) -> ( ( 0 || M /\ 0 || N ) <-> ( 0 || 0 /\ 0 || 0 ) ) )
7 anidm 394 . . . . . 6 |- ( ( 0 || 0 /\ 0 || 0 ) <-> 0 || 0 )
86, 7bitrdi 195 . . . . 5 |- ( ( M = 0 /\ N = 0 ) -> ( ( 0 || M /\ 0 || N ) <-> 0 || 0 ) )
93, 8mpbiri 167 . . . 4 |- ( ( M = 0 /\ N = 0 ) -> ( 0 || M /\ 0 || N ) )
10 oveq12 5845 . . . . . . 7 |- ( ( M = 0 /\ N = 0 ) -> ( M gcd N ) = ( 0 gcd 0 ) )
11 gcd0val 11878 . . . . . . 7 |- ( 0 gcd 0 ) = 0
1210, 11eqtrdi 2213 . . . . . 6 |- ( ( M = 0 /\ N = 0 ) -> ( M gcd N ) = 0 )
1312breq1d 3986 . . . . 5 |- ( ( M = 0 /\ N = 0 ) -> ( ( M gcd N ) || M <-> 0 || M ) )
1412breq1d 3986 . . . . 5 |- ( ( M = 0 /\ N = 0 ) -> ( ( M gcd N ) || N <-> 0 || N ) )
1513, 14anbi12d 465 . . . 4 |- ( ( M = 0 /\ N = 0 ) -> ( ( ( M gcd N ) || M /\ ( M gcd N ) || N ) <-> ( 0 || M /\ 0 || N ) ) )
169, 15mpbird 166 . . 3 |- ( ( M = 0 /\ N = 0 ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
1716adantl 275 . 2 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ ( M = 0 /\ N = 0 ) ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
18 gcdn0val 11879 . . . 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 9189 . . . . . 6 |- ZZ C_ RR
20 gcdsupex 11875 . . . . . 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 3202 . . . . . 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 65 . . . . 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 3222 . . . . . 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 9280 . . . 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 2241 . . 3 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( M gcd N ) e. { n e. ZZ | ( n || M /\ n || N ) } )
27 gcdn0cl 11880 . . . . 5 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( M gcd N ) e. NN )
2827nnzd 9303 . . . 4 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( M gcd N ) e. ZZ )
29 breq1 3979 . . . . . 6 |- ( n = ( M gcd N ) -> ( n || M <-> ( M gcd N ) || M ) )
30 breq1 3979 . . . . . 6 |- ( n = ( M gcd N ) -> ( n || N <-> ( M gcd N ) || N ) )
3129, 30anbi12d 465 . . . . 5 |- ( n = ( M gcd N ) -> ( ( n || M /\ n || N ) <-> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) ) )
3231elrab3 2878 . . . 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 146 . 2 |- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 /\ N = 0 ) ) -> ( ( M gcd N ) || M /\ ( M gcd N ) || N ) )
35 gcdmndc 11862 . . 3 |- ( ( M e. ZZ /\ N e. ZZ ) -> DECID ( M = 0 /\ N = 0 ) )
36 exmiddc 826 . . 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 788 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 103   <-> wb 104   \/ wo 698  DECID wdc 824   = wceq 1342   e. wcel 2135   A.wral 2442   E.wrex 2443   {crab 2446   C_ wss 3111   class class class wbr 3976  (class class class)co 5836   supcsup 6938   RRcr 7743   0cc0 7744   < clt 7924   ZZcz 9182   || cdvds 11713   gcd cgcd 11860
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1434  ax-7 1435  ax-gen 1436  ax-ie1 1480  ax-ie2 1481  ax-8 1491  ax-10 1492  ax-11 1493  ax-i12 1494  ax-bndl 1496  ax-4 1497  ax-17 1513  ax-i9 1517  ax-ial 1521  ax-i5r 1522  ax-13 2137  ax-14 2138  ax-ext 2146  ax-coll 4091  ax-sep 4094  ax-nul 4102  ax-pow 4147  ax-pr 4181  ax-un 4405  ax-setind 4508  ax-iinf 4559  ax-cnex 7835  ax-resscn 7836  ax-1cn 7837  ax-1re 7838  ax-icn 7839  ax-addcl 7840  ax-addrcl 7841  ax-mulcl 7842  ax-mulrcl 7843  ax-addcom 7844  ax-mulcom 7845  ax-addass 7846  ax-mulass 7847  ax-distr 7848  ax-i2m1 7849  ax-0lt1 7850  ax-1rid 7851  ax-0id 7852  ax-rnegex 7853  ax-precex 7854  ax-cnre 7855  ax-pre-ltirr 7856  ax-pre-ltwlin 7857  ax-pre-lttrn 7858  ax-pre-apti 7859  ax-pre-ltadd 7860  ax-pre-mulgt0 7861  ax-pre-mulext 7862  ax-arch 7863  ax-caucvg 7864
This theorem depends on definitions:  df-bi 116  df-dc 825  df-3or 968  df-3an 969  df-tru 1345  df-fal 1348  df-nf 1448  df-sb 1750  df-eu 2016  df-mo 2017  df-clab 2151  df-cleq 2157  df-clel 2160  df-nfc 2295  df-ne 2335  df-nel 2430  df-ral 2447  df-rex 2448  df-reu 2449  df-rmo 2450  df-rab 2451  df-v 2723  df-sbc 2947  df-csb 3041  df-dif 3113  df-un 3115  df-in 3117  df-ss 3124  df-nul 3405  df-if 3516  df-pw 3555  df-sn 3576  df-pr 3577  df-op 3579  df-uni 3784  df-int 3819  df-iun 3862  df-br 3977  df-opab 4038  df-mpt 4039  df-tr 4075  df-id 4265  df-po 4268  df-iso 4269  df-iord 4338  df-on 4340  df-ilim 4341  df-suc 4343  df-iom 4562  df-xp 4604  df-rel 4605  df-cnv 4606  df-co 4607  df-dm 4608  df-rn 4609  df-res 4610  df-ima 4611  df-iota 5147  df-fun 5184  df-fn 5185  df-f 5186  df-f1 5187  df-fo 5188  df-f1o 5189  df-fv 5190  df-riota 5792  df-ov 5839  df-oprab 5840  df-mpo 5841  df-1st 6100  df-2nd 6101  df-recs 6264  df-frec 6350  df-sup 6940  df-pnf 7926  df-mnf 7927  df-xr 7928  df-ltxr 7929  df-le 7930  df-sub 8062  df-neg 8063  df-reap 8464  df-ap 8471  df-div 8560  df-inn 8849  df-2 8907  df-3 8908  df-4 8909  df-n0 9106  df-z 9183  df-uz 9458  df-q 9549  df-rp 9581  df-fz 9936  df-fzo 10068  df-fl 10195  df-mod 10248  df-seqfrec 10371  df-exp 10445  df-cj 10770  df-re 10771  df-im 10772  df-rsqrt 10926  df-abs 10927  df-dvds 11714  df-gcd 11861
This theorem is referenced by:  zeqzmulgcd  11888  divgcdz  11889  divgcdnn  11893  gcd0id  11897  gcdneg  11900  gcdaddm  11902  gcd1  11905  dvdsgcdb  11931  dfgcd2  11932  mulgcd  11934  gcdzeq  11940  dvdsmulgcd  11943  sqgcd  11947  dvdssqlem  11948  bezoutr  11950  gcddvdslcm  11984  lcmgcdlem  11988  lcmgcdeq  11994  coprmgcdb  11999  ncoprmgcdne1b  12000  mulgcddvds  12005  rpmulgcd2  12006  qredeu  12008  rpdvds  12010  divgcdcoprm0  12012  divgcdodd  12052  coprm  12053  rpexp  12062  divnumden  12105  phimullem  12134  hashgcdlem  12147  hashgcdeq  12148  phisum  12149  pythagtriplem4  12177  pythagtriplem19  12191  pcgcd1  12236  pc2dvds  12238
  Copyright terms: Public domain W3C validator