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

Theorem eucalginv 12851
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 12849 . . 3  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( E `
 X )  =  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) )
32fveq2d 5612 . 2  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  gcd  `  ( E `  X
) )  =  (  gcd  `  if (
( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) ) )
4 1st2nd2 6246 . . . . . . . . 9  |-  ( X  e.  ( NN0  X.  NN0 )  ->  X  = 
<. ( 1st `  X
) ,  ( 2nd `  X ) >. )
54adantr 451 . . . . . . . 8  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  X  =  <. ( 1st `  X
) ,  ( 2nd `  X ) >. )
65fveq2d 5612 . . . . . . 7  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  mod  `  X )  =  (  mod  `  <. ( 1st `  X ) ,  ( 2nd `  X
) >. ) )
7 df-ov 5948 . . . . . . 7  |-  ( ( 1st `  X )  mod  ( 2nd `  X
) )  =  (  mod  `  <. ( 1st `  X ) ,  ( 2nd `  X )
>. )
86, 7syl6eqr 2408 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  mod  `  X )  =  ( ( 1st `  X
)  mod  ( 2nd `  X ) ) )
98oveq2d 5961 . . . . 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 10137 . . . . . . 7  |-  ( ( 2nd `  X )  e.  NN  ->  ( 2nd `  X )  e.  ZZ )
1110adantl 452 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 2nd `  X )  e.  ZZ )
12 xp1st 6236 . . . . . . . . . 10  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( 1st `  X )  e.  NN0 )
1312adantr 451 . . . . . . . . 9  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 1st `  X )  e. 
NN0 )
1413nn0zd 10207 . . . . . . . 8  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 1st `  X )  e.  ZZ )
15 zmodcl 11081 . . . . . . . 8  |-  ( ( ( 1st `  X
)  e.  ZZ  /\  ( 2nd `  X )  e.  NN )  -> 
( ( 1st `  X
)  mod  ( 2nd `  X ) )  e. 
NN0 )
1614, 15sylancom 648 . . . . . . 7  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 1st `  X
)  mod  ( 2nd `  X ) )  e. 
NN0 )
1716nn0zd 10207 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 1st `  X
)  mod  ( 2nd `  X ) )  e.  ZZ )
18 gcdcom 12796 . . . . . 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 642 . . . . 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 12812 . . . . . 6  |-  ( ( ( 1st `  X
)  e.  ZZ  /\  ( 2nd `  X )  e.  NN )  -> 
( ( ( 1st `  X )  mod  ( 2nd `  X ) )  gcd  ( 2nd `  X
) )  =  ( ( 1st `  X
)  gcd  ( 2nd `  X ) ) )
2114, 20sylancom 648 . . . . 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 2394 . . . 4  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (
( 2nd `  X
)  gcd  (  mod  `  X ) )  =  ( ( 1st `  X
)  gcd  ( 2nd `  X ) ) )
23 nnne0 9868 . . . . . . . . 9  |-  ( ( 2nd `  X )  e.  NN  ->  ( 2nd `  X )  =/=  0 )
2423adantl 452 . . . . . . . 8  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  ( 2nd `  X )  =/=  0 )
2524neneqd 2537 . . . . . . 7  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  -.  ( 2nd `  X )  =  0 )
26 iffalse 3648 . . . . . . 7  |-  ( -.  ( 2nd `  X
)  =  0  ->  if ( ( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )  =  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )
2725, 26syl 15 . . . . . 6  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  if ( ( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )  =  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )
2827fveq2d 5612 . . . . 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 5948 . . . . 5  |-  ( ( 2nd `  X )  gcd  (  mod  `  X
) )  =  (  gcd  `  <. ( 2nd `  X ) ,  (  mod  `  X ) >. )
3028, 29syl6eqr 2408 . . . 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 5612 . . . . 5  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  X )  =  (  gcd  `  <. ( 1st `  X ) ,  ( 2nd `  X
) >. ) )
32 df-ov 5948 . . . . 5  |-  ( ( 1st `  X )  gcd  ( 2nd `  X
) )  =  (  gcd  `  <. ( 1st `  X ) ,  ( 2nd `  X )
>. )
3331, 32syl6eqr 2408 . . . 4  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  X )  =  ( ( 1st `  X
)  gcd  ( 2nd `  X ) ) )
3422, 30, 333eqtr4d 2400 . . 3  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  e.  NN )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  (  gcd  `  X ) )
35 iftrue 3647 . . . . 5  |-  ( ( 2nd `  X )  =  0  ->  if ( ( 2nd `  X
)  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. )  =  X )
3635fveq2d 5612 . . . 4  |-  ( ( 2nd `  X )  =  0  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  (  gcd  `  X ) )
3736adantl 452 . . 3  |-  ( ( X  e.  ( NN0 
X.  NN0 )  /\  ( 2nd `  X )  =  0 )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X
) ,  (  mod  `  X ) >. )
)  =  (  gcd  `  X ) )
38 xp2nd 6237 . . . 4  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( 2nd `  X )  e.  NN0 )
39 elnn0 10059 . . . 4  |-  ( ( 2nd `  X )  e.  NN0  <->  ( ( 2nd `  X )  e.  NN  \/  ( 2nd `  X
)  =  0 ) )
4038, 39sylib 188 . . 3  |-  ( X  e.  ( NN0  X.  NN0 )  ->  ( ( 2nd `  X )  e.  NN  \/  ( 2nd `  X )  =  0 ) )
4134, 37, 40mpjaodan 761 . 2  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  gcd  `  if ( ( 2nd `  X )  =  0 ,  X ,  <. ( 2nd `  X ) ,  (  mod  `  X
) >. ) )  =  (  gcd  `  X
) )
423, 41eqtrd 2390 1  |-  ( X  e.  ( NN0  X.  NN0 )  ->  (  gcd  `  ( E `  X
) )  =  (  gcd  `  X )
)
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    \/ wo 357    /\ wa 358    = wceq 1642    e. wcel 1710    =/= wne 2521   ifcif 3641   <.cop 3719    X. cxp 4769   ` cfv 5337  (class class class)co 5945    e. cmpt2 5947   1stc1st 6207   2ndc2nd 6208   0cc0 8827   NNcn 9836   NN0cn0 10057   ZZcz 10116    mod cmo 11065    gcd cgcd 12782
This theorem is referenced by:  eucalg  12854
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1546  ax-5 1557  ax-17 1616  ax-9 1654  ax-8 1675  ax-13 1712  ax-14 1714  ax-6 1729  ax-7 1734  ax-11 1746  ax-12 1930  ax-ext 2339  ax-sep 4222  ax-nul 4230  ax-pow 4269  ax-pr 4295  ax-un 4594  ax-cnex 8883  ax-resscn 8884  ax-1cn 8885  ax-icn 8886  ax-addcl 8887  ax-addrcl 8888  ax-mulcl 8889  ax-mulrcl 8890  ax-mulcom 8891  ax-addass 8892  ax-mulass 8893  ax-distr 8894  ax-i2m1 8895  ax-1ne0 8896  ax-1rid 8897  ax-rnegex 8898  ax-rrecex 8899  ax-cnre 8900  ax-pre-lttri 8901  ax-pre-lttrn 8902  ax-pre-ltadd 8903  ax-pre-mulgt0 8904  ax-pre-sup 8905
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1319  df-ex 1542  df-nf 1545  df-sb 1649  df-eu 2213  df-mo 2214  df-clab 2345  df-cleq 2351  df-clel 2354  df-nfc 2483  df-ne 2523  df-nel 2524  df-ral 2624  df-rex 2625  df-reu 2626  df-rmo 2627  df-rab 2628  df-v 2866  df-sbc 3068  df-csb 3158  df-dif 3231  df-un 3233  df-in 3235  df-ss 3242  df-pss 3244  df-nul 3532  df-if 3642  df-pw 3703  df-sn 3722  df-pr 3723  df-tp 3724  df-op 3725  df-uni 3909  df-iun 3988  df-br 4105  df-opab 4159  df-mpt 4160  df-tr 4195  df-eprel 4387  df-id 4391  df-po 4396  df-so 4397  df-fr 4434  df-we 4436  df-ord 4477  df-on 4478  df-lim 4479  df-suc 4480  df-om 4739  df-xp 4777  df-rel 4778  df-cnv 4779  df-co 4780  df-dm 4781  df-rn 4782  df-res 4783  df-ima 4784  df-iota 5301  df-fun 5339  df-fn 5340  df-f 5341  df-f1 5342  df-fo 5343  df-f1o 5344  df-fv 5345  df-ov 5948  df-oprab 5949  df-mpt2 5950  df-1st 6209  df-2nd 6210  df-riota 6391  df-recs 6475  df-rdg 6510  df-er 6747  df-en 6952  df-dom 6953  df-sdom 6954  df-sup 7284  df-pnf 8959  df-mnf 8960  df-xr 8961  df-ltxr 8962  df-le 8963  df-sub 9129  df-neg 9130  df-div 9514  df-nn 9837  df-2 9894  df-3 9895  df-n0 10058  df-z 10117  df-uz 10323  df-rp 10447  df-fl 11017  df-mod 11066  df-seq 11139  df-exp 11198  df-cj 11680  df-re 11681  df-im 11682  df-sqr 11816  df-abs 11817  df-dvds 12629  df-gcd 12783
  Copyright terms: Public domain W3C validator