eucalgval - Intuitionistic Logic Explorer

	Intuitionistic Logic Explorer		< Previous Next > Nearby theorems
Mirrors > Home > ILE Home > Th. List > eucalgval		GIF version

Theorem eucalgval 12619

Description: Euclid's Algorithm eucalg 12624 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 6016	. . 3 ⊢ ((1^st ‘𝑋)𝐸(2^nd ‘𝑋)) = (𝐸‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩)
2		xp1st 6323	. . . 4 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (1^st ‘𝑋) ∈ ℕ₀)
3		xp2nd 6324	. . . 4 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (2^nd ‘𝑋) ∈ ℕ₀)
4		eucalgval.1	. . . . 5 ⊢ 𝐸 = (𝑥 ∈ ℕ₀, 𝑦 ∈ ℕ₀ ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))
5	4	eucalgval2 12618	. . . 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 411	. . 3 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ((1^st ‘𝑋)𝐸(2^nd ‘𝑋)) = if((2^nd ‘𝑋) = 0, ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩, ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩))
7	1, 6	eqtr3id 2276	. 2 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (𝐸‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩) = if((2^nd ‘𝑋) = 0, ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩, ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩))
8		1st2nd2 6333	. . 3 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → 𝑋 = ⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩)
9	8	fveq2d 5639	. 2 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (𝐸‘𝑋) = (𝐸‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩))
10	8	fveq2d 5639	. . . . 5 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ( mod ‘𝑋) = ( mod ‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩))
11		df-ov 6016	. . . . 5 ⊢ ((1^st ‘𝑋) mod (2^nd ‘𝑋)) = ( mod ‘⟨(1^st ‘𝑋), (2^nd ‘𝑋)⟩)
12	10, 11	eqtr4di 2280	. . . 4 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ( mod ‘𝑋) = ((1^st ‘𝑋) mod (2^nd ‘𝑋)))
13	12	opeq2d 3867	. . 3 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → ⟨(2^nd ‘𝑋), ( mod ‘𝑋)⟩ = ⟨(2^nd ‘𝑋), ((1^st ‘𝑋) mod (2^nd ‘𝑋))⟩)
14	8, 13	ifeq12d 3623	. 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 2272	1 ⊢ (𝑋 ∈ (ℕ₀ × ℕ₀) → (𝐸‘𝑋) = if((2^nd ‘𝑋) = 0, 𝑋, ⟨(2^nd ‘𝑋), ( mod ‘𝑋)⟩))

Colors of variables: wff set class

Syntax hints: → wi 4 = wceq 1395 ∈ wcel 2200 ifcif 3603 ⟨cop 3670 × cxp 4721 ‘cfv 5324 (class class class)co 6013 ∈ cmpo 6015 1^st c1st 6296 2^nd c2nd 6297 0cc0 8025 ℕ₀cn0 9395 mod cmo 10577

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 106 ax-ia2 107 ax-ia3 108 ax-in1 617 ax-in2 618 ax-io 714 ax-5 1493 ax-7 1494 ax-gen 1495 ax-ie1 1539 ax-ie2 1540 ax-8 1550 ax-10 1551 ax-11 1552 ax-i12 1553 ax-bndl 1555 ax-4 1556 ax-17 1572 ax-i9 1576 ax-ial 1580 ax-i5r 1581 ax-13 2202 ax-14 2203 ax-ext 2211 ax-sep 4205 ax-pow 4262 ax-pr 4297 ax-un 4528 ax-setind 4633 ax-cnex 8116 ax-resscn 8117 ax-1cn 8118 ax-1re 8119 ax-icn 8120 ax-addcl 8121 ax-addrcl 8122 ax-mulcl 8123 ax-mulrcl 8124 ax-addcom 8125 ax-mulcom 8126 ax-addass 8127 ax-mulass 8128 ax-distr 8129 ax-i2m1 8130 ax-0lt1 8131 ax-1rid 8132 ax-0id 8133 ax-rnegex 8134 ax-precex 8135 ax-cnre 8136 ax-pre-ltirr 8137 ax-pre-ltwlin 8138 ax-pre-lttrn 8139 ax-pre-apti 8140 ax-pre-ltadd 8141 ax-pre-mulgt0 8142 ax-pre-mulext 8143 ax-arch 8144

This theorem depends on definitions: df-bi 117 df-dc 840 df-3or 1003 df-3an 1004 df-tru 1398 df-fal 1401 df-nf 1507 df-sb 1809 df-eu 2080 df-mo 2081 df-clab 2216 df-cleq 2222 df-clel 2225 df-nfc 2361 df-ne 2401 df-nel 2496 df-ral 2513 df-rex 2514 df-reu 2515 df-rmo 2516 df-rab 2517 df-v 2802 df-sbc 3030 df-csb 3126 df-dif 3200 df-un 3202 df-in 3204 df-ss 3211 df-nul 3493 df-if 3604 df-pw 3652 df-sn 3673 df-pr 3674 df-op 3676 df-uni 3892 df-int 3927 df-iun 3970 df-br 4087 df-opab 4149 df-mpt 4150 df-id 4388 df-po 4391 df-iso 4392 df-xp 4729 df-rel 4730 df-cnv 4731 df-co 4732 df-dm 4733 df-rn 4734 df-res 4735 df-ima 4736 df-iota 5284 df-fun 5326 df-fn 5327 df-f 5328 df-fv 5332 df-riota 5966 df-ov 6016 df-oprab 6017 df-mpo 6018 df-1st 6298 df-2nd 6299 df-pnf 8209 df-mnf 8210 df-xr 8211 df-ltxr 8212 df-le 8213 df-sub 8345 df-neg 8346 df-reap 8748 df-ap 8755 df-div 8846 df-inn 9137 df-n0 9396 df-z 9473 df-q 9847 df-rp 9882 df-fl 10523 df-mod 10578

This theorem is referenced by: eucalginv 12621 eucalglt 12622

W3C validator