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

Theorem dvdsgcd 12964
Description: An integer which divides each of two others also divides their gcd. (Contributed by Paul Chapman, 22-Jun-2011.) (Revised by Mario Carneiro, 30-May-2014.)
Assertion
Ref Expression
dvdsgcd  |-  ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  ->  (
( K  ||  M  /\  K  ||  N )  ->  K  ||  ( M  gcd  N ) ) )

Proof of Theorem dvdsgcd
Dummy variables  x  y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 bezout 12963 . . 3  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  E. x  e.  ZZ  E. y  e.  ZZ  ( M  gcd  N )  =  ( ( M  x.  x )  +  ( N  x.  y ) ) )
213adant1 975 . 2  |-  ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  ->  E. x  e.  ZZ  E. y  e.  ZZ  ( M  gcd  N )  =  ( ( M  x.  x )  +  ( N  x.  y ) ) )
3 dvds2ln 12801 . . . . . . . . 9  |-  ( ( ( x  e.  ZZ  /\  y  e.  ZZ )  /\  ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ ) )  -> 
( ( K  ||  M  /\  K  ||  N
)  ->  K  ||  (
( x  x.  M
)  +  ( y  x.  N ) ) ) )
433impia 1150 . . . . . . . 8  |-  ( ( ( x  e.  ZZ  /\  y  e.  ZZ )  /\  ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N ) )  ->  K  ||  ( ( x  x.  M )  +  ( y  x.  N
) ) )
543coml 1160 . . . . . . 7  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  ->  K  ||  ( ( x  x.  M )  +  ( y  x.  N
) ) )
6 simp3l 985 . . . . . . . . 9  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  ->  x  e.  ZZ )
7 simp12 988 . . . . . . . . 9  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  ->  M  e.  ZZ )
8 zcn 10213 . . . . . . . . . 10  |-  ( x  e.  ZZ  ->  x  e.  CC )
9 zcn 10213 . . . . . . . . . 10  |-  ( M  e.  ZZ  ->  M  e.  CC )
10 mulcom 9003 . . . . . . . . . 10  |-  ( ( x  e.  CC  /\  M  e.  CC )  ->  ( x  x.  M
)  =  ( M  x.  x ) )
118, 9, 10syl2an 464 . . . . . . . . 9  |-  ( ( x  e.  ZZ  /\  M  e.  ZZ )  ->  ( x  x.  M
)  =  ( M  x.  x ) )
126, 7, 11syl2anc 643 . . . . . . . 8  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  -> 
( x  x.  M
)  =  ( M  x.  x ) )
13 simp3r 986 . . . . . . . . 9  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  -> 
y  e.  ZZ )
14 simp13 989 . . . . . . . . 9  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  ->  N  e.  ZZ )
15 zcn 10213 . . . . . . . . . 10  |-  ( y  e.  ZZ  ->  y  e.  CC )
16 zcn 10213 . . . . . . . . . 10  |-  ( N  e.  ZZ  ->  N  e.  CC )
17 mulcom 9003 . . . . . . . . . 10  |-  ( ( y  e.  CC  /\  N  e.  CC )  ->  ( y  x.  N
)  =  ( N  x.  y ) )
1815, 16, 17syl2an 464 . . . . . . . . 9  |-  ( ( y  e.  ZZ  /\  N  e.  ZZ )  ->  ( y  x.  N
)  =  ( N  x.  y ) )
1913, 14, 18syl2anc 643 . . . . . . . 8  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  -> 
( y  x.  N
)  =  ( N  x.  y ) )
2012, 19oveq12d 6032 . . . . . . 7  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  -> 
( ( x  x.  M )  +  ( y  x.  N ) )  =  ( ( M  x.  x )  +  ( N  x.  y ) ) )
215, 20breqtrd 4171 . . . . . 6  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  ->  K  ||  ( ( M  x.  x )  +  ( N  x.  y
) ) )
22 breq2 4151 . . . . . 6  |-  ( ( M  gcd  N )  =  ( ( M  x.  x )  +  ( N  x.  y
) )  ->  ( K  ||  ( M  gcd  N )  <->  K  ||  ( ( M  x.  x )  +  ( N  x.  y ) ) ) )
2321, 22syl5ibrcom 214 . . . . 5  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N )  /\  ( x  e.  ZZ  /\  y  e.  ZZ ) )  -> 
( ( M  gcd  N )  =  ( ( M  x.  x )  +  ( N  x.  y ) )  ->  K  ||  ( M  gcd  N ) ) )
24233expia 1155 . . . 4  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N ) )  ->  ( (
x  e.  ZZ  /\  y  e.  ZZ )  ->  ( ( M  gcd  N )  =  ( ( M  x.  x )  +  ( N  x.  y ) )  ->  K  ||  ( M  gcd  N ) ) ) )
2524rexlimdvv 2773 . . 3  |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  ( K  ||  M  /\  K  ||  N ) )  ->  ( E. x  e.  ZZ  E. y  e.  ZZ  ( M  gcd  N )  =  ( ( M  x.  x )  +  ( N  x.  y ) )  ->  K  ||  ( M  gcd  N ) ) )
2625ex 424 . 2  |-  ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  ->  (
( K  ||  M  /\  K  ||  N )  ->  ( E. x  e.  ZZ  E. y  e.  ZZ  ( M  gcd  N )  =  ( ( M  x.  x )  +  ( N  x.  y ) )  ->  K  ||  ( M  gcd  N ) ) ) )
272, 26mpid 39 1  |-  ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  ->  (
( K  ||  M  /\  K  ||  N )  ->  K  ||  ( M  gcd  N ) ) )
Colors of variables: wff set class
Syntax hints:    -> wi 4    /\ wa 359    /\ w3a 936    = wceq 1649    e. wcel 1717   E.wrex 2644   class class class wbr 4147  (class class class)co 6014   CCcc 8915    + caddc 8920    x. cmul 8922   ZZcz 10208    || cdivides 12773    gcd cgcd 12927
This theorem is referenced by:  dvdsgcdb  12965  mulgcd  12967  coprmdvds  13023  mulgcddvds  13025  rpmulgcd2  13026  rpexp  13041  pythagtriplem4  13114  pcgcd1  13171  pockthlem  13194  odadd2  15385  ablfacrp  15545  mumul  20825  lgsne0  20978  lgsquad2lem2  21004
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-13 1719  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2362  ax-sep 4265  ax-nul 4273  ax-pow 4312  ax-pr 4338  ax-un 4635  ax-cnex 8973  ax-resscn 8974  ax-1cn 8975  ax-icn 8976  ax-addcl 8977  ax-addrcl 8978  ax-mulcl 8979  ax-mulrcl 8980  ax-mulcom 8981  ax-addass 8982  ax-mulass 8983  ax-distr 8984  ax-i2m1 8985  ax-1ne0 8986  ax-1rid 8987  ax-rnegex 8988  ax-rrecex 8989  ax-cnre 8990  ax-pre-lttri 8991  ax-pre-lttrn 8992  ax-pre-ltadd 8993  ax-pre-mulgt0 8994  ax-pre-sup 8995
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2236  df-mo 2237  df-clab 2368  df-cleq 2374  df-clel 2377  df-nfc 2506  df-ne 2546  df-nel 2547  df-ral 2648  df-rex 2649  df-reu 2650  df-rmo 2651  df-rab 2652  df-v 2895  df-sbc 3099  df-csb 3189  df-dif 3260  df-un 3262  df-in 3264  df-ss 3271  df-pss 3273  df-nul 3566  df-if 3677  df-pw 3738  df-sn 3757  df-pr 3758  df-tp 3759  df-op 3760  df-uni 3952  df-iun 4031  df-br 4148  df-opab 4202  df-mpt 4203  df-tr 4238  df-eprel 4429  df-id 4433  df-po 4438  df-so 4439  df-fr 4476  df-we 4478  df-ord 4519  df-on 4520  df-lim 4521  df-suc 4522  df-om 4780  df-xp 4818  df-rel 4819  df-cnv 4820  df-co 4821  df-dm 4822  df-rn 4823  df-res 4824  df-ima 4825  df-iota 5352  df-fun 5390  df-fn 5391  df-f 5392  df-f1 5393  df-fo 5394  df-f1o 5395  df-fv 5396  df-ov 6017  df-oprab 6018  df-mpt2 6019  df-2nd 6283  df-riota 6479  df-recs 6563  df-rdg 6598  df-er 6835  df-en 7040  df-dom 7041  df-sdom 7042  df-sup 7375  df-pnf 9049  df-mnf 9050  df-xr 9051  df-ltxr 9052  df-le 9053  df-sub 9219  df-neg 9220  df-div 9604  df-nn 9927  df-2 9984  df-3 9985  df-n0 10148  df-z 10209  df-uz 10415  df-rp 10539  df-fl 11123  df-mod 11172  df-seq 11245  df-exp 11304  df-cj 11825  df-re 11826  df-im 11827  df-sqr 11961  df-abs 11962  df-dvds 12774  df-gcd 12928
  Copyright terms: Public domain W3C validator