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

Theorem eucalgval 16503
Description: Euclid's Algorithm eucalg 16508 computes the greatest common divisor of two nonnegative integers by repeatedly replacing the larger of them with its remainder modulo the smaller until the remainder is 0.

The value of the step function 𝐸 for Euclid's Algorithm. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 28-May-2014.)

Hypothesis
Ref Expression
eucalgval.1 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))
Assertion
Ref Expression
eucalgval (𝑋 ∈ (ℕ0 × ℕ0) → (𝐸𝑋) = if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩))
Distinct variable group:   𝑥,𝑦,𝑋
Allowed substitution hints:   𝐸(𝑥,𝑦)

Proof of Theorem eucalgval
StepHypRef Expression
1 df-ov 7397 . . 3 ((1st𝑋)𝐸(2nd𝑋)) = (𝐸‘⟨(1st𝑋), (2nd𝑋)⟩)
2 xp1st 7991 . . . 4 (𝑋 ∈ (ℕ0 × ℕ0) → (1st𝑋) ∈ ℕ0)
3 xp2nd 7992 . . . 4 (𝑋 ∈ (ℕ0 × ℕ0) → (2nd𝑋) ∈ ℕ0)
4 eucalgval.1 . . . . 5 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))
54eucalgval2 16502 . . . 4 (((1st𝑋) ∈ ℕ0 ∧ (2nd𝑋) ∈ ℕ0) → ((1st𝑋)𝐸(2nd𝑋)) = if((2nd𝑋) = 0, ⟨(1st𝑋), (2nd𝑋)⟩, ⟨(2nd𝑋), ((1st𝑋) mod (2nd𝑋))⟩))
62, 3, 5syl2anc 584 . . 3 (𝑋 ∈ (ℕ0 × ℕ0) → ((1st𝑋)𝐸(2nd𝑋)) = if((2nd𝑋) = 0, ⟨(1st𝑋), (2nd𝑋)⟩, ⟨(2nd𝑋), ((1st𝑋) mod (2nd𝑋))⟩))
71, 6eqtr3id 2786 . 2 (𝑋 ∈ (ℕ0 × ℕ0) → (𝐸‘⟨(1st𝑋), (2nd𝑋)⟩) = if((2nd𝑋) = 0, ⟨(1st𝑋), (2nd𝑋)⟩, ⟨(2nd𝑋), ((1st𝑋) mod (2nd𝑋))⟩))
8 1st2nd2 7998 . . 3 (𝑋 ∈ (ℕ0 × ℕ0) → 𝑋 = ⟨(1st𝑋), (2nd𝑋)⟩)
98fveq2d 6883 . 2 (𝑋 ∈ (ℕ0 × ℕ0) → (𝐸𝑋) = (𝐸‘⟨(1st𝑋), (2nd𝑋)⟩))
108fveq2d 6883 . . . . 5 (𝑋 ∈ (ℕ0 × ℕ0) → ( mod ‘𝑋) = ( mod ‘⟨(1st𝑋), (2nd𝑋)⟩))
11 df-ov 7397 . . . . 5 ((1st𝑋) mod (2nd𝑋)) = ( mod ‘⟨(1st𝑋), (2nd𝑋)⟩)
1210, 11eqtr4di 2790 . . . 4 (𝑋 ∈ (ℕ0 × ℕ0) → ( mod ‘𝑋) = ((1st𝑋) mod (2nd𝑋)))
1312opeq2d 4874 . . 3 (𝑋 ∈ (ℕ0 × ℕ0) → ⟨(2nd𝑋), ( mod ‘𝑋)⟩ = ⟨(2nd𝑋), ((1st𝑋) mod (2nd𝑋))⟩)
148, 13ifeq12d 4544 . 2 (𝑋 ∈ (ℕ0 × ℕ0) → if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩) = if((2nd𝑋) = 0, ⟨(1st𝑋), (2nd𝑋)⟩, ⟨(2nd𝑋), ((1st𝑋) mod (2nd𝑋))⟩))
157, 9, 143eqtr4d 2782 1 (𝑋 ∈ (ℕ0 × ℕ0) → (𝐸𝑋) = if((2nd𝑋) = 0, 𝑋, ⟨(2nd𝑋), ( mod ‘𝑋)⟩))
Colors of variables: wff setvar class
Syntax hints:  wi 4   = wceq 1541  wcel 2106  ifcif 4523  cop 4629   × cxp 5668  cfv 6533  (class class class)co 7394  cmpo 7396  1st c1st 7957  2nd c2nd 7958  0cc0 11094  0cn0 12456   mod cmo 13818
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2703  ax-sep 5293  ax-nul 5300  ax-pr 5421  ax-un 7709
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3an 1089  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2534  df-eu 2563  df-clab 2710  df-cleq 2724  df-clel 2810  df-nfc 2885  df-ral 3062  df-rex 3071  df-rab 3433  df-v 3476  df-sbc 3775  df-dif 3948  df-un 3950  df-in 3952  df-ss 3962  df-nul 4320  df-if 4524  df-sn 4624  df-pr 4626  df-op 4630  df-uni 4903  df-br 5143  df-opab 5205  df-mpt 5226  df-id 5568  df-xp 5676  df-rel 5677  df-cnv 5678  df-co 5679  df-dm 5680  df-rn 5681  df-iota 6485  df-fun 6535  df-fv 6541  df-ov 7397  df-oprab 7398  df-mpo 7399  df-1st 7959  df-2nd 7960
This theorem is referenced by:  eucalginv  16505  eucalglt  16506
  Copyright terms: Public domain W3C validator