ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  lcmgcd Unicode version

Theorem lcmgcd 10935
Description: The product of two numbers' least common multiple and greatest common divisor is the absolute value of the product of the two numbers. In particular, that absolute value is the least common multiple of two coprime numbers, for which  ( M  gcd  N
)  =  1.

Multiple methods exist for proving this, and it is often proven either as a consequence of the fundamental theorem of arithmetic or of Bézout's identity bezout 10875; see e.g. https://proofwiki.org/wiki/Product_of_GCD_and_LCM and https://math.stackexchange.com/a/470827. This proof uses the latter to first confirm it for positive integers  M and 
N (the "Second Proof" in the above Stack Exchange page), then shows that implies it for all nonzero integer inputs, then finally uses lcm0val 10922 to show it applies when either or both inputs are zero. (Contributed by Steve Rodriguez, 20-Jan-2020.)

Assertion
Ref Expression
lcmgcd  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( M lcm  N
)  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  N )
) )

Proof of Theorem lcmgcd
StepHypRef Expression
1 gcdcl 10833 . . . . . . . 8  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( M  gcd  N
)  e.  NN0 )
21nn0cnd 8661 . . . . . . 7  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( M  gcd  N
)  e.  CC )
32mul02d 7814 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( 0  x.  ( M  gcd  N ) )  =  0 )
4 0z 8694 . . . . . . . . . 10  |-  0  e.  ZZ
5 lcmcom 10921 . . . . . . . . . 10  |-  ( ( N  e.  ZZ  /\  0  e.  ZZ )  ->  ( N lcm  0 )  =  ( 0 lcm  N
) )
64, 5mpan2 416 . . . . . . . . 9  |-  ( N  e.  ZZ  ->  ( N lcm  0 )  =  ( 0 lcm  N ) )
7 lcm0val 10922 . . . . . . . . 9  |-  ( N  e.  ZZ  ->  ( N lcm  0 )  =  0 )
86, 7eqtr3d 2119 . . . . . . . 8  |-  ( N  e.  ZZ  ->  (
0 lcm  N )  =  0 )
98adantl 271 . . . . . . 7  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( 0 lcm  N )  =  0 )
109oveq1d 5628 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( 0 lcm  N
)  x.  ( M  gcd  N ) )  =  ( 0  x.  ( M  gcd  N
) ) )
11 zcn 8688 . . . . . . . . 9  |-  ( N  e.  ZZ  ->  N  e.  CC )
1211adantl 271 . . . . . . . 8  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  N  e.  CC )
1312mul02d 7814 . . . . . . 7  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( 0  x.  N
)  =  0 )
1413abs00bd 10394 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( abs `  (
0  x.  N ) )  =  0 )
153, 10, 143eqtr4d 2127 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( 0 lcm  N
)  x.  ( M  gcd  N ) )  =  ( abs `  (
0  x.  N ) ) )
1615adantr 270 . . . 4  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  M  =  0 )  ->  ( (
0 lcm  N )  x.  ( M  gcd  N
) )  =  ( abs `  ( 0  x.  N ) ) )
17 simpr 108 . . . . . 6  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  M  =  0 )  ->  M  = 
0 )
1817oveq1d 5628 . . . . 5  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  M  =  0 )  ->  ( M lcm  N )  =  ( 0 lcm 
N ) )
1918oveq1d 5628 . . . 4  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  M  =  0 )  ->  ( ( M lcm  N )  x.  ( M  gcd  N ) )  =  ( ( 0 lcm 
N )  x.  ( M  gcd  N ) ) )
2017oveq1d 5628 . . . . 5  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  M  =  0 )  ->  ( M  x.  N )  =  ( 0  x.  N ) )
2120fveq2d 5272 . . . 4  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  M  =  0 )  ->  ( abs `  ( M  x.  N
) )  =  ( abs `  ( 0  x.  N ) ) )
2216, 19, 213eqtr4d 2127 . . 3  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  M  =  0 )  ->  ( ( M lcm  N )  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  N )
) )
23 lcm0val 10922 . . . . . . . 8  |-  ( M  e.  ZZ  ->  ( M lcm  0 )  =  0 )
2423adantr 270 . . . . . . 7  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( M lcm  0 )  =  0 )
2524oveq1d 5628 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( M lcm  0
)  x.  ( M  gcd  N ) )  =  ( 0  x.  ( M  gcd  N
) ) )
26 zcn 8688 . . . . . . . . 9  |-  ( M  e.  ZZ  ->  M  e.  CC )
2726adantr 270 . . . . . . . 8  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  M  e.  CC )
2827mul01d 7815 . . . . . . 7  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( M  x.  0 )  =  0 )
2928abs00bd 10394 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( abs `  ( M  x.  0 ) )  =  0 )
303, 25, 293eqtr4d 2127 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( M lcm  0
)  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  0 ) ) )
3130adantr 270 . . . 4  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  N  =  0 )  ->  ( ( M lcm  0 )  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  0 ) ) )
32 simpr 108 . . . . . 6  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  N  =  0 )  ->  N  = 
0 )
3332oveq2d 5629 . . . . 5  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  N  =  0 )  ->  ( M lcm  N )  =  ( M lcm  0 ) )
3433oveq1d 5628 . . . 4  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  N  =  0 )  ->  ( ( M lcm  N )  x.  ( M  gcd  N ) )  =  ( ( M lcm  0 )  x.  ( M  gcd  N ) ) )
3532oveq2d 5629 . . . . 5  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  N  =  0 )  ->  ( M  x.  N )  =  ( M  x.  0 ) )
3635fveq2d 5272 . . . 4  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  N  =  0 )  ->  ( abs `  ( M  x.  N
) )  =  ( abs `  ( M  x.  0 ) ) )
3731, 34, 363eqtr4d 2127 . . 3  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  N  =  0 )  ->  ( ( M lcm  N )  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  N )
) )
3822, 37jaodan 744 . 2  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  ( M  =  0  \/  N  =  0 ) )  -> 
( ( M lcm  N
)  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  N )
) )
39 neanior 2338 . . . . 5  |-  ( ( M  =/=  0  /\  N  =/=  0 )  <->  -.  ( M  =  0  \/  N  =  0 ) )
40 nnabscl 10428 . . . . . . 7  |-  ( ( M  e.  ZZ  /\  M  =/=  0 )  -> 
( abs `  M
)  e.  NN )
41 nnabscl 10428 . . . . . . 7  |-  ( ( N  e.  ZZ  /\  N  =/=  0 )  -> 
( abs `  N
)  e.  NN )
4240, 41anim12i 331 . . . . . 6  |-  ( ( ( M  e.  ZZ  /\  M  =/=  0 )  /\  ( N  e.  ZZ  /\  N  =/=  0 ) )  -> 
( ( abs `  M
)  e.  NN  /\  ( abs `  N )  e.  NN ) )
4342an4s 553 . . . . 5  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  ( M  =/=  0  /\  N  =/=  0 ) )  -> 
( ( abs `  M
)  e.  NN  /\  ( abs `  N )  e.  NN ) )
4439, 43sylan2br 282 . . . 4  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  \/  N  =  0 ) )  ->  ( ( abs `  M )  e.  NN  /\  ( abs `  N
)  e.  NN ) )
45 lcmgcdlem 10934 . . . . 5  |-  ( ( ( abs `  M
)  e.  NN  /\  ( abs `  N )  e.  NN )  -> 
( ( ( ( abs `  M ) lcm  ( abs `  N
) )  x.  (
( abs `  M
)  gcd  ( abs `  N ) ) )  =  ( abs `  (
( abs `  M
)  x.  ( abs `  N ) ) )  /\  ( ( 0  e.  NN  /\  (
( abs `  M
)  ||  0  /\  ( abs `  N ) 
||  0 ) )  ->  ( ( abs `  M ) lcm  ( abs `  N ) )  ||  0 ) ) )
4645simpld 110 . . . 4  |-  ( ( ( abs `  M
)  e.  NN  /\  ( abs `  N )  e.  NN )  -> 
( ( ( abs `  M ) lcm  ( abs `  N ) )  x.  ( ( abs `  M
)  gcd  ( abs `  N ) ) )  =  ( abs `  (
( abs `  M
)  x.  ( abs `  N ) ) ) )
4744, 46syl 14 . . 3  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  \/  N  =  0 ) )  ->  ( ( ( abs `  M ) lcm  ( abs `  N
) )  x.  (
( abs `  M
)  gcd  ( abs `  N ) ) )  =  ( abs `  (
( abs `  M
)  x.  ( abs `  N ) ) ) )
48 lcmabs 10933 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( abs `  M
) lcm  ( abs `  N
) )  =  ( M lcm  N ) )
49 gcdabs 10854 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( abs `  M
)  gcd  ( abs `  N ) )  =  ( M  gcd  N
) )
5048, 49oveq12d 5631 . . . 4  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( ( abs `  M ) lcm  ( abs `  N ) )  x.  ( ( abs `  M
)  gcd  ( abs `  N ) ) )  =  ( ( M lcm 
N )  x.  ( M  gcd  N ) ) )
5150adantr 270 . . 3  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  \/  N  =  0 ) )  ->  ( ( ( abs `  M ) lcm  ( abs `  N
) )  x.  (
( abs `  M
)  gcd  ( abs `  N ) ) )  =  ( ( M lcm 
N )  x.  ( M  gcd  N ) ) )
52 absidm 10426 . . . . . . 7  |-  ( M  e.  CC  ->  ( abs `  ( abs `  M
) )  =  ( abs `  M ) )
53 absidm 10426 . . . . . . 7  |-  ( N  e.  CC  ->  ( abs `  ( abs `  N
) )  =  ( abs `  N ) )
5452, 53oveqan12d 5632 . . . . . 6  |-  ( ( M  e.  CC  /\  N  e.  CC )  ->  ( ( abs `  ( abs `  M ) )  x.  ( abs `  ( abs `  N ) ) )  =  ( ( abs `  M )  x.  ( abs `  N
) ) )
5526, 11, 54syl2an 283 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( abs `  ( abs `  M ) )  x.  ( abs `  ( abs `  N ) ) )  =  ( ( abs `  M )  x.  ( abs `  N
) ) )
56 nn0abscl 10413 . . . . . . . 8  |-  ( M  e.  ZZ  ->  ( abs `  M )  e. 
NN0 )
5756nn0cnd 8661 . . . . . . 7  |-  ( M  e.  ZZ  ->  ( abs `  M )  e.  CC )
5857adantr 270 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( abs `  M
)  e.  CC )
59 nn0abscl 10413 . . . . . . . 8  |-  ( N  e.  ZZ  ->  ( abs `  N )  e. 
NN0 )
6059nn0cnd 8661 . . . . . . 7  |-  ( N  e.  ZZ  ->  ( abs `  N )  e.  CC )
6160adantl 271 . . . . . 6  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( abs `  N
)  e.  CC )
6258, 61absmuld 10522 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( abs `  (
( abs `  M
)  x.  ( abs `  N ) ) )  =  ( ( abs `  ( abs `  M
) )  x.  ( abs `  ( abs `  N
) ) ) )
6327, 12absmuld 10522 . . . . 5  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( abs `  ( M  x.  N )
)  =  ( ( abs `  M )  x.  ( abs `  N
) ) )
6455, 62, 633eqtr4d 2127 . . . 4  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( abs `  (
( abs `  M
)  x.  ( abs `  N ) ) )  =  ( abs `  ( M  x.  N )
) )
6564adantr 270 . . 3  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  \/  N  =  0 ) )  ->  ( abs `  (
( abs `  M
)  x.  ( abs `  N ) ) )  =  ( abs `  ( M  x.  N )
) )
6647, 51, 653eqtr3d 2125 . 2  |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  \/  N  =  0 ) )  ->  ( ( M lcm 
N )  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  N )
) )
67 lcmmndc 10919 . . 3  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  -> DECID  ( M  =  0  \/  N  =  0 ) )
68 exmiddc 780 . . 3  |-  (DECID  ( M  =  0  \/  N  =  0 )  -> 
( ( M  =  0  \/  N  =  0 )  \/  -.  ( M  =  0  \/  N  =  0
) ) )
6967, 68syl 14 . 2  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( M  =  0  \/  N  =  0 )  \/  -.  ( M  =  0  \/  N  =  0
) ) )
7038, 66, 69mpjaodan 745 1  |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( M lcm  N
)  x.  ( M  gcd  N ) )  =  ( abs `  ( M  x.  N )
) )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    /\ wa 102    \/ wo 662  DECID wdc 778    = wceq 1287    e. wcel 1436    =/= wne 2251   class class class wbr 3820   ` cfv 4981  (class class class)co 5613   CCcc 7292   0cc0 7294    x. cmul 7299   NNcn 8357   ZZcz 8683   abscabs 10325    || cdvds 10671    gcd cgcd 10813   lcm clcm 10917
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 577  ax-in2 578  ax-io 663  ax-5 1379  ax-7 1380  ax-gen 1381  ax-ie1 1425  ax-ie2 1426  ax-8 1438  ax-10 1439  ax-11 1440  ax-i12 1441  ax-bndl 1442  ax-4 1443  ax-13 1447  ax-14 1448  ax-17 1462  ax-i9 1466  ax-ial 1470  ax-i5r 1471  ax-ext 2067  ax-coll 3929  ax-sep 3932  ax-nul 3940  ax-pow 3984  ax-pr 4010  ax-un 4234  ax-setind 4326  ax-iinf 4376  ax-cnex 7380  ax-resscn 7381  ax-1cn 7382  ax-1re 7383  ax-icn 7384  ax-addcl 7385  ax-addrcl 7386  ax-mulcl 7387  ax-mulrcl 7388  ax-addcom 7389  ax-mulcom 7390  ax-addass 7391  ax-mulass 7392  ax-distr 7393  ax-i2m1 7394  ax-0lt1 7395  ax-1rid 7396  ax-0id 7397  ax-rnegex 7398  ax-precex 7399  ax-cnre 7400  ax-pre-ltirr 7401  ax-pre-ltwlin 7402  ax-pre-lttrn 7403  ax-pre-apti 7404  ax-pre-ltadd 7405  ax-pre-mulgt0 7406  ax-pre-mulext 7407  ax-arch 7408  ax-caucvg 7409
This theorem depends on definitions:  df-bi 115  df-dc 779  df-3or 923  df-3an 924  df-tru 1290  df-fal 1293  df-nf 1393  df-sb 1690  df-eu 1948  df-mo 1949  df-clab 2072  df-cleq 2078  df-clel 2081  df-nfc 2214  df-ne 2252  df-nel 2347  df-ral 2360  df-rex 2361  df-reu 2362  df-rmo 2363  df-rab 2364  df-v 2617  df-sbc 2830  df-csb 2923  df-dif 2990  df-un 2992  df-in 2994  df-ss 3001  df-nul 3276  df-if 3380  df-pw 3417  df-sn 3437  df-pr 3438  df-op 3440  df-uni 3637  df-int 3672  df-iun 3715  df-br 3821  df-opab 3875  df-mpt 3876  df-tr 3912  df-id 4094  df-po 4097  df-iso 4098  df-iord 4167  df-on 4169  df-ilim 4170  df-suc 4172  df-iom 4379  df-xp 4417  df-rel 4418  df-cnv 4419  df-co 4420  df-dm 4421  df-rn 4422  df-res 4423  df-ima 4424  df-iota 4946  df-fun 4983  df-fn 4984  df-f 4985  df-f1 4986  df-fo 4987  df-f1o 4988  df-fv 4989  df-isom 4990  df-riota 5569  df-ov 5616  df-oprab 5617  df-mpt2 5618  df-1st 5868  df-2nd 5869  df-recs 6024  df-frec 6110  df-sup 6623  df-inf 6624  df-pnf 7468  df-mnf 7469  df-xr 7470  df-ltxr 7471  df-le 7472  df-sub 7599  df-neg 7600  df-reap 7993  df-ap 8000  df-div 8079  df-inn 8358  df-2 8416  df-3 8417  df-4 8418  df-n0 8607  df-z 8684  df-uz 8952  df-q 9037  df-rp 9067  df-fz 9357  df-fzo 9482  df-fl 9605  df-mod 9658  df-iseq 9780  df-iexp 9853  df-cj 10171  df-re 10172  df-im 10173  df-rsqrt 10326  df-abs 10327  df-dvds 10672  df-gcd 10814  df-lcm 10918
This theorem is referenced by:  lcmid  10937  lcm1  10938  lcmgcdnn  10939
  Copyright terms: Public domain W3C validator