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

Theorem znunit 18729
Description: The units of ℤ/nℤ are the integers coprime to the base. (Contributed by Mario Carneiro, 18-Apr-2016.)
Hypotheses
Ref Expression
znchr.y  |-  Y  =  (ℤ/n `  N )
znunit.u  |-  U  =  (Unit `  Y )
znunit.l  |-  L  =  ( ZRHom `  Y
)
Assertion
Ref Expression
znunit  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( ( L `  A )  e.  U  <->  ( A  gcd  N )  =  1 ) )

Proof of Theorem znunit
Dummy variables  m  n  x are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 znchr.y . . . . 5  |-  Y  =  (ℤ/n `  N )
21zncrng 18710 . . . 4  |-  ( N  e.  NN0  ->  Y  e. 
CRing )
32adantr 465 . . 3  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  Y  e.  CRing )
4 znunit.u . . . 4  |-  U  =  (Unit `  Y )
5 eqid 2457 . . . 4  |-  ( 1r
`  Y )  =  ( 1r `  Y
)
6 eqid 2457 . . . 4  |-  ( ||r `  Y
)  =  ( ||r `  Y
)
74, 5, 6crngunit 17438 . . 3  |-  ( Y  e.  CRing  ->  ( ( L `  A )  e.  U  <->  ( L `  A ) ( ||r `  Y
) ( 1r `  Y ) ) )
83, 7syl 16 . 2  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( ( L `  A )  e.  U  <->  ( L `  A ) ( ||r `
 Y ) ( 1r `  Y ) ) )
9 eqid 2457 . . . . . . 7  |-  ( Base `  Y )  =  (
Base `  Y )
10 znunit.l . . . . . . 7  |-  L  =  ( ZRHom `  Y
)
111, 9, 10znzrhfo 18713 . . . . . 6  |-  ( N  e.  NN0  ->  L : ZZ -onto-> ( Base `  Y
) )
1211adantr 465 . . . . 5  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  L : ZZ -onto-> ( Base `  Y ) )
13 fof 5801 . . . . 5  |-  ( L : ZZ -onto-> ( Base `  Y )  ->  L : ZZ --> ( Base `  Y
) )
1412, 13syl 16 . . . 4  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  L : ZZ --> ( Base `  Y ) )
15 ffvelrn 6030 . . . 4  |-  ( ( L : ZZ --> ( Base `  Y )  /\  A  e.  ZZ )  ->  ( L `  A )  e.  ( Base `  Y
) )
1614, 15sylancom 667 . . 3  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( L `  A
)  e.  ( Base `  Y ) )
17 eqid 2457 . . . 4  |-  ( .r
`  Y )  =  ( .r `  Y
)
189, 6, 17dvdsr2 17423 . . 3  |-  ( ( L `  A )  e.  ( Base `  Y
)  ->  ( ( L `  A )
( ||r `
 Y ) ( 1r `  Y )  <->  E. x  e.  ( Base `  Y ) ( x ( .r `  Y ) ( L `
 A ) )  =  ( 1r `  Y ) ) )
