eucalgval - Metamath Proof Explorer

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

Theorem eucalgval 16629

Description: Euclid's Algorithm eucalg 16634 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	⊢ 𝐸 = (𝑥 ∈ ℕ₀, 𝑦 ∈ ℕ₀ ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))

**Assertion**
Ref	Expression
eucalgval	⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (𝐸‘𝑋) = if((2^nd ‘𝑋) = 0, 𝑋, ⟨(2^nd ‘𝑋), ( mod ‘𝑋)⟩))

Distinct variable group: 𝑥,𝑦,𝑋 Allowed substitution hints: 𝐸(𝑥,𝑦)

**Proof of Theorem eucalgval**
Step	Hyp	Ref	Expression
1		df-ov 7451	. . 3 ⊢ ((1^st ‘𝑋)𝐸(2^nd ‘𝑋)) = (𝐸‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩)
2		xp1st 8062	. . . 4 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (1^st ‘𝑋) ∈ ℕ₀)
3		xp2nd 8063	. . . 4 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (2^nd ‘𝑋) ∈ ℕ₀)
4		eucalgval.1	. . . . 5 ⊢ 𝐸 = (𝑥 ∈ ℕ₀, 𝑦 ∈ ℕ₀ ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))
5	4	eucalgval2 16628	. . . 4 ⊢ (((1^st ‘𝑋) ∈ ℕ₀ ∧ (2^nd ‘𝑋) ∈ ℕ₀) → ((1^st ‘𝑋)𝐸(2^nd ‘𝑋)) = if((2^nd ‘𝑋) = 0, ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩, ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩))
6	2, 3, 5	syl2anc 583	. . 3 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ((1^st ‘𝑋)𝐸(2^nd ‘𝑋)) = if((2^nd ‘𝑋) = 0, ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩, ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩))
7	1, 6	eqtr3id 2794	. 2 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (𝐸‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩) = if((2^nd ‘𝑋) = 0, ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩, ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩))
8		1st2nd2 8069	. . 3 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → 𝑋 = ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩)
9	8	fveq2d 6924	. 2 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (𝐸‘𝑋) = (𝐸‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩))
10	8	fveq2d 6924	. . . . 5 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ( mod ‘𝑋) = ( mod ‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩))
11		df-ov 7451	. . . . 5 ⊢ ((1^st ‘𝑋) mod (2^nd ‘𝑋)) = ( mod ‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩)
12	10, 11	eqtr4di 2798	. . . 4 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ( mod ‘𝑋) = ((1^st ‘𝑋) mod (2^nd ‘𝑋)))
13	12	opeq2d 4904	. . 3 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ⟨(2^nd ‘𝑋), ( mod ‘𝑋)⟩ = ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩)
14	8, 13	ifeq12d 4569	. 2 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → if((2^nd ‘𝑋) = 0, 𝑋, ⟨(2^nd ‘𝑋), ( mod ‘𝑋)⟩) = if((2^nd ‘𝑋) = 0, ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩, ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩))
15	7, 9, 14	3eqtr4d 2790	1 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (𝐸‘𝑋) = if((2^nd ‘𝑋) = 0, 𝑋, ⟨(2^nd ‘𝑋), ( mod ‘𝑋)⟩))

Colors of variables: wff setvar class

Syntax hints: → wi 4 = wceq 1537 ∈ wcel 2108 ifcif 4548 ⟨cop 4654 × cxp 5698 ‘cfv 6573 (class class class)co 7448 ∈ cmpo 7450 1^st c1st 8028 2^nd c2nd 8029 0cc0 11184 ℕ₀cn0 12553 mod cmo 13920

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1793 ax-4 1807 ax-5 1909 ax-6 1967 ax-7 2007 ax-8 2110 ax-9 2118 ax-10 2141 ax-11 2158 ax-12 2178 ax-ext 2711 ax-sep 5317 ax-nul 5324 ax-pr 5447 ax-un 7770

This theorem depends on definitions: df-bi 207 df-an 396 df-or 847 df-3an 1089 df-tru 1540 df-fal 1550 df-ex 1778 df-nf 1782 df-sb 2065 df-mo 2543 df-eu 2572 df-clab 2718 df-cleq 2732 df-clel 2819 df-nfc 2895 df-ral 3068 df-rex 3077 df-rab 3444 df-v 3490 df-sbc 3805 df-dif 3979 df-un 3981 df-in 3983 df-ss 3993 df-nul 4353 df-if 4549 df-sn 4649 df-pr 4651 df-op 4655 df-uni 4932 df-br 5167 df-opab 5229 df-mpt 5250 df-id 5593 df-xp 5706 df-rel 5707 df-cnv 5708 df-co 5709 df-dm 5710 df-rn 5711 df-iota 6525 df-fun 6575 df-fv 6581 df-ov 7451 df-oprab 7452 df-mpo 7453 df-1st 8030 df-2nd 8031

This theorem is referenced by: eucalginv 16631 eucalglt 16632

W3C validator