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

Theorem odzval 13140
Description: Value of the order function. This is a function of functions; the inner argument selects the base (i.e. mod  N for some  N, often prime) and the outer argument selects the integer or equivalence class (if you want to think about it that way) from the integers mod  N. In order to ensure the supremum is well-defined, we only define the expression when  A and  N are coprime. (Contributed by Mario Carneiro, 23-Feb-2014.)
Assertion
Ref Expression
odzval  |-  ( ( N  e.  NN  /\  A  e.  ZZ  /\  ( A  gcd  N )  =  1 )  ->  (
( od Z `  N ) `  A
)  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
Distinct variable groups:    n, N    A, n

Proof of Theorem odzval
Dummy variables  m  x are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 oveq2 6056 . . . . . . . . 9  |-  ( m  =  N  ->  (
x  gcd  m )  =  ( x  gcd  N ) )
21eqeq1d 2420 . . . . . . . 8  |-  ( m  =  N  ->  (
( x  gcd  m
)  =  1  <->  (
x  gcd  N )  =  1 ) )
32rabbidv 2916 . . . . . . 7  |-  ( m  =  N  ->  { x  e.  ZZ  |  ( x  gcd  m )  =  1 }  =  {
x  e.  ZZ  | 
( x  gcd  N
)  =  1 } )
4 oveq1 6055 . . . . . . . . 9  |-  ( n  =  x  ->  (
n  gcd  N )  =  ( x  gcd  N ) )
54eqeq1d 2420 . . . . . . . 8  |-  ( n  =  x  ->  (
( n  gcd  N
)  =  1  <->  (
x  gcd  N )  =  1 ) )
65cbvrabv 2923 . . . . . . 7  |-  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  =  {
x  e.  ZZ  | 
( x  gcd  N
)  =  1 }
73, 6syl6eqr 2462 . . . . . 6  |-  ( m  =  N  ->  { x  e.  ZZ  |  ( x  gcd  m )  =  1 }  =  {
n  e.  ZZ  | 
( n  gcd  N
)  =  1 } )
8 breq1 4183 . . . . . . . 8  |-  ( m  =  N  ->  (
m  ||  ( (
x ^ n )  -  1 )  <->  N  ||  (
( x ^ n
)  -  1 ) ) )
98rabbidv 2916 . . . . . . 7  |-  ( m  =  N  ->  { n  e.  NN  |  m  ||  ( ( x ^
n )  -  1 ) }  =  {
n  e.  NN  |  N  ||  ( ( x ^ n )  - 
1 ) } )
109supeq1d 7417 . . . . . 6  |-  ( m  =  N  ->  sup ( { n  e.  NN  |  m  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  )  =  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
117, 10mpteq12dv 4255 . . . . 5  |-  ( m  =  N  ->  (
x  e.  { x  e.  ZZ  |  ( x  gcd  m )  =  1 }  |->  sup ( { n  e.  NN  |  m  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) )  =  ( x  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  |->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) ) )
12 df-odz 13117 . . . . 5  |-  od Z  =  ( m  e.  NN  |->  ( x  e. 
{ x  e.  ZZ  |  ( x  gcd  m )  =  1 }  |->  sup ( { n  e.  NN  |  m  ||  ( ( x ^
n )  -  1 ) } ,  RR ,  `'  <  ) ) )
13 zex 10255 . . . . . . 7  |-  ZZ  e.  _V
1413rabex 4322 . . . . . 6  |-  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  e.  _V
1514mptex 5933 . . . . 5  |-  ( x  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  |->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) )  e.  _V
1611, 12, 15fvmpt 5773 . . . 4  |-  ( N  e.  NN  ->  ( od Z `  N )  =  ( x  e. 
{ n  e.  ZZ  |  ( n  gcd  N )  =  1 } 
|->  sup ( { n  e.  NN  |  N  ||  ( ( x ^
n )  -  1 ) } ,  RR ,  `'  <  ) ) )
1716fveq1d 5697 . . 3  |-  ( N  e.  NN  ->  (
( od Z `  N ) `  A
)  =  ( ( x  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  |->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) ) `  A
) )
18 oveq1 6055 . . . . . 6  |-  ( n  =  A  ->  (
n  gcd  N )  =  ( A  gcd  N ) )
1918eqeq1d 2420 . . . . 5  |-  ( n  =  A  ->  (
( n  gcd  N
)  =  1  <->  ( A  gcd  N )  =  1 ) )
2019elrab 3060 . . . 4  |-  ( A  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  <->  ( A  e.  ZZ  /\  ( A  gcd  N )  =  1 ) )
21 oveq1 6055 . . . . . . . . 9  |-  ( x  =  A  ->  (
x ^ n )  =  ( A ^
n ) )
2221oveq1d 6063 . . . . . . . 8  |-  ( x  =  A  ->  (
( x ^ n
)  -  1 )  =  ( ( A ^ n )  - 
1 ) )
2322breq2d 4192 . . . . . . 7  |-  ( x  =  A  ->  ( N  ||  ( ( x ^ n )  - 
1 )  <->  N  ||  (
( A ^ n
)  -  1 ) ) )
2423rabbidv 2916 . . . . . 6  |-  ( x  =  A  ->  { n  e.  NN  |  N  ||  ( ( x ^
n )  -  1 ) }  =  {
n  e.  NN  |  N  ||  ( ( A ^ n )  - 
1 ) } )
2524supeq1d 7417 . . . . 5  |-  ( x  =  A  ->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  )  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
26 eqid 2412 . . . . 5  |-  ( x  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  |->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) )  =  ( x  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  |->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
27 ltso 9120 . . . . . . 7  |-  <  Or  RR
28 cnvso 5378 . . . . . . 7  |-  (  < 
Or  RR  <->  `'  <  Or  RR )
2927, 28mpbi 200 . . . . . 6  |-  `'  <  Or  RR
3029supex 7432 . . . . 5  |-  sup ( { n  e.  NN  |  N  ||  ( ( A ^ n )  -  1 ) } ,  RR ,  `'  <  )  e.  _V
3125, 26, 30fvmpt 5773 . . . 4  |-  ( A  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  ->  (
( x  e.  {
n  e.  ZZ  | 
( n  gcd  N
)  =  1 } 
|->  sup ( { n  e.  NN  |  N  ||  ( ( x ^
n )  -  1 ) } ,  RR ,  `'  <  ) ) `
 A )  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^
n )  -  1 ) } ,  RR ,  `'  <  ) )
3220, 31sylbir 205 . . 3  |-  ( ( A  e.  ZZ  /\  ( A  gcd  N )  =  1 )  -> 
( ( x  e. 
{ n  e.  ZZ  |  ( n  gcd  N )  =  1 } 
|->  sup ( { n  e.  NN  |  N  ||  ( ( x ^
n )  -  1 ) } ,  RR ,  `'  <  ) ) `
 A )  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^
n )  -  1 ) } ,  RR ,  `'  <  ) )
3317, 32sylan9eq 2464 . 2  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  ( A  gcd  N
)  =  1 ) )  ->  ( ( od Z `  N ) `
 A )  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^
n )  -  1 ) } ,  RR ,  `'  <  ) )
34333impb 1149 1  |-  ( ( N  e.  NN  /\  A  e.  ZZ  /\  ( A  gcd  N )  =  1 )  ->  (
( od Z `  N ) `  A
)  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
Colors of variables: wff set class
Syntax hints:    -> wi 4    /\ wa 359    /\ w3a 936    = wceq 1649    e. wcel 1721   {crab 2678   class class class wbr 4180    e. cmpt 4234    Or wor 4470   `'ccnv 4844   ` cfv 5421  (class class class)co 6048   supcsup 7411   RRcr 8953   1c1 8955    < clt 9084    - cmin 9255   NNcn 9964   ZZcz 10246   ^cexp 11345    || cdivides 12815    gcd cgcd 12969   od
Zcodz 13115
This theorem is referenced by:  odzcllem  13141  odzdvds  13144
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1662  ax-8 1683  ax-13 1723  ax-14 1725  ax-6 1740  ax-7 1745  ax-11 1757  ax-12 1946  ax-ext 2393  ax-rep 4288  ax-sep 4298  ax-nul 4306  ax-pow 4345  ax-pr 4371  ax-un 4668  ax-cnex 9010  ax-resscn 9011  ax-pre-lttri 9028  ax-pre-lttrn 9029
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2266  df-mo 2267  df-clab 2399  df-cleq 2405  df-clel 2408  df-nfc 2537  df-ne 2577  df-nel 2578  df-ral 2679  df-rex 2680  df-reu 2681  df-rmo 2682  df-rab 2683  df-v 2926  df-sbc 3130  df-csb 3220  df-dif 3291  df-un 3293  df-in 3295  df-ss 3302  df-nul 3597  df-if 3708  df-pw 3769  df-sn 3788  df-pr 3789  df-op 3791  df-uni 3984  df-iun 4063  df-br 4181  df-opab 4235  df-mpt 4236  df-id 4466  df-po 4471  df-so 4472  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 5385  df-fun 5423  df-fn 5424  df-f 5425  df-f1 5426  df-fo 5427  df-f1o 5428  df-fv 5429  df-ov 6051  df-er 6872  df-en 7077  df-dom 7078  df-sdom 7079  df-sup 7412  df-pnf 9086  df-mnf 9087  df-ltxr 9089  df-neg 9258  df-z 10247  df-odz 13117
  Copyright terms: Public domain W3C validator