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

Theorem eucalginv 13764
Description: The invariant of the step function  E for Euclid's Algorithm is the  gcd operator applied to the state. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 29-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
eucalginv  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  gcd  `  ( E `  X
) )  =  (  gcd  `  X )
)
Distinct variable group:    x, y, X
Allowed substitution hints:    E( x, y)

Proof of Theorem eucalginv
StepHypRef Expression
1 eucalgval.1 . . . 4  |-  E  =  ( x  e.  NN0 ,  y  e.  NN0  |->  if ( y  =  0 , 
<. x ,  y >. ,  <. y ,  ( x  mod  y )
>. ) )
21eucalgval 13762 . . 3  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( E `
 X )  =  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) )
32fveq2d 5700 . 2  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  gcd  `  ( E `  X
) )  =  (  gcd  `  if (
( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) ) )
4 1st2nd2 6618 . . . . . . . . 9  |-  ( X  e.  ( NN0  X.  NN0 )  ->  X  = 
<. ( 1st `  X
) ,  ( 2nd `  X ) >. )
54adantr 465 . . . . . . . 8  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  X  =  <. ( 1st `  X
) ,  ( 2nd `  X ) >. )
65fveq2d 5700 . . . . . . 7  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  mod  `  X )  =  (  mod  `  <. ( 1st `  X ) ,  ( 2nd `  X
) >. ) )
7 df-ov 6099 . . . . . . 7  |-  ( ( 1st `  X )  mod  ( 2nd `  X
) )  =  (  mod  `  <. ( 1st `  X ) ,  ( 2nd `  X )
>. )
86, 7syl6eqr 2493 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  mod  `  X )  =  ( ( 1st `  X
)  mod  ( 2nd `  X ) ) )
98oveq2d 6112 . . . . 5  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 2nd `  X
)  gcd  (  mod  `  X ) )  =  ( ( 2nd `  X
)  gcd  ( ( 1st `  X )  mod  ( 2nd `  X
) ) ) )
10 nnz 10673 . . . . . . 7  |-  ( ( 2nd `  X )  e.  NN  ->  ( 2nd `  X )  e.  ZZ )
1110adantl 466 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 2nd `  X )  e.  ZZ )
12 xp1st 6611 . . . . . . . . . 10  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( 1st `  X )  e.  NN0 )
1312adantr 465 . . . . . . . . 9  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 1st `  X )  e. 
NN0 )
1413nn0zd 10750 . . . . . . . 8  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 1st `  X )  e.  ZZ )
15 zmodcl 11732 . . . . . . . 8  |-  ( ( ( 1st `  X
)  e.  ZZ  /\  ( 2nd `  X )  e.  NN )  -> 
( ( 1st `  X
)  mod  ( 2nd `  X ) )  e. 
NN0 )
1614, 15sylancom 667 . . . . . . 7  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 1st `  X
)  mod  ( 2nd `  X ) )  e. 
NN0 )
1716nn0zd 10750 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 1st `  X
)  mod  ( 2nd `  X ) )  e.  ZZ )
18 gcdcom 13709 . . . . . 6  |-  ( ( ( 2nd `  X
)  e.  ZZ  /\  ( ( 1st `  X
)  mod  ( 2nd `  X ) )  e.  ZZ )  ->  (
( 2nd `  X
)  gcd  ( ( 1st `  X )  mod  ( 2nd `  X
) ) )  =  ( ( ( 1st `  X )  mod  ( 2nd `  X ) )  gcd  ( 2nd `  X
) ) )
1911, 17, 18syl2anc 661 . . . . 5  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 2nd `  X
)  gcd  ( ( 1st `  X )  mod  ( 2nd `  X
) ) )  =  ( ( ( 1st `  X )  mod  ( 2nd `  X ) )  gcd  ( 2nd `  X
) ) )
20 modgcd 13725 . . . . . 6  |-  ( ( ( 1st `  X
)  e.  ZZ  /\  ( 2nd `  X )  e.  NN )  -> 
( ( ( 1st `  X )  mod  ( 2nd `  X ) )  gcd  ( 2nd `  X
) )  =  ( ( 1st `  X
)  gcd  ( 2nd `  X ) ) )
2114, 20sylancom 667 . . . . 5  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( ( 1st `  X
)  mod  ( 2nd `  X ) )  gcd  ( 2nd `  X
) )  =  ( ( 1st `  X
)  gcd  ( 2nd `  X ) ) )
229, 19, 213eqtrd 2479 . . . 4  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 2nd `  X
)  gcd  (  mod  `  X ) )  =  ( ( 1st `  X
)  gcd  ( 2nd `  X ) ) )
23 nnne0 10359 . . . . . . . . 9  |-  ( ( 2nd `  X )  e.  NN  ->  ( 2nd `  X )  =/=  0 )
2423adantl 466 . . . . . . . 8  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 2nd `  X )  =/=  0 )
2524neneqd 2629 . . . . . . 7  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  -.  ( 2nd `  X )  =  0 )
26 iffalse 3804 . . . . . . 7  |-  ( -.  ( 2nd `  X
)  =  0  ->  if ( ( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )  =  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )
2725, 26syl 16 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  if ( ( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )  =  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )
2827fveq2d 5700 . . . . 5  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  (  gcd  `  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)
29 df-ov 6099 . . . . 5  |-  ( ( 2nd `  X )  gcd  (  mod  `  X
) )  =  (  gcd  `  <. ( 2nd `  X ) ,  (  mod  `  X ) >. )
3028, 29syl6eqr 2493 . . . 4  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  ( ( 2nd `  X )  gcd  (  mod  `  X
) ) )
315fveq2d 5700 . . . . 5  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  X )  =  (  gcd  `  <. ( 1st `  X ) ,  ( 2nd `  X
) >. ) )
32 df-ov 6099 . . . . 5  |-  ( ( 1st `  X )  gcd  ( 2nd `  X
) )  =  (  gcd  `  <. ( 1st `  X ) ,  ( 2nd `  X )
>. )
3331, 32syl6eqr 2493 . . . 4  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  X )  =  ( ( 1st `  X
)  gcd  ( 2nd `  X ) ) )
3422, 30, 333eqtr4d 2485 . . 3  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  (  gcd  `  X ) )
35 iftrue 3802 . . . . 5  |-  ( ( 2nd `  X )  =  0  ->  if ( ( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )  =  X )
3635fveq2d 5700 . . . 4  |-  ( ( 2nd `  X )  =  0  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  (  gcd  `  X ) )
3736adantl 466 . . 3  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  =  0 )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  (  gcd  `  X ) )
38 xp2nd 6612 . . . 4  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( 2nd `  X )  e.  NN0 )
39 elnn0 10586 . . . 4  |-  ( ( 2nd `  X )  e.  NN0  <->  ( ( 2nd `  X )  e.  NN  \/  ( 2nd `  X
)  =  0 ) )
4038, 39sylib 196 . . 3  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( ( 2nd `  X )  e.  NN  \/  ( 2nd `  X )  =  0 ) )
4134, 37, 40mpjaodan 784 . 2  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) )  =  (  gcd  `  X
) )
423, 41eqtrd 2475 1  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  gcd  `  ( E `  X
) )  =  (  gcd  `  X )
)
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    \/ wo 368    /\ wa 369    = wceq 1369    e. wcel 1756    =/= wne 2611   ifcif 3796   <.cop 3888    X. cxp 4843   ` cfv 5423  (class class class)co 6096    e. cmpt2 6098   1stc1st 6580   2ndc2nd 6581   0cc0 9287   NNcn 10327   NN0cn0 10584   ZZcz 10651    mod cmo 11713    gcd cgcd 13695
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 2423  ax-sep 4418  ax-nul 4426  ax-pow 4475  ax-pr 4536  ax-un 6377  ax-cnex 9343  ax-resscn 9344  ax-1cn 9345  ax-icn 9346  ax-addcl 9347  ax-addrcl 9348  ax-mulcl 9349  ax-mulrcl 9350  ax-mulcom 9351  ax-addass 9352  ax-mulass 9353  ax-distr 9354  ax-i2m1 9355  ax-1ne0 9356  ax-1rid 9357  ax-rnegex 9358  ax-rrecex 9359  ax-cnre 9360  ax-pre-lttri 9361  ax-pre-lttrn 9362  ax-pre-ltadd 9363  ax-pre-mulgt0 9364  ax-pre-sup 9365
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1372  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2257  df-mo 2258  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2573  df-ne 2613  df-nel 2614  df-ral 2725  df-rex 2726  df-reu 2727  df-rmo 2728  df-rab 2729  df-v 2979  df-sbc 3192  df-csb 3294  df-dif 3336  df-un 3338  df-in 3340  df-ss 3347  df-pss 3349  df-nul 3643  df-if 3797  df-pw 3867  df-sn 3883  df-pr 3885  df-tp 3887  df-op 3889  df-uni 4097  df-iun 4178  df-br 4298  df-opab 4356  df-mpt 4357  df-tr 4391  df-eprel 4637  df-id 4641  df-po 4646  df-so 4647  df-fr 4684  df-we 4686  df-ord 4727  df-on 4728  df-lim 4729  df-suc 4730  df-xp 4851  df-rel 4852  df-cnv 4853  df-co 4854  df-dm 4855  df-rn 4856  df-res 4857  df-ima 4858  df-iota 5386  df-fun 5425  df-fn 5426  df-f 5427  df-f1 5428  df-fo 5429  df-f1o 5430  df-fv 5431  df-riota 6057  df-ov 6099  df-oprab 6100  df-mpt2 6101  df-om 6482  df-1st 6582  df-2nd 6583  df-recs 6837  df-rdg 6871  df-er 7106  df-en 7316  df-dom 7317  df-sdom 7318  df-sup 7696  df-pnf 9425  df-mnf 9426  df-xr 9427  df-ltxr 9428  df-le 9429  df-sub 9602  df-neg 9603  df-div 9999  df-nn 10328  df-2 10385  df-3 10386  df-n0 10585  df-z 10652  df-uz 10867  df-rp 10997  df-fl 11647  df-mod 11714  df-seq 11812  df-exp 11871  df-cj 12593  df-re 12594  df-im 12595  df-sqr 12729  df-abs 12730  df-dvds 13541  df-gcd 13696
This theorem is referenced by:  eucalg  13767
  Copyright terms: Public domain W3C validator