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

Theorem eucalginv 15906
 Description: The invariant of the step function 𝐸 for Euclid's Algorithm is the gcd operator applied to the state. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 29-May-2014.)
Hypothesis
Ref Expression
eucalgval.1 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))
Assertion
Ref Expression
eucalginv (𝑋 ∈ (ℕ0 × ℕ0) → ( gcd ‘(𝐸𝑋)) = ( gcd ‘𝑋))
Distinct variable group:   𝑥,𝑦,𝑋
Allowed substitution hints:   𝐸(𝑥,𝑦)

Proof of Theorem eucalginv
StepHypRef Expression
1 eucalgval.1 . . . 4 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))
21eucalgval 15904 . . 3 (𝑋 ∈ (ℕ0 × ℕ0) → (𝐸𝑋) = if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩))
32fveq2d 6650 . 2 (𝑋 ∈ (ℕ0 × ℕ0) → ( gcd ‘(𝐸𝑋)) = ( gcd ‘if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩)))
4 1st2nd2 7706 . . . . . . . . 9 (𝑋 ∈ (ℕ0 × ℕ0) → 𝑋 = ⟨(1st𝑋), (2nd𝑋)⟩)
54adantr 483 . . . . . . . 8 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → 𝑋 = ⟨(1st𝑋), (2nd𝑋)⟩)
65fveq2d 6650 . . . . . . 7 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ( mod ‘𝑋) = ( mod ‘⟨(1st𝑋), (2nd𝑋)⟩))
7 df-ov 7136 . . . . . . 7 ((1st𝑋) mod (2nd𝑋)) = ( mod ‘⟨(1st𝑋), (2nd𝑋)⟩)
86, 7syl6eqr 2873 . . . . . 6 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ( mod ‘𝑋) = ((1st𝑋) mod (2nd𝑋)))
98oveq2d 7149 . . . . 5 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ((2nd𝑋) gcd ( mod ‘𝑋)) = ((2nd𝑋) gcd ((1st𝑋) mod (2nd𝑋))))
10 nnz 11983 . . . . . 6 ((2nd𝑋) ∈ ℕ → (2nd𝑋) ∈ ℤ)
11 xp1st 7699 . . . . . . . . . 10 (𝑋 ∈ (ℕ0 × ℕ0) → (1st𝑋) ∈ ℕ0)
1211adantr 483 . . . . . . . . 9 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → (1st𝑋) ∈ ℕ0)
1312nn0zd 12064 . . . . . . . 8 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → (1st𝑋) ∈ ℤ)
14 zmodcl 13243 . . . . . . . 8 (((1st𝑋) ∈ ℤ ∧ (2nd𝑋) ∈ ℕ) → ((1st𝑋) mod (2nd𝑋)) ∈ ℕ0)
1513, 14sylancom 590 . . . . . . 7 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ((1st𝑋) mod (2nd𝑋)) ∈ ℕ0)
1615nn0zd 12064 . . . . . 6 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ((1st𝑋) mod (2nd𝑋)) ∈ ℤ)
17 gcdcom 15840 . . . . . 6 (((2nd𝑋) ∈ ℤ ∧ ((1st𝑋) mod (2nd𝑋)) ∈ ℤ) → ((2nd𝑋) gcd ((1st𝑋) mod (2nd𝑋))) = (((1st𝑋) mod (2nd𝑋)) gcd (2nd𝑋)))
1810, 16, 17syl2an2 684 . . . . 5 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ((2nd𝑋) gcd ((1st𝑋) mod (2nd𝑋))) = (((1st𝑋) mod (2nd𝑋)) gcd (2nd𝑋)))
19 modgcd 15858 . . . . . 6 (((1st𝑋) ∈ ℤ ∧ (2nd𝑋) ∈ ℕ) → (((1st𝑋) mod (2nd𝑋)) gcd (2nd𝑋)) = ((1st𝑋) gcd (2nd𝑋)))
2013, 19sylancom 590 . . . . 5 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → (((1st𝑋) mod (2nd𝑋)) gcd (2nd𝑋)) = ((1st𝑋) gcd (2nd𝑋)))
219, 18, 203eqtrd 2859 . . . 4 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ((2nd𝑋) gcd ( mod ‘𝑋)) = ((1st𝑋) gcd (2nd𝑋)))
22 nnne0 11650 . . . . . . . . 9 ((2nd𝑋) ∈ ℕ → (2nd𝑋) ≠ 0)
2322adantl 484 . . . . . . . 8 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → (2nd𝑋) ≠ 0)
2423neneqd 3011 . . . . . . 7 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ¬ (2nd𝑋) = 0)
2524iffalsed 4454 . . . . . 6 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩) = ⟨(2nd𝑋), ( mod ‘𝑋)⟩)
2625fveq2d 6650 . . . . 5 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ( gcd ‘if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩)) = ( gcd ‘⟨(2nd𝑋), ( mod ‘𝑋)⟩))
27 df-ov 7136 . . . . 5 ((2nd𝑋) gcd ( mod ‘𝑋)) = ( gcd ‘⟨(2nd𝑋), ( mod ‘𝑋)⟩)
2826, 27syl6eqr 2873 . . . 4 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ( gcd ‘if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩)) = ((2nd𝑋) gcd ( mod ‘𝑋)))
295fveq2d 6650 . . . . 5 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ( gcd ‘𝑋) = ( gcd ‘⟨(1st𝑋), (2nd𝑋)⟩))
30 df-ov 7136 . . . . 5 ((1st𝑋) gcd (2nd𝑋)) = ( gcd ‘⟨(1st𝑋), (2nd𝑋)⟩)
3129, 30syl6eqr 2873 . . . 4 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ( gcd ‘𝑋) = ((1st𝑋) gcd (2nd𝑋)))
3221, 28, 313eqtr4d 2865 . . 3 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) ∈ ℕ) → ( gcd ‘if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩)) = ( gcd ‘𝑋))
33 iftrue 4449 . . . . 5 ((2nd𝑋) = 0 → if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩) = 𝑋)
3433fveq2d 6650 . . . 4 ((2nd𝑋) = 0 → ( gcd ‘if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩)) = ( gcd ‘𝑋))
3534adantl 484 . . 3 ((𝑋 ∈ (ℕ0 × ℕ0) ∧ (2nd𝑋) = 0) → ( gcd ‘if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩)) = ( gcd ‘𝑋))
36 xp2nd 7700 . . . 4 (𝑋 ∈ (ℕ0 × ℕ0) → (2nd𝑋) ∈ ℕ0)
37 elnn0 11878 . . . 4 ((2nd𝑋) ∈ ℕ0 ↔ ((2nd𝑋) ∈ ℕ ∨ (2nd𝑋) = 0))
3836, 37sylib 220 . . 3 (𝑋 ∈ (ℕ0 × ℕ0) → ((2nd𝑋) ∈ ℕ ∨ (2nd𝑋) = 0))
3932, 35, 38mpjaodan 955 . 2 (𝑋 ∈ (ℕ0 × ℕ0) → ( gcd ‘if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩)) = ( gcd ‘𝑋))
403, 39eqtrd 2855 1 (𝑋 ∈ (ℕ0 × ℕ0) → ( gcd ‘(𝐸𝑋)) = ( gcd ‘𝑋))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ∧ wa 398   ∨ wo 843   = wceq 1537   ∈ wcel 2114   ≠ wne 3006  ifcif 4443  ⟨cop 4549   × cxp 5529  ‘cfv 6331  (class class class)co 7133   ∈ cmpo 7135  1st c1st 7665  2nd c2nd 7666  0cc0 10515  ℕcn 11616  ℕ0cn0 11876  ℤcz 11960   mod cmo 13221   gcd cgcd 15821 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2161  ax-12 2177  ax-ext 2792  ax-sep 5179  ax-nul 5186  ax-pow 5242  ax-pr 5306  ax-un 7439  ax-cnex 10571  ax-resscn 10572  ax-1cn 10573  ax-icn 10574  ax-addcl 10575  ax-addrcl 10576  ax-mulcl 10577  ax-mulrcl 10578  ax-mulcom 10579  ax-addass 10580  ax-mulass 10581  ax-distr 10582  ax-i2m1 10583  ax-1ne0 10584  ax-1rid 10585  ax-rnegex 10586  ax-rrecex 10587  ax-cnre 10588  ax-pre-lttri 10589  ax-pre-lttrn 10590  ax-pre-ltadd 10591  ax-pre-mulgt0 10592  ax-pre-sup 10593 This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3or 1084  df-3an 1085  df-tru 1540  df-ex 1781  df-nf 1785  df-sb 2070  df-mo 2622  df-eu 2653  df-clab 2799  df-cleq 2813  df-clel 2891  df-nfc 2959  df-ne 3007  df-nel 3111  df-ral 3130  df-rex 3131  df-reu 3132  df-rmo 3133  df-rab 3134  df-v 3475  df-sbc 3753  df-csb 3861  df-dif 3916  df-un 3918  df-in 3920  df-ss 3930  df-pss 3932  df-nul 4270  df-if 4444  df-pw 4517  df-sn 4544  df-pr 4546  df-tp 4548  df-op 4550  df-uni 4815  df-iun 4897  df-br 5043  df-opab 5105  df-mpt 5123  df-tr 5149  df-id 5436  df-eprel 5441  df-po 5450  df-so 5451  df-fr 5490  df-we 5492  df-xp 5537  df-rel 5538  df-cnv 5539  df-co 5540  df-dm 5541  df-rn 5542  df-res 5543  df-ima 5544  df-pred 6124  df-ord 6170  df-on 6171  df-lim 6172  df-suc 6173  df-iota 6290  df-fun 6333  df-fn 6334  df-f 6335  df-f1 6336  df-fo 6337  df-f1o 6338  df-fv 6339  df-riota 7091  df-ov 7136  df-oprab 7137  df-mpo 7138  df-om 7559  df-1st 7667  df-2nd 7668  df-wrecs 7925  df-recs 7986  df-rdg 8024  df-er 8267  df-en 8488  df-dom 8489  df-sdom 8490  df-sup 8884  df-inf 8885  df-pnf 10655  df-mnf 10656  df-xr 10657  df-ltxr 10658  df-le 10659  df-sub 10850  df-neg 10851  df-div 11276  df-nn 11617  df-2 11679  df-3 11680  df-n0 11877  df-z 11961  df-uz 12223  df-rp 12369  df-fl 13146  df-mod 13222  df-seq 13354  df-exp 13415  df-cj 14438  df-re 14439  df-im 14440  df-sqrt 14574  df-abs 14575  df-dvds 15588  df-gcd 15822 This theorem is referenced by:  eucalg  15909
 Copyright terms: Public domain W3C validator