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

Theorem odzval 13862
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 )  ->  (
( odZ `  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 6098 . . . . . . . . 9  |-  ( m  =  N  ->  (
x  gcd  m )  =  ( x  gcd  N ) )
21eqeq1d 2450 . . . . . . . 8  |-  ( m  =  N  ->  (
( x  gcd  m
)  =  1  <->  (
x  gcd  N )  =  1 ) )
32rabbidv 2963 . . . . . . 7  |-  ( m  =  N  ->  { x  e.  ZZ  |  ( x  gcd  m )  =  1 }  =  {
x  e.  ZZ  | 
( x  gcd  N
)  =  1 } )
4 oveq1 6097 . . . . . . . . 9  |-  ( n  =  x  ->  (
n  gcd  N )  =  ( x  gcd  N ) )
54eqeq1d 2450 . . . . . . . 8  |-  ( n  =  x  ->  (
( n  gcd  N
)  =  1  <->  (
x  gcd  N )  =  1 ) )
65cbvrabv 2970 . . . . . . 7  |-  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  =  {
x  e.  ZZ  | 
( x  gcd  N
)  =  1 }
73, 6syl6eqr 2492 . . . . . 6  |-  ( m  =  N  ->  { x  e.  ZZ  |  ( x  gcd  m )  =  1 }  =  {
n  e.  ZZ  | 
( n  gcd  N
)  =  1 } )
8 breq1 4294 . . . . . . . 8  |-  ( m  =  N  ->  (
m  ||  ( (
x ^ n )  -  1 )  <->  N  ||  (
( x ^ n
)  -  1 ) ) )
98rabbidv 2963 . . . . . . 7  |-  ( m  =  N  ->  { n  e.  NN  |  m  ||  ( ( x ^
n )  -  1 ) }  =  {
n  e.  NN  |  N  ||  ( ( x ^ n )  - 
1 ) } )
109supeq1d 7695 . . . . . 6  |-  ( m  =  N  ->  sup ( { n  e.  NN  |  m  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  )  =  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
117, 10mpteq12dv 4369 . . . . 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 13839 . . . . 5  |-  odZ 
=  ( m  e.  NN  |->  ( x  e. 
{ x  e.  ZZ  |  ( x  gcd  m )  =  1 }  |->  sup ( { n  e.  NN  |  m  ||  ( ( x ^
n )  -  1 ) } ,  RR ,  `'  <  ) ) )
13 zex 10654 . . . . . . 7  |-  ZZ  e.  _V
1413rabex 4442 . . . . . 6  |-  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  e.  _V
1514mptex 5947 . . . . 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  ->  ( odZ `  N )  =  ( x  e. 
{ n  e.  ZZ  |  ( n  gcd  N )  =  1 } 
|->  sup ( { n  e.  NN  |  N  ||  ( ( x ^
n )  -  1 ) } ,  RR ,  `'  <  ) ) )
1716fveq1d 5692 . . 3  |-  ( N  e.  NN  ->  (
( odZ `  N ) `  A
)  =  ( ( x  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  |->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  ) ) `  A
) )
18 oveq1 6097 . . . . . 6  |-  ( n  =  A  ->  (
n  gcd  N )  =  ( A  gcd  N ) )
1918eqeq1d 2450 . . . . 5  |-  ( n  =  A  ->  (
( n  gcd  N
)  =  1  <->  ( A  gcd  N )  =  1 ) )
2019elrab 3116 . . . 4  |-  ( A  e.  { n  e.  ZZ  |  ( n  gcd  N )  =  1 }  <->  ( A  e.  ZZ  /\  ( A  gcd  N )  =  1 ) )
21 oveq1 6097 . . . . . . . . 9  |-  ( x  =  A  ->  (
x ^ n )  =  ( A ^
n ) )
2221oveq1d 6105 . . . . . . . 8  |-  ( x  =  A  ->  (
( x ^ n
)  -  1 )  =  ( ( A ^ n )  - 
1 ) )
2322breq2d 4303 . . . . . . 7  |-  ( x  =  A  ->  ( N  ||  ( ( x ^ n )  - 
1 )  <->  N  ||  (
( A ^ n
)  -  1 ) ) )
2423rabbidv 2963 . . . . . 6  |-  ( x  =  A  ->  { n  e.  NN  |  N  ||  ( ( x ^
n )  -  1 ) }  =  {
n  e.  NN  |  N  ||  ( ( A ^ n )  - 
1 ) } )
2524supeq1d 7695 . . . . 5  |-  ( x  =  A  ->  sup ( { n  e.  NN  |  N  ||  ( ( x ^ n )  -  1 ) } ,  RR ,  `'  <  )  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
26 eqid 2442 . . . . 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 gtso 9455 . . . . . 6  |-  `'  <  Or  RR
2827supex 7712 . . . . 5  |-  sup ( { n  e.  NN  |  N  ||  ( ( A ^ n )  -  1 ) } ,  RR ,  `'  <  )  e.  _V
2925, 26, 28fvmpt 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 ,  `'  <  ) )
3020, 29sylbir 213 . . 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 ,  `'  <  ) )
3117, 30sylan9eq 2494 . 2  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  ( A  gcd  N
)  =  1 ) )  ->  ( ( odZ `  N ) `
 A )  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^
n )  -  1 ) } ,  RR ,  `'  <  ) )
32313impb 1183 1  |-  ( ( N  e.  NN  /\  A  e.  ZZ  /\  ( A  gcd  N )  =  1 )  ->  (
( odZ `  N ) `  A
)  =  sup ( { n  e.  NN  |  N  ||  ( ( A ^ n )  -  1 ) } ,  RR ,  `'  <  ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    /\ wa 369    /\ w3a 965    = wceq 1369    e. wcel 1756   {crab 2718   class class class wbr 4291    e. cmpt 4349   `'ccnv 4838   ` cfv 5417  (class class class)co 6090   supcsup 7689   RRcr 9280   1c1 9282    < clt 9417    - cmin 9594   NNcn 10321   ZZcz 10645   ^cexp 11864    || cdivides 13534    gcd cgcd 13689   odZcodz 13837
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-rep 4402  ax-sep 4412  ax-nul 4420  ax-pow 4469  ax-pr 4530  ax-un 6371  ax-cnex 9337  ax-resscn 9338  ax-pre-lttri 9355  ax-pre-lttrn 9356
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 2429  df-cleq 2435  df-clel 2438  df-nfc 2567  df-ne 2607  df-nel 2608  df-ral 2719  df-rex 2720  df-reu 2721  df-rmo 2722  df-rab 2723  df-v 2973  df-sbc 3186  df-csb 3288  df-dif 3330  df-un 3332  df-in 3334  df-ss 3341  df-nul 3637  df-if 3791  df-pw 3861  df-sn 3877  df-pr 3879  df-op 3883  df-uni 4091  df-iun 4172  df-br 4292  df-opab 4350  df-mpt 4351  df-id 4635  df-po 4640  df-so 4641  df-xp 4845  df-rel 4846  df-cnv 4847  df-co 4848  df-dm 4849  df-rn 4850  df-res 4851  df-ima 4852  df-iota 5380  df-fun 5419  df-fn 5420  df-f 5421  df-f1 5422  df-fo 5423  df-f1o 5424  df-fv 5425  df-ov 6093  df-er 7100  df-en 7310  df-dom 7311  df-sdom 7312  df-sup 7690  df-pnf 9419  df-mnf 9420  df-ltxr 9422  df-neg 9597  df-z 10646  df-odz 13839
This theorem is referenced by:  odzcllem  13863  odzdvds  13866
  Copyright terms: Public domain W3C validator