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

Theorem gcdmultiple 15733
Description: 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.)
Assertion
Ref Expression
gcdmultiple ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → (𝑀 gcd (𝑀 · 𝑁)) = 𝑀)

Proof of Theorem gcdmultiple
Dummy variables 𝑘 𝑛 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 oveq2 7031 . . . . . 6 (𝑘 = 1 → (𝑀 · 𝑘) = (𝑀 · 1))
21oveq2d 7039 . . . . 5 (𝑘 = 1 → (𝑀 gcd (𝑀 · 𝑘)) = (𝑀 gcd (𝑀 · 1)))
32eqeq1d 2799 . . . 4 (𝑘 = 1 → ((𝑀 gcd (𝑀 · 𝑘)) = 𝑀 ↔ (𝑀 gcd (𝑀 · 1)) = 𝑀))
43imbi2d 342 . . 3 (𝑘 = 1 → ((𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑘)) = 𝑀) ↔ (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 1)) = 𝑀)))
5 oveq2 7031 . . . . . 6 (𝑘 = 𝑛 → (𝑀 · 𝑘) = (𝑀 · 𝑛))
65oveq2d 7039 . . . . 5 (𝑘 = 𝑛 → (𝑀 gcd (𝑀 · 𝑘)) = (𝑀 gcd (𝑀 · 𝑛)))
76eqeq1d 2799 . . . 4 (𝑘 = 𝑛 → ((𝑀 gcd (𝑀 · 𝑘)) = 𝑀 ↔ (𝑀 gcd (𝑀 · 𝑛)) = 𝑀))
87imbi2d 342 . . 3 (𝑘 = 𝑛 → ((𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑘)) = 𝑀) ↔ (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑛)) = 𝑀)))
9 oveq2 7031 . . . . . 6 (𝑘 = (𝑛 + 1) → (𝑀 · 𝑘) = (𝑀 · (𝑛 + 1)))
109oveq2d 7039 . . . . 5 (𝑘 = (𝑛 + 1) → (𝑀 gcd (𝑀 · 𝑘)) = (𝑀 gcd (𝑀 · (𝑛 + 1))))
1110eqeq1d 2799 . . . 4 (𝑘 = (𝑛 + 1) → ((𝑀 gcd (𝑀 · 𝑘)) = 𝑀 ↔ (𝑀 gcd (𝑀 · (𝑛 + 1))) = 𝑀))
1211imbi2d 342 . . 3 (𝑘 = (𝑛 + 1) → ((𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑘)) = 𝑀) ↔ (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · (𝑛 + 1))) = 𝑀)))
13 oveq2 7031 . . . . . 6 (𝑘 = 𝑁 → (𝑀 · 𝑘) = (𝑀 · 𝑁))
1413oveq2d 7039 . . . . 5 (𝑘 = 𝑁 → (𝑀 gcd (𝑀 · 𝑘)) = (𝑀 gcd (𝑀 · 𝑁)))
1514eqeq1d 2799 . . . 4 (𝑘 = 𝑁 → ((𝑀 gcd (𝑀 · 𝑘)) = 𝑀 ↔ (𝑀 gcd (𝑀 · 𝑁)) = 𝑀))
1615imbi2d 342 . . 3 (𝑘 = 𝑁 → ((𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑘)) = 𝑀) ↔ (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑁)) = 𝑀)))
17 nncn 11500 . . . . . 6 (𝑀 ∈ ℕ → 𝑀 ∈ ℂ)
1817mulid1d 10511 . . . . 5 (𝑀 ∈ ℕ → (𝑀 · 1) = 𝑀)
1918oveq2d 7039 . . . 4 (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 1)) = (𝑀 gcd 𝑀))
20 nnz 11858 . . . . . 6 (𝑀 ∈ ℕ → 𝑀 ∈ ℤ)
21 gcdid 15712 . . . . . 6 (𝑀 ∈ ℤ → (𝑀 gcd 𝑀) = (abs‘𝑀))
2220, 21syl 17 . . . . 5 (𝑀 ∈ ℕ → (𝑀 gcd 𝑀) = (abs‘𝑀))
23 nnre 11499 . . . . . 6 (𝑀 ∈ ℕ → 𝑀 ∈ ℝ)
24 nnnn0 11758 . . . . . . 7 (𝑀 ∈ ℕ → 𝑀 ∈ ℕ0)
2524nn0ge0d 11812 . . . . . 6 (𝑀 ∈ ℕ → 0 ≤ 𝑀)
2623, 25absidd 14620 . . . . 5 (𝑀 ∈ ℕ → (abs‘𝑀) = 𝑀)
2722, 26eqtrd 2833 . . . 4 (𝑀 ∈ ℕ → (𝑀 gcd 𝑀) = 𝑀)
2819, 27eqtrd 2833 . . 3 (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 1)) = 𝑀)
29 1z 11866 . . . . . . . . 9 1 ∈ ℤ
30 nnz 11858 . . . . . . . . . 10 (𝑛 ∈ ℕ → 𝑛 ∈ ℤ)
31 zmulcl 11885 . . . . . . . . . 10 ((𝑀 ∈ ℤ ∧ 𝑛 ∈ ℤ) → (𝑀 · 𝑛) ∈ ℤ)
3220, 30, 31syl2an 595 . . . . . . . . 9 ((𝑀 ∈ ℕ ∧ 𝑛 ∈ ℕ) → (𝑀 · 𝑛) ∈ ℤ)
33 gcdaddm 15710 . . . . . . . . 9 ((1 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ (𝑀 · 𝑛) ∈ ℤ) → (𝑀 gcd (𝑀 · 𝑛)) = (𝑀 gcd ((𝑀 · 𝑛) + (1 · 𝑀))))
3429, 20, 32, 33mp3an2ani 1460 . . . . . . . 8 ((𝑀 ∈ ℕ ∧ 𝑛 ∈ ℕ) → (𝑀 gcd (𝑀 · 𝑛)) = (𝑀 gcd ((𝑀 · 𝑛) + (1 · 𝑀))))
35 nncn 11500 . . . . . . . . . 10 (𝑛 ∈ ℕ → 𝑛 ∈ ℂ)
36 ax-1cn 10448 . . . . . . . . . . . 12 1 ∈ ℂ
37 adddi 10479 . . . . . . . . . . . 12 ((𝑀 ∈ ℂ ∧ 𝑛 ∈ ℂ ∧ 1 ∈ ℂ) → (𝑀 · (𝑛 + 1)) = ((𝑀 · 𝑛) + (𝑀 · 1)))
3836, 37mp3an3 1442 . . . . . . . . . . 11 ((𝑀 ∈ ℂ ∧ 𝑛 ∈ ℂ) → (𝑀 · (𝑛 + 1)) = ((𝑀 · 𝑛) + (𝑀 · 1)))
39 mulcom 10476 . . . . . . . . . . . . . 14 ((𝑀 ∈ ℂ ∧ 1 ∈ ℂ) → (𝑀 · 1) = (1 · 𝑀))
4036, 39mpan2 687 . . . . . . . . . . . . 13 (𝑀 ∈ ℂ → (𝑀 · 1) = (1 · 𝑀))
4140adantr 481 . . . . . . . . . . . 12 ((𝑀 ∈ ℂ ∧ 𝑛 ∈ ℂ) → (𝑀 · 1) = (1 · 𝑀))
4241oveq2d 7039 . . . . . . . . . . 11 ((𝑀 ∈ ℂ ∧ 𝑛 ∈ ℂ) → ((𝑀 · 𝑛) + (𝑀 · 1)) = ((𝑀 · 𝑛) + (1 · 𝑀)))
4338, 42eqtrd 2833 . . . . . . . . . 10 ((𝑀 ∈ ℂ ∧ 𝑛 ∈ ℂ) → (𝑀 · (𝑛 + 1)) = ((𝑀 · 𝑛) + (1 · 𝑀)))
4417, 35, 43syl2an 595 . . . . . . . . 9 ((𝑀 ∈ ℕ ∧ 𝑛 ∈ ℕ) → (𝑀 · (𝑛 + 1)) = ((𝑀 · 𝑛) + (1 · 𝑀)))
4544oveq2d 7039 . . . . . . . 8 ((𝑀 ∈ ℕ ∧ 𝑛 ∈ ℕ) → (𝑀 gcd (𝑀 · (𝑛 + 1))) = (𝑀 gcd ((𝑀 · 𝑛) + (1 · 𝑀))))
4634, 45eqtr4d 2836 . . . . . . 7 ((𝑀 ∈ ℕ ∧ 𝑛 ∈ ℕ) → (𝑀 gcd (𝑀 · 𝑛)) = (𝑀 gcd (𝑀 · (𝑛 + 1))))
4746eqeq1d 2799 . . . . . 6 ((𝑀 ∈ ℕ ∧ 𝑛 ∈ ℕ) → ((𝑀 gcd (𝑀 · 𝑛)) = 𝑀 ↔ (𝑀 gcd (𝑀 · (𝑛 + 1))) = 𝑀))
4847biimpd 230 . . . . 5 ((𝑀 ∈ ℕ ∧ 𝑛 ∈ ℕ) → ((𝑀 gcd (𝑀 · 𝑛)) = 𝑀 → (𝑀 gcd (𝑀 · (𝑛 + 1))) = 𝑀))
4948expcom 414 . . . 4 (𝑛 ∈ ℕ → (𝑀 ∈ ℕ → ((𝑀 gcd (𝑀 · 𝑛)) = 𝑀 → (𝑀 gcd (𝑀 · (𝑛 + 1))) = 𝑀)))
5049a2d 29 . . 3 (𝑛 ∈ ℕ → ((𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑛)) = 𝑀) → (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · (𝑛 + 1))) = 𝑀)))
514, 8, 12, 16, 28, 50nnind 11510 . 2 (𝑁 ∈ ℕ → (𝑀 ∈ ℕ → (𝑀 gcd (𝑀 · 𝑁)) = 𝑀))
5251impcom 408 1 ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → (𝑀 gcd (𝑀 · 𝑁)) = 𝑀)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 396   = wceq 1525  wcel 2083  cfv 6232  (class class class)co 7023  cc 10388  1c1 10391   + caddc 10393   · cmul 10395  cn 11492  cz 11835  abscabs 14431   gcd cgcd 15680
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1781  ax-4 1795  ax-5 1892  ax-6 1951  ax-7 1996  ax-8 2085  ax-9 2093  ax-10 2114  ax-11 2128  ax-12 2143  ax-13 2346  ax-ext 2771  ax-sep 5101  ax-nul 5108  ax-pow 5164  ax-pr 5228  ax-un 7326  ax-cnex 10446  ax-resscn 10447  ax-1cn 10448  ax-icn 10449  ax-addcl 10450  ax-addrcl 10451  ax-mulcl 10452  ax-mulrcl 10453  ax-mulcom 10454  ax-addass 10455  ax-mulass 10456  ax-distr 10457  ax-i2m1 10458  ax-1ne0 10459  ax-1rid 10460  ax-rnegex 10461  ax-rrecex 10462  ax-cnre 10463  ax-pre-lttri 10464  ax-pre-lttrn 10465  ax-pre-ltadd 10466  ax-pre-mulgt0 10467  ax-pre-sup 10468
This theorem depends on definitions:  df-bi 208  df-an 397  df-or 843  df-3or 1081  df-3an 1082  df-tru 1528  df-ex 1766  df-nf 1770  df-sb 2045  df-mo 2578  df-eu 2614  df-clab 2778  df-cleq 2790  df-clel 2865  df-nfc 2937  df-ne 2987  df-nel 3093  df-ral 3112  df-rex 3113  df-reu 3114  df-rmo 3115  df-rab 3116  df-v 3442  df-sbc 3712  df-csb 3818  df-dif 3868  df-un 3870  df-in 3872  df-ss 3880  df-pss 3882  df-nul 4218  df-if 4388  df-pw 4461  df-sn 4479  df-pr 4481  df-tp 4483  df-op 4485  df-uni 4752  df-iun 4833  df-br 4969  df-opab 5031  df-mpt 5048  df-tr 5071  df-id 5355  df-eprel 5360  df-po 5369  df-so 5370  df-fr 5409  df-we 5411  df-xp 5456  df-rel 5457  df-cnv 5458  df-co 5459  df-dm 5460  df-rn 5461  df-res 5462  df-ima 5463  df-pred 6030  df-ord 6076  df-on 6077  df-lim 6078  df-suc 6079  df-iota 6196  df-fun 6234  df-fn 6235  df-f 6236  df-f1 6237  df-fo 6238  df-f1o 6239  df-fv 6240  df-riota 6984  df-ov 7026  df-oprab 7027  df-mpo 7028  df-om 7444  df-2nd 7553  df-wrecs 7805  df-recs 7867  df-rdg 7905  df-er 8146  df-en 8365  df-dom 8366  df-sdom 8367  df-sup 8759  df-inf 8760  df-pnf 10530  df-mnf 10531  df-xr 10532  df-ltxr 10533  df-le 10534  df-sub 10725  df-neg 10726  df-div 11152  df-nn 11493  df-2 11554  df-3 11555  df-n0 11752  df-z 11836  df-uz 12098  df-rp 12244  df-seq 13224  df-exp 13284  df-cj 14296  df-re 14297  df-im 14298  df-sqrt 14432  df-abs 14433  df-dvds 15445  df-gcd 15681
This theorem is referenced by:  gcdmultiplez  15734  rpmulgcd  15739
  Copyright terms: Public domain W3C validator