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

Theorem eucalgval 13755
Description: Euclid's Algorithm eucalg 13760 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.)

Hypothesis
Ref Expression
eucalgval.1  |-  E  =  ( x  e.  NN0 ,  y  e.  NN0  |->  if ( y  =  0 , 
<. x ,  y >. ,  <. y ,  ( x  mod  y )
>. ) )
Assertion
Ref Expression
eucalgval  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( E `
 X )  =  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) )
Distinct variable group:    x, y, X
Allowed substitution hints:    E( x, y)

Proof of Theorem eucalgval
StepHypRef Expression
1 df-ov 6092 . . 3  |-  ( ( 1st `  X ) E ( 2nd `  X
) )  =  ( E `  <. ( 1st `  X ) ,  ( 2nd `  X
) >. )
2 xp1st 6604 . . . 4  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( 1st `  X )  e.  NN0 )
3 xp2nd 6605 . . . 4  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( 2nd `  X )  e.  NN0 )
4 eucalgval.1 . . . . 5  |-  E  =  ( x  e.  NN0 ,  y  e.  NN0  |->  if ( y  =  0 , 
<. x ,  y >. ,  <. y ,  ( x  mod  y )
>. ) )
54eucalgval2 13754 . . . 4  |-  ( ( ( 1st `  X
)  e.  NN0  /\  ( 2nd `  X )  e.  NN0 )  -> 
( ( 1st `  X
) E ( 2nd `  X ) )  =  if ( ( 2nd `  X )  =  0 ,  <. ( 1st `  X
) ,  ( 2nd `  X ) >. ,  <. ( 2nd `  X ) ,  ( ( 1st `  X )  mod  ( 2nd `  X ) )
>. ) )
62, 3, 5syl2anc 661 . . 3  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( ( 1st `  X ) E ( 2nd `  X
) )  =  if ( ( 2nd `  X
)  =  0 , 
<. ( 1st `  X
) ,  ( 2nd `  X ) >. ,  <. ( 2nd `  X ) ,  ( ( 1st `  X )  mod  ( 2nd `  X ) )
>. ) )
71, 6syl5eqr 2487 . 2  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( E `
 <. ( 1st `  X
) ,  ( 2nd `  X ) >. )  =  if ( ( 2nd `  X )  =  0 ,  <. ( 1st `  X
) ,  ( 2nd `  X ) >. ,  <. ( 2nd `  X ) ,  ( ( 1st `  X )  mod  ( 2nd `  X ) )
>. ) )
8 1st2nd2 6611 . . 3  |-  ( X  e.  ( NN0  X.  NN0 )  ->  X  = 
<. ( 1st `  X
) ,  ( 2nd `  X ) >. )
98fveq2d 5693 . 2  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( E `
 X )  =  ( E `  <. ( 1st `  X ) ,  ( 2nd `  X
) >. ) )
108fveq2d 5693 . . . . 5  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  mod  `  X )  =  (  mod  `  <. ( 1st `  X ) ,  ( 2nd `  X )
>. ) )
11 df-ov 6092 . . . . 5  |-  ( ( 1st `  X )  mod  ( 2nd `  X
) )  =  (  mod  `  <. ( 1st `  X ) ,  ( 2nd `  X )
>. )
1210, 11syl6eqr 2491 . . . 4  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  mod  `  X )  =  ( ( 1st `  X
)  mod  ( 2nd `  X ) ) )
1312opeq2d 4064 . . 3  |-  ( X  e.  ( NN0  X.  NN0 )  ->  <. ( 2nd `  X ) ,  (  mod  `  X
) >.  =  <. ( 2nd `  X ) ,  ( ( 1st `  X
)  mod  ( 2nd `  X ) ) >.
)
148, 13ifeq12d 3807 . 2  |-  ( X  e.  ( NN0  X.  NN0 )  ->  if ( ( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )  =  if ( ( 2nd `  X
)  =  0 , 
<. ( 1st `  X
) ,  ( 2nd `  X ) >. ,  <. ( 2nd `  X ) ,  ( ( 1st `  X )  mod  ( 2nd `  X ) )
>. ) )
157, 9, 143eqtr4d 2483 1  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( E `
 X )  =  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    = wceq 1369    e. wcel 1756   ifcif 3789   <.cop 3881    X. cxp 4836   ` cfv 5416  (class class class)co 6089    e. cmpt2 6091   1stc1st 6573   2ndc2nd 6574   0cc0 9280   NN0cn0 10577    mod cmo 11706
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1591  ax-4 1602  ax-5 1670  ax-6 1708  ax-7 1728  ax-8 1758  ax-9 1760  ax-10 1775  ax-11 1780  ax-12 1792  ax-13 1943  ax-ext 2422  ax-sep 4411  ax-nul 4419  ax-pow 4468  ax-pr 4529  ax-un 6370
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3an 967  df-tru 1372  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2257  df-mo 2258  df-clab 2428  df-cleq 2434  df-clel 2437  df-nfc 2566  df-ne 2606  df-ral 2718  df-rex 2719  df-rab 2722  df-v 2972  df-sbc 3185  df-dif 3329  df-un 3331  df-in 3333  df-ss 3340  df-nul 3636  df-if 3790  df-sn 3876  df-pr 3878  df-op 3882  df-uni 4090  df-br 4291  df-opab 4349  df-mpt 4350  df-id 4634  df-xp 4844  df-rel 4845  df-cnv 4846  df-co 4847  df-dm 4848  df-rn 4849  df-iota 5379  df-fun 5418  df-fv 5424  df-ov 6092  df-oprab 6093  df-mpt2 6094  df-1st 6575  df-2nd 6576
This theorem is referenced by:  eucalginv  13757  eucalglt  13758
  Copyright terms: Public domain W3C validator