MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  gcdmultipleOLD Structured version   Visualization version   GIF version

Theorem gcdmultipleOLD 16301
Description: Obsolete proof of gcdmultiple 16285 as of 12-Jan-2024. The GCD of a multiple of a number is the number itself. (Contributed by Scott Fenton, 12-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.) (Proof modification is discouraged.) (New usage is discouraged.)
Assertion
Ref Expression
gcdmultipleOLD ((๐‘€ โˆˆ โ„• โˆง ๐‘ โˆˆ โ„•) โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘)) = ๐‘€)

Proof of Theorem gcdmultipleOLD
Dummy variables ๐‘˜ ๐‘› are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 oveq2 7311 . . . . . 6 (๐‘˜ = 1 โ†’ (๐‘€ ยท ๐‘˜) = (๐‘€ ยท 1))
21oveq2d 7319 . . . . 5 (๐‘˜ = 1 โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = (๐‘€ gcd (๐‘€ ยท 1)))
32eqeq1d 2738 . . . 4 (๐‘˜ = 1 โ†’ ((๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€ โ†” (๐‘€ gcd (๐‘€ ยท 1)) = ๐‘€))
43imbi2d 342 . . 3 (๐‘˜ = 1 โ†’ ((๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€) โ†” (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท 1)) = ๐‘€)))
5 oveq2 7311 . . . . . 6 (๐‘˜ = ๐‘› โ†’ (๐‘€ ยท ๐‘˜) = (๐‘€ ยท ๐‘›))
65oveq2d 7319 . . . . 5 (๐‘˜ = ๐‘› โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = (๐‘€ gcd (๐‘€ ยท ๐‘›)))
76eqeq1d 2738 . . . 4 (๐‘˜ = ๐‘› โ†’ ((๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€ โ†” (๐‘€ gcd (๐‘€ ยท ๐‘›)) = ๐‘€))
87imbi2d 342 . . 3 (๐‘˜ = ๐‘› โ†’ ((๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€) โ†” (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘›)) = ๐‘€)))
9 oveq2 7311 . . . . . 6 (๐‘˜ = (๐‘› + 1) โ†’ (๐‘€ ยท ๐‘˜) = (๐‘€ ยท (๐‘› + 1)))
109oveq2d 7319 . . . . 5 (๐‘˜ = (๐‘› + 1) โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))))
1110eqeq1d 2738 . . . 4 (๐‘˜ = (๐‘› + 1) โ†’ ((๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€ โ†” (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))) = ๐‘€))
1211imbi2d 342 . . 3 (๐‘˜ = (๐‘› + 1) โ†’ ((๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€) โ†” (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))) = ๐‘€)))
13 oveq2 7311 . . . . . 6 (๐‘˜ = ๐‘ โ†’ (๐‘€ ยท ๐‘˜) = (๐‘€ ยท ๐‘))
1413oveq2d 7319 . . . . 5 (๐‘˜ = ๐‘ โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = (๐‘€ gcd (๐‘€ ยท ๐‘)))
1514eqeq1d 2738 . . . 4 (๐‘˜ = ๐‘ โ†’ ((๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€ โ†” (๐‘€ gcd (๐‘€ ยท ๐‘)) = ๐‘€))
1615imbi2d 342 . . 3 (๐‘˜ = ๐‘ โ†’ ((๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘˜)) = ๐‘€) โ†” (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘)) = ๐‘€)))
17 nncn 12023 . . . . . 6 (๐‘€ โˆˆ โ„• โ†’ ๐‘€ โˆˆ โ„‚)
1817mulid1d 11034 . . . . 5 (๐‘€ โˆˆ โ„• โ†’ (๐‘€ ยท 1) = ๐‘€)
1918oveq2d 7319 . . . 4 (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท 1)) = (๐‘€ gcd ๐‘€))
20 nnz 12384 . . . . . 6 (๐‘€ โˆˆ โ„• โ†’ ๐‘€ โˆˆ โ„ค)
21 gcdid 16275 . . . . . 6 (๐‘€ โˆˆ โ„ค โ†’ (๐‘€ gcd ๐‘€) = (absโ€˜๐‘€))
2220, 21syl 17 . . . . 5 (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd ๐‘€) = (absโ€˜๐‘€))
23 nnre 12022 . . . . . 6 (๐‘€ โˆˆ โ„• โ†’ ๐‘€ โˆˆ โ„)
24 nnnn0 12282 . . . . . . 7 (๐‘€ โˆˆ โ„• โ†’ ๐‘€ โˆˆ โ„•0)
2524nn0ge0d 12338 . . . . . 6 (๐‘€ โˆˆ โ„• โ†’ 0 โ‰ค ๐‘€)
2623, 25absidd 15175 . . . . 5 (๐‘€ โˆˆ โ„• โ†’ (absโ€˜๐‘€) = ๐‘€)
2722, 26eqtrd 2776 . . . 4 (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd ๐‘€) = ๐‘€)
2819, 27eqtrd 2776 . . 3 (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท 1)) = ๐‘€)
29 1z 12392 . . . . . . . . 9 1 โˆˆ โ„ค
30 nnz 12384 . . . . . . . . . 10 (๐‘› โˆˆ โ„• โ†’ ๐‘› โˆˆ โ„ค)
31 zmulcl 12411 . . . . . . . . . 10 ((๐‘€ โˆˆ โ„ค โˆง ๐‘› โˆˆ โ„ค) โ†’ (๐‘€ ยท ๐‘›) โˆˆ โ„ค)
3220, 30, 31syl2an 597 . . . . . . . . 9 ((๐‘€ โˆˆ โ„• โˆง ๐‘› โˆˆ โ„•) โ†’ (๐‘€ ยท ๐‘›) โˆˆ โ„ค)
33 gcdaddm 16273 . . . . . . . . 9 ((1 โˆˆ โ„ค โˆง ๐‘€ โˆˆ โ„ค โˆง (๐‘€ ยท ๐‘›) โˆˆ โ„ค) โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘›)) = (๐‘€ gcd ((๐‘€ ยท ๐‘›) + (1 ยท ๐‘€))))
3429, 20, 32, 33mp3an2ani 1468 . . . . . . . 8 ((๐‘€ โˆˆ โ„• โˆง ๐‘› โˆˆ โ„•) โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘›)) = (๐‘€ gcd ((๐‘€ ยท ๐‘›) + (1 ยท ๐‘€))))
35 nncn 12023 . . . . . . . . . 10 (๐‘› โˆˆ โ„• โ†’ ๐‘› โˆˆ โ„‚)
36 ax-1cn 10971 . . . . . . . . . . . 12 1 โˆˆ โ„‚
37 adddi 11002 . . . . . . . . . . . 12 ((๐‘€ โˆˆ โ„‚ โˆง ๐‘› โˆˆ โ„‚ โˆง 1 โˆˆ โ„‚) โ†’ (๐‘€ ยท (๐‘› + 1)) = ((๐‘€ ยท ๐‘›) + (๐‘€ ยท 1)))
3836, 37mp3an3 1450 . . . . . . . . . . 11 ((๐‘€ โˆˆ โ„‚ โˆง ๐‘› โˆˆ โ„‚) โ†’ (๐‘€ ยท (๐‘› + 1)) = ((๐‘€ ยท ๐‘›) + (๐‘€ ยท 1)))
39 mulcom 10999 . . . . . . . . . . . . . 14 ((๐‘€ โˆˆ โ„‚ โˆง 1 โˆˆ โ„‚) โ†’ (๐‘€ ยท 1) = (1 ยท ๐‘€))
4036, 39mpan2 689 . . . . . . . . . . . . 13 (๐‘€ โˆˆ โ„‚ โ†’ (๐‘€ ยท 1) = (1 ยท ๐‘€))
4140adantr 482 . . . . . . . . . . . 12 ((๐‘€ โˆˆ โ„‚ โˆง ๐‘› โˆˆ โ„‚) โ†’ (๐‘€ ยท 1) = (1 ยท ๐‘€))
4241oveq2d 7319 . . . . . . . . . . 11 ((๐‘€ โˆˆ โ„‚ โˆง ๐‘› โˆˆ โ„‚) โ†’ ((๐‘€ ยท ๐‘›) + (๐‘€ ยท 1)) = ((๐‘€ ยท ๐‘›) + (1 ยท ๐‘€)))
4338, 42eqtrd 2776 . . . . . . . . . 10 ((๐‘€ โˆˆ โ„‚ โˆง ๐‘› โˆˆ โ„‚) โ†’ (๐‘€ ยท (๐‘› + 1)) = ((๐‘€ ยท ๐‘›) + (1 ยท ๐‘€)))
4417, 35, 43syl2an 597 . . . . . . . . 9 ((๐‘€ โˆˆ โ„• โˆง ๐‘› โˆˆ โ„•) โ†’ (๐‘€ ยท (๐‘› + 1)) = ((๐‘€ ยท ๐‘›) + (1 ยท ๐‘€)))
4544oveq2d 7319 . . . . . . . 8 ((๐‘€ โˆˆ โ„• โˆง ๐‘› โˆˆ โ„•) โ†’ (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))) = (๐‘€ gcd ((๐‘€ ยท ๐‘›) + (1 ยท ๐‘€))))
4634, 45eqtr4d 2779 . . . . . . 7 ((๐‘€ โˆˆ โ„• โˆง ๐‘› โˆˆ โ„•) โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘›)) = (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))))
4746eqeq1d 2738 . . . . . 6 ((๐‘€ โˆˆ โ„• โˆง ๐‘› โˆˆ โ„•) โ†’ ((๐‘€ gcd (๐‘€ ยท ๐‘›)) = ๐‘€ โ†” (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))) = ๐‘€))
4847biimpd 228 . . . . 5 ((๐‘€ โˆˆ โ„• โˆง ๐‘› โˆˆ โ„•) โ†’ ((๐‘€ gcd (๐‘€ ยท ๐‘›)) = ๐‘€ โ†’ (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))) = ๐‘€))
4948expcom 415 . . . 4 (๐‘› โˆˆ โ„• โ†’ (๐‘€ โˆˆ โ„• โ†’ ((๐‘€ gcd (๐‘€ ยท ๐‘›)) = ๐‘€ โ†’ (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))) = ๐‘€)))
5049a2d 29 . . 3 (๐‘› โˆˆ โ„• โ†’ ((๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘›)) = ๐‘€) โ†’ (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท (๐‘› + 1))) = ๐‘€)))
514, 8, 12, 16, 28, 50nnind 12033 . 2 (๐‘ โˆˆ โ„• โ†’ (๐‘€ โˆˆ โ„• โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘)) = ๐‘€))
5251impcom 409 1 ((๐‘€ โˆˆ โ„• โˆง ๐‘ โˆˆ โ„•) โ†’ (๐‘€ gcd (๐‘€ ยท ๐‘)) = ๐‘€)
Colors of variables: wff setvar class
Syntax hints:   โ†’ wi 4   โˆง wa 397   = wceq 1539   โˆˆ wcel 2104  โ€˜cfv 6454  (class class class)co 7303  โ„‚cc 10911  1c1 10914   + caddc 10916   ยท cmul 10918  โ„•cn 12015  โ„คcz 12361  abscabs 14986   gcd cgcd 16242
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1795  ax-4 1809  ax-5 1911  ax-6 1969  ax-7 2009  ax-8 2106  ax-9 2114  ax-10 2135  ax-11 2152  ax-12 2169  ax-ext 2707  ax-sep 5232  ax-nul 5239  ax-pow 5297  ax-pr 5361  ax-un 7616  ax-cnex 10969  ax-resscn 10970  ax-1cn 10971  ax-icn 10972  ax-addcl 10973  ax-addrcl 10974  ax-mulcl 10975  ax-mulrcl 10976  ax-mulcom 10977  ax-addass 10978  ax-mulass 10979  ax-distr 10980  ax-i2m1 10981  ax-1ne0 10982  ax-1rid 10983  ax-rnegex 10984  ax-rrecex 10985  ax-cnre 10986  ax-pre-lttri 10987  ax-pre-lttrn 10988  ax-pre-ltadd 10989  ax-pre-mulgt0 10990  ax-pre-sup 10991
This theorem depends on definitions:  df-bi 206  df-an 398  df-or 846  df-3or 1088  df-3an 1089  df-tru 1542  df-fal 1552  df-ex 1780  df-nf 1784  df-sb 2066  df-mo 2538  df-eu 2567  df-clab 2714  df-cleq 2728  df-clel 2814  df-nfc 2887  df-ne 2942  df-nel 3048  df-ral 3063  df-rex 3072  df-rmo 3285  df-reu 3286  df-rab 3287  df-v 3439  df-sbc 3722  df-csb 3838  df-dif 3895  df-un 3897  df-in 3899  df-ss 3909  df-pss 3911  df-nul 4263  df-if 4466  df-pw 4541  df-sn 4566  df-pr 4568  df-op 4572  df-uni 4845  df-iun 4933  df-br 5082  df-opab 5144  df-mpt 5165  df-tr 5199  df-id 5496  df-eprel 5502  df-po 5510  df-so 5511  df-fr 5551  df-we 5553  df-xp 5602  df-rel 5603  df-cnv 5604  df-co 5605  df-dm 5606  df-rn 5607  df-res 5608  df-ima 5609  df-pred 6213  df-ord 6280  df-on 6281  df-lim 6282  df-suc 6283  df-iota 6406  df-fun 6456  df-fn 6457  df-f 6458  df-f1 6459  df-fo 6460  df-f1o 6461  df-fv 6462  df-riota 7260  df-ov 7306  df-oprab 7307  df-mpo 7308  df-om 7741  df-2nd 7860  df-frecs 8124  df-wrecs 8155  df-recs 8229  df-rdg 8268  df-er 8525  df-en 8761  df-dom 8762  df-sdom 8763  df-sup 9241  df-inf 9242  df-pnf 11053  df-mnf 11054  df-xr 11055  df-ltxr 11056  df-le 11057  df-sub 11249  df-neg 11250  df-div 11675  df-nn 12016  df-2 12078  df-3 12079  df-n0 12276  df-z 12362  df-uz 12625  df-rp 12773  df-seq 13764  df-exp 13825  df-cj 14851  df-re 14852  df-im 14853  df-sqrt 14987  df-abs 14988  df-dvds 16005  df-gcd 16243
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator