Theorem eucalgval

Description: Euclid's Algorithm eucalg 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 E for Euclid's Algorithm. (Contributed by Paul Chapman, 31-Mar-2011) (Revised by Mario Carneiro, 28-May-2014)

	Ref	Expression
Hypothesis	eucalgval.1	$$⊢E=\left(x\in {\mathbb{N}}_0,y\in {\mathbb{N}}_0⟼if\left(y=0,⟨x,y⟩,⟨y,x\mathrm{mod}y⟩\right)\right)$$
Assertion	eucalgval	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to E\left(X\right)=if\left(2^{nd}\left(X\right)=0,X,⟨2^{nd}\left(X\right),\mathrm{mod}\left(X\right)⟩\right)$$

Proof

Step	Hyp	Ref	Expression
1		eucalgval.1	$$⊢E=\left(x\in {\mathbb{N}}_0,y\in {\mathbb{N}}_0⟼if\left(y=0,⟨x,y⟩,⟨y,x\mathrm{mod}y⟩\right)\right)$$
2		df-ov	$$⊢1^{st}\left(X\right)E{2}^{nd}\left(X\right)=E\left(⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩\right)$$
3		xp1st	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to 1^{st}\left(X\right)\in {\mathbb{N}}_0$$
4		xp2nd	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to 2^{nd}\left(X\right)\in {\mathbb{N}}_0$$
5	1	eucalgval2	$$⊢\left(1^{st}\left(X\right)\in {\mathbb{N}}_0\wedge 2^{nd}\left(X\right)\in {\mathbb{N}}_0\right)\to 1^{st}\left(X\right)E{2}^{nd}\left(X\right)=if\left(2^{nd}\left(X\right)=0,⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩,⟨2^{nd}\left(X\right),1^{st}\left(X\right)\mathrm{mod}{2}^{nd}\left(X\right)⟩\right)$$
6	3 4 5	syl2anc	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to 1^{st}\left(X\right)E{2}^{nd}\left(X\right)=if\left(2^{nd}\left(X\right)=0,⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩,⟨2^{nd}\left(X\right),1^{st}\left(X\right)\mathrm{mod}{2}^{nd}\left(X\right)⟩\right)$$
7	2 6	eqtr3id	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to E\left(⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩\right)=if\left(2^{nd}\left(X\right)=0,⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩,⟨2^{nd}\left(X\right),1^{st}\left(X\right)\mathrm{mod}{2}^{nd}\left(X\right)⟩\right)$$
8		1st2nd2	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to X=⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩$$
9	8	fveq2d	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to E\left(X\right)=E\left(⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩\right)$$
10	8	fveq2d	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to \mathrm{mod}\left(X\right)=\mathrm{mod}\left(⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩\right)$$
11		df-ov	$$⊢1^{st}\left(X\right)\mathrm{mod}{2}^{nd}\left(X\right)=\mathrm{mod}\left(⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩\right)$$
12	10 11	eqtr4di	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to \mathrm{mod}\left(X\right)=1^{st}\left(X\right)\mathrm{mod}{2}^{nd}\left(X\right)$$
13	12	opeq2d	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to ⟨2^{nd}\left(X\right),\mathrm{mod}\left(X\right)⟩=⟨2^{nd}\left(X\right),1^{st}\left(X\right)\mathrm{mod}{2}^{nd}\left(X\right)⟩$$
14	8 13	ifeq12d	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to if\left(2^{nd}\left(X\right)=0,X,⟨2^{nd}\left(X\right),\mathrm{mod}\left(X\right)⟩\right)=if\left(2^{nd}\left(X\right)=0,⟨1^{st}\left(X\right),2^{nd}\left(X\right)⟩,⟨2^{nd}\left(X\right),1^{st}\left(X\right)\mathrm{mod}{2}^{nd}\left(X\right)⟩\right)$$
15	7 9 14	3eqtr4d	$$⊢X\in \left({\mathbb{N}}_0\times {\mathbb{N}}_0\right)\to E\left(X\right)=if\left(2^{nd}\left(X\right)=0,X,⟨2^{nd}\left(X\right),\mathrm{mod}\left(X\right)⟩\right)$$