1916, 18syl 16 . 2  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( ( L `  A ) ( ||r `  Y
) ( 1r `  Y )  <->  E. x  e.  ( Base `  Y
) ( x ( .r `  Y ) ( L `  A
) )  =  ( 1r `  Y ) ) )
20 forn 5804 . . . . . 6  |-  ( L : ZZ -onto-> ( Base `  Y )  ->  ran  L  =  ( Base `  Y
) )
2112, 20syl 16 . . . . 5  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ran  L  =  (
Base `  Y )
)
2221rexeqdv 3061 . . . 4  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. x  e. 
ran  L ( x ( .r `  Y
) ( L `  A ) )  =  ( 1r `  Y
)  <->  E. x  e.  (
Base `  Y )
( x ( .r
`  Y ) ( L `  A ) )  =  ( 1r
`  Y ) ) )
23 ffn 5737 . . . . 5  |-  ( L : ZZ --> ( Base `  Y )  ->  L  Fn  ZZ )
24 oveq1 6303 . . . . . . 7  |-  ( x  =  ( L `  n )  ->  (
x ( .r `  Y ) ( L `
 A ) )  =  ( ( L `
 n ) ( .r `  Y ) ( L `  A
) ) )
2524eqeq1d 2459 . . . . . 6  |-  ( x  =  ( L `  n )  ->  (
( x ( .r
`  Y ) ( L `  A ) )  =  ( 1r
`  Y )  <->  ( ( L `  n )
( .r `  Y
) ( L `  A ) )  =  ( 1r `  Y
) ) )
2625rexrn 6034 . . . . 5  |-  ( L  Fn  ZZ  ->  ( E. x  e.  ran  L ( x ( .r
`  Y ) ( L `  A ) )  =  ( 1r
`  Y )  <->  E. n  e.  ZZ  ( ( L `
 n ) ( .r `  Y ) ( L `  A
) )  =  ( 1r `  Y ) ) )
2714, 23, 263syl 20 . . . 4  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. x  e. 
ran  L ( x ( .r `  Y
) ( L `  A ) )  =  ( 1r `  Y
)  <->  E. n  e.  ZZ  ( ( L `  n ) ( .r
`  Y ) ( L `  A ) )  =  ( 1r
`  Y ) ) )
2822, 27bitr3d 255 . . 3  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. x  e.  ( Base `  Y
) ( x ( .r `  Y ) ( L `  A
) )  =  ( 1r `  Y )  <->  E. n  e.  ZZ  ( ( L `  n ) ( .r
`  Y ) ( L `  A ) )  =  ( 1r
`  Y ) ) )
29 crngring 17336 . . . . . . . . . 10  |-  ( Y  e.  CRing  ->  Y  e.  Ring )
303, 29syl 16 . . . . . . . . 9  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  Y  e.  Ring )
3110zrhrhm 18676 . . . . . . . . 9  |-  ( Y  e.  Ring  ->  L  e.  (ring RingHom  Y ) )
3230, 31syl 16 . . . . . . . 8  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  L  e.  (ring RingHom  Y ) )
3332adantr 465 . . . . . . 7  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  L  e.  (ring RingHom  Y
) )
34 simpr 461 . . . . . . 7  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  n  e.  ZZ )
35 simplr 755 . . . . . . 7  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  A  e.  ZZ )
36 zringbas 18621 . . . . . . . 8  |-  ZZ  =  ( Base ` ring )
37 zringmulr 18624 . . . . . . . 8  |-  x.  =  ( .r ` ring )
3836, 37, 17rhmmul 17503 . . . . . . 7  |-  ( ( L  e.  (ring RingHom  Y )  /\  n  e.  ZZ  /\  A  e.  ZZ )  ->  ( L `  ( n  x.  A ) )  =  ( ( L `  n ) ( .r
`  Y ) ( L `  A ) ) )
3933, 34, 35, 38syl3anc 1228 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  ( L `  ( n  x.  A
) )  =  ( ( L `  n
) ( .r `  Y ) ( L `
 A ) ) )
4030adantr 465 . . . . . . 7  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  Y  e.  Ring )
4110, 5zrh1 18677 . . . . . . 7  |-  ( Y  e.  Ring  ->  ( L `
 1 )  =  ( 1r `  Y
) )
4240, 41syl 16 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  ( L ` 
1 )  =  ( 1r `  Y ) )
4339, 42eqeq12d 2479 . . . . 5  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  ( ( L `
 ( n  x.  A ) )  =  ( L `  1
)  <->  ( ( L `
 n ) ( .r `  Y ) ( L `  A
) )  =  ( 1r `  Y ) ) )
44 simpll 753 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  N  e.  NN0 )
4534, 35zmulcld 10996 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  ( n  x.  A )  e.  ZZ )
46 1zzd 10916 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  1  e.  ZZ )
471, 10zndvds 18715 . . . . . 6  |-  ( ( N  e.  NN0  /\  ( n  x.  A
)  e.  ZZ  /\  1  e.  ZZ )  ->  ( ( L `  ( n  x.  A
) )  =  ( L `  1 )  <-> 
N  ||  ( (
n  x.  A )  -  1 ) ) )
4844, 45, 46, 47syl3anc 1228 . . . . 5  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  ( ( L `
 ( n  x.  A ) )  =  ( L `  1
)  <->  N  ||  ( ( n  x.  A )  -  1 ) ) )
4943, 48bitr3d 255 . . . 4  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  ( ( ( L `  n ) ( .r `  Y
) ( L `  A ) )  =  ( 1r `  Y
)  <->  N  ||  ( ( n  x.  A )  -  1 ) ) )
5049rexbidva 2965 . . 3  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. n  e.  ZZ  ( ( L `
 n ) ( .r `  Y ) ( L `  A
) )  =  ( 1r `  Y )  <->  E. n  e.  ZZ  N  ||  ( ( n  x.  A )  - 
1 ) ) )
51 simplr 755 . . . . . . . . . 10  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  ->  A  e.  ZZ )
52 nn0z 10908 . . . . . . . . . . 11  |-  ( N  e.  NN0  ->  N  e.  ZZ )
5352ad2antrr 725 . . . . . . . . . 10  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  ->  N  e.  ZZ )
54 gcddvds 14165 . . . . . . . . . 10  |-  ( ( A  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( A  gcd  N )  ||  A  /\  ( A  gcd  N ) 
||  N ) )
5551, 53, 54syl2anc 661 . . . . . . . . 9  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( ( A  gcd  N )  ||  A  /\  ( A  gcd  N ) 
||  N ) )
5655simpld 459 . . . . . . . 8  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  ||  A )
5751, 53gcdcld 14168 . . . . . . . . . 10  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  e.  NN0 )
5857nn0zd 10988 . . . . . . . . 9  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  e.  ZZ )
5934adantrr 716 . . . . . . . . 9  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  ->  n  e.  ZZ )
60 dvdsmultr2 14033 . . . . . . . . 9  |-  ( ( ( A  gcd  N
)  e.  ZZ  /\  n  e.  ZZ  /\  A  e.  ZZ )  ->  (
( A  gcd  N
)  ||  A  ->  ( A  gcd  N ) 
||  ( n  x.  A ) ) )
6158, 59, 51, 60syl3anc 1228 . . . . . . . 8  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( ( A  gcd  N )  ||  A  -> 
( A  gcd  N
)  ||  ( n  x.  A ) ) )
6256, 61mpd 15 . . . . . . 7  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  ||  ( n  x.  A ) )
6345adantrr 716 . . . . . . . 8  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( n  x.  A
)  e.  ZZ )
64 1zzd 10916 . . . . . . . 8  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
1  e.  ZZ )
6555simprd 463 . . . . . . . . 9  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  ||  N )
66 simprr 757 . . . . . . . . 9  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  ->  N  ||  ( ( n  x.  A )  - 
1 ) )
67 peano2zm 10928 . . . . . . . . . . 11  |-  ( ( n  x.  A )  e.  ZZ  ->  (
( n  x.  A
)  -  1 )  e.  ZZ )
6863, 67syl 16 . . . . . . . . . 10  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( ( n  x.  A )  -  1 )  e.  ZZ )
69 dvdstr 14030 . . . . . . . . . 10  |-  ( ( ( A  gcd  N
)  e.  ZZ  /\  N  e.  ZZ  /\  (
( n  x.  A
)  -  1 )  e.  ZZ )  -> 
( ( ( A  gcd  N )  ||  N  /\  N  ||  (
( n  x.  A
)  -  1 ) )  ->  ( A  gcd  N )  ||  (
( n  x.  A
)  -  1 ) ) )
7058, 53, 68, 69syl3anc 1228 . . . . . . . . 9  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( ( ( A  gcd  N )  ||  N  /\  N  ||  (
( n  x.  A
)  -  1 ) )  ->  ( A  gcd  N )  ||  (
( n  x.  A
)  -  1 ) ) )
7165, 66, 70mp2and 679 . . . . . . . 8  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  ||  ( (
n  x.  A )  -  1 ) )
72 dvdssub2 14035 . . . . . . . 8  |-  ( ( ( ( A  gcd  N )  e.  ZZ  /\  ( n  x.  A
)  e.  ZZ  /\  1  e.  ZZ )  /\  ( A  gcd  N
)  ||  ( (
n  x.  A )  -  1 ) )  ->  ( ( A  gcd  N )  ||  ( n  x.  A
)  <->  ( A  gcd  N )  ||  1 ) )
7358, 63, 64, 71, 72syl31anc 1231 . . . . . . 7  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( ( A  gcd  N )  ||  ( n  x.  A )  <->  ( A  gcd  N )  ||  1
) )
7462, 73mpbid 210 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  ||  1 )
75 dvds1 14046 . . . . . . 7  |-  ( ( A  gcd  N )  e.  NN0  ->  ( ( A  gcd  N ) 
||  1  <->  ( A  gcd  N )  =  1 ) )
7657, 75syl 16 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( ( A  gcd  N )  ||  1  <->  ( A  gcd  N )  =  1 ) )
7774, 76mpbid 210 . . . . 5  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  ( n  e.  ZZ  /\  N  ||  ( ( n  x.  A )  -  1 ) ) )  -> 
( A  gcd  N
)  =  1 )
7877rexlimdvaa 2950 . . . 4  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. n  e.  ZZ  N  ||  (
( n  x.  A
)  -  1 )  ->  ( A  gcd  N )  =  1 ) )
79 simpr 461 . . . . . . 7  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  A  e.  ZZ )
8052adantr 465 . . . . . . 7  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  N  e.  ZZ )
81 bezout 14192 . . . . . . 7  |-  ( ( A  e.  ZZ  /\  N  e.  ZZ )  ->  E. n  e.  ZZ  E. m  e.  ZZ  ( A  gcd  N )  =  ( ( A  x.  n )  +  ( N  x.  m ) ) )
8279, 80, 81syl2anc 661 . . . . . 6  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  E. n  e.  ZZ  E. m  e.  ZZ  ( A  gcd  N )  =  ( ( A  x.  n )  +  ( N  x.  m ) ) )
83 eqeq1 2461 . . . . . . 7  |-  ( ( A  gcd  N )  =  1  ->  (
( A  gcd  N
)  =  ( ( A  x.  n )  +  ( N  x.  m ) )  <->  1  =  ( ( A  x.  n )  +  ( N  x.  m ) ) ) )
84832rexbidv 2975 . . . . . 6  |-  ( ( A  gcd  N )  =  1  ->  ( E. n  e.  ZZ  E. m  e.  ZZ  ( A  gcd  N )  =  ( ( A  x.  n )  +  ( N  x.  m ) )  <->  E. n  e.  ZZ  E. m  e.  ZZ  1  =  ( ( A  x.  n )  +  ( N  x.  m
) ) ) )
8582, 84syl5ibcom 220 . . . . 5  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( ( A  gcd  N )  =  1  ->  E. n  e.  ZZ  E. m  e.  ZZ  1  =  ( ( A  x.  n )  +  ( N  x.  m
) ) ) )
8652ad3antrrr 729 . . . . . . . . . . 11  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  N  e.  ZZ )
87 dvdsmul1 14017 . . . . . . . . . . 11  |-  ( ( N  e.  ZZ  /\  m  e.  ZZ )  ->  N  ||  ( N  x.  m ) )
8886, 87sylancom 667 . . . . . . . . . 10  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  N  ||  ( N  x.  m
) )
89 zmulcl 10933 . . . . . . . . . . . 12  |-  ( ( N  e.  ZZ  /\  m  e.  ZZ )  ->  ( N  x.  m
)  e.  ZZ )
9086, 89sylancom 667 . . . . . . . . . . 11  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  ( N  x.  m )  e.  ZZ )
91 dvdsnegb 14013 . . . . . . . . . . 11  |-  ( ( N  e.  ZZ  /\  ( N  x.  m
)  e.  ZZ )  ->  ( N  ||  ( N  x.  m
)  <->  N  ||  -u ( N  x.  m )
) )
9286, 90, 91syl2anc 661 . . . . . . . . . 10  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  ( N  ||  ( N  x.  m )  <->  N  ||  -u ( N  x.  m )
) )
9388, 92mpbid 210 . . . . . . . . 9  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  N  ||  -u ( N  x.  m
) )
9435adantr 465 . . . . . . . . . . . . . . 15  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  A  e.  ZZ )
9594zcnd 10991 . . . . . . . . . . . . . 14  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  A  e.  CC )
96 zcn 10890 . . . . . . . . . . . . . . 15  |-  ( n  e.  ZZ  ->  n  e.  CC )
9796ad2antlr 726 . . . . . . . . . . . . . 14  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  n  e.  CC )
9895, 97mulcomd 9634 . . . . . . . . . . . . 13  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  ( A  x.  n )  =  ( n  x.  A ) )
9998oveq1d 6311 . . . . . . . . . . . 12  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
( A  x.  n
)  +  ( N  x.  m ) )  =  ( ( n  x.  A )  +  ( N  x.  m
) ) )
10097, 95mulcld 9633 . . . . . . . . . . . . 13  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
n  x.  A )  e.  CC )
10190zcnd 10991 . . . . . . . . . . . . 13  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  ( N  x.  m )  e.  CC )
102100, 101subnegd 9957 . . . . . . . . . . . 12  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
( n  x.  A
)  -  -u ( N  x.  m )
)  =  ( ( n  x.  A )  +  ( N  x.  m ) ) )
10399, 102eqtr4d 2501 . . . . . . . . . . 11  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
( A  x.  n
)  +  ( N  x.  m ) )  =  ( ( n  x.  A )  -  -u ( N  x.  m
) ) )
104103oveq2d 6312 . . . . . . . . . 10  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
( n  x.  A
)  -  ( ( A  x.  n )  +  ( N  x.  m ) ) )  =  ( ( n  x.  A )  -  ( ( n  x.  A )  -  -u ( N  x.  m )
) ) )
105101negcld 9937 . . . . . . . . . . 11  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  -u ( N  x.  m )  e.  CC )
106100, 105nncand 9955 . . . . . . . . . 10  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
( n  x.  A
)  -  ( ( n  x.  A )  -  -u ( N  x.  m ) ) )  =  -u ( N  x.  m ) )
107104, 106eqtrd 2498 . . . . . . . . 9  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
( n  x.  A
)  -  ( ( A  x.  n )  +  ( N  x.  m ) ) )  =  -u ( N  x.  m ) )
10893, 107breqtrrd 4482 . . . . . . . 8  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  N  ||  ( ( n  x.  A )  -  (
( A  x.  n
)  +  ( N  x.  m ) ) ) )
109 oveq2 6304 . . . . . . . . 9  |-  ( 1  =  ( ( A  x.  n )  +  ( N  x.  m
) )  ->  (
( n  x.  A
)  -  1 )  =  ( ( n  x.  A )  -  ( ( A  x.  n )  +  ( N  x.  m ) ) ) )
110109breq2d 4468 . . . . . . . 8  |-  ( 1  =  ( ( A  x.  n )  +  ( N  x.  m
) )  ->  ( N  ||  ( ( n  x.  A )  - 
1 )  <->  N  ||  (
( n  x.  A
)  -  ( ( A  x.  n )  +  ( N  x.  m ) ) ) ) )
111108, 110syl5ibrcom 222 . . . . . . 7  |-  ( ( ( ( N  e. 
NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  /\  m  e.  ZZ )  ->  (
1  =  ( ( A  x.  n )  +  ( N  x.  m ) )  ->  N  ||  ( ( n  x.  A )  - 
1 ) ) )
112111rexlimdva 2949 . . . . . 6  |-  ( ( ( N  e.  NN0  /\  A  e.  ZZ )  /\  n  e.  ZZ )  ->  ( E. m  e.  ZZ  1  =  ( ( A  x.  n
)  +  ( N  x.  m ) )  ->  N  ||  (
( n  x.  A
)  -  1 ) ) )
113112reximdva 2932 . . . . 5  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. n  e.  ZZ  E. m  e.  ZZ  1  =  ( ( A  x.  n
)  +  ( N  x.  m ) )  ->  E. n  e.  ZZ  N  ||  ( ( n  x.  A )  - 
1 ) ) )
11485, 113syld 44 . . . 4  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( ( A  gcd  N )  =  1  ->  E. n  e.  ZZ  N  ||  ( ( n  x.  A )  - 
1 ) ) )
11578, 114impbid 191 . . 3  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. n  e.  ZZ  N  ||  (
( n  x.  A
)  -  1 )  <-> 
( A  gcd  N
)  =  1 ) )
11628, 50, 1153bitrd 279 . 2  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( E. x  e.  ( Base `  Y
) ( x ( .r `  Y ) ( L `  A
) )  =  ( 1r `  Y )  <-> 
( A  gcd  N
)  =  1 ) )
1178, 19, 1163bitrd 279 1  |-  ( ( N  e.  NN0  /\  A  e.  ZZ )  ->  ( ( L `  A )  e.  U  <->  ( A  gcd  N )  =  1 ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 184    /\ wa 369    = wceq 1395    e. wcel 1819   E.wrex 2808   class class class wbr 4456   ran crn 5009    Fn wfn 5589   -->wf 5590   -onto->wfo 5592   ` cfv 5594  (class class class)co 6296   CCcc 9507   1c1 9510    + caddc 9512    x. cmul 9514    - cmin 9824   -ucneg 9825   NN0cn0 10816   ZZcz 10885    || cdvds 13998    gcd cgcd 14156   Basecbs 14644   .rcmulr 14713   1rcur 17280   Ringcrg 17325   CRingccrg 17326   ||rcdsr 17414  Unitcui 17415   RingHom crh 17488  ℤringzring 18615   ZRHomczrh 18664  ℤ/nczn 18667
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1619  ax-4 1632  ax-5 1705  ax-6 1748  ax-7 1791  ax-8 1821  ax-9 1823  ax-10 1838  ax-11 1843  ax-12 1855  ax-13 2000  ax-ext 2435  ax-rep 4568  ax-sep 4578  ax-nul 4586  ax-pow 4634  ax-pr 4695  ax-un 6591  ax-inf2 8075  ax-cnex 9565  ax-resscn 9566  ax-1cn 9567  ax-icn 9568  ax-addcl 9569  ax-addrcl 9570  ax-mulcl 9571  ax-mulrcl 9572  ax-mulcom 9573  ax-addass 9574  ax-mulass 9575  ax-distr 9576  ax-i2m1 9577  ax-1ne0 9578  ax-1rid 9579  ax-rnegex 9580  ax-rrecex 9581  ax-cnre 9582  ax-pre-lttri 9583  ax-pre-lttrn 9584  ax-pre-ltadd 9585  ax-pre-mulgt0 9586  ax-pre-sup 9587  ax-addf 9588  ax-mulf 9589
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 974  df-3an 975  df-tru 1398  df-ex 1614  df-nf 1618  df-sb 1741  df-eu 2287  df-mo 2288  df-clab 2443  df-cleq 2449  df-clel 2452  df-nfc 2607  df-ne 2654  df-nel 2655  df-ral 2812  df-rex 2813  df-reu 2814  df-rmo 2815  df-rab 2816  df-v 3111  df-sbc 3328  df-csb 3431  df-dif 3474  df-un 3476  df-in 3478  df-ss 3485  df-pss 3487  df-nul 3794  df-if 3945  df-pw 4017  df-sn 4033  df-pr 4035  df-tp 4037  df-op 4039  df-uni 4252  df-int 4289  df-iun 4334  df-br 4457  df-opab 4516  df-mpt 4517  df-tr 4551  df-eprel 4800  df-id 4804  df-po 4809  df-so 4810  df-fr 4847  df-we 4849  df-ord 4890  df-on 4891  df-lim 4892  df-suc 4893  df-xp 5014  df-rel 5015  df-cnv 5016  df-co 5017  df-dm 5018  df-rn 5019  df-res 5020  df-ima 5021  df-iota 5557  df-fun 5596  df-fn 5597  df-f 5598  df-f1 5599  df-fo 5600  df-f1o 5601  df-fv 5602  df-riota 6258  df-ov 6299  df-oprab 6300  df-mpt2 6301  df-om 6700  df-1st 6799  df-2nd 6800  df-tpos 6973  df-recs 7060  df-rdg 7094  df-1o 7148  df-oadd 7152  df-er 7329  df-ec 7331  df-qs 7335  df-map 7440  df-en 7536  df-dom 7537  df-sdom 7538  df-fin 7539  df-sup 7919  df-pnf 9647  df-mnf 9648  df-xr 9649  df-ltxr 9650  df-le 9651  df-sub 9826  df-neg 9827  df-div 10228  df-nn 10557  df-2 10615  df-3 10616  df-4 10617  df-5 10618  df-6 10619  df-7 10620  df-8 10621  df-9 10622  df-10 10623  df-n0 10817  df-z 10886  df-dec 11001  df-uz 11107  df-rp 11246  df-fz 11698  df-fl 11932  df-mod 12000  df-seq 12111  df-exp 12170  df-cj 12944  df-re 12945  df-im 12946  df-sqrt 13080  df-abs 13081  df-dvds 13999  df-gcd 14157  df-struct 14646  df-ndx 14647  df-slot 14648  df-base 14649  df-sets 14650  df-ress 14651  df-plusg 14725  df-mulr 14726  df-starv 14727  df-sca 14728  df-vsca 14729  df-ip 14730  df-tset 14731  df-ple 14732  df-ds 14734  df-unif 14735  df-0g 14859  df-imas 14925  df-qus 14926  df-mgm 15999  df-sgrp 16038  df-mnd 16048  df-mhm 16093  df-grp 16184  df-minusg 16185  df-sbg 16186  df-mulg 16187  df-subg 16325  df-nsg 16326  df-eqg 16327  df-ghm 16392  df-cmn 16927  df-abl 16928  df-mgp 17269  df-ur 17281  df-ring 17327  df-cring 17328  df-oppr 17399  df-dvdsr 17417  df-unit 17418  df-rnghom 17491  df-subrg 17554  df-lmod 17641  df-lss 17706  df-lsp 17745  df-sra 17945  df-rgmod 17946  df-lidl 17947  df-rsp 17948  df-2idl 18007  df-cnfld 18548  df-zring 18616  df-zrh 18668  df-zn 18671
This theorem is referenced by:  znunithash  18730  znrrg  18731  dchrelbas4  23644  lgsdchr  23749  rpvmasumlem  23798  dirith  23840
  Copyright terms: Public domain W3C validator