Metamath Proof Explorer

Theorem cncongr1

Description: One direction of the bicondition in cncongr . Theorem 5.4 in ApostolNT p. 109. (Contributed by AV, 13-Jul-2021)

Ref Expression
Assertion cncongr1 
|- ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) -> ( A mod M ) = ( B mod M ) ) )

Proof

Step Hyp Ref Expression
1 zmulcl 
 |-  ( ( A e. ZZ /\ C e. ZZ ) -> ( A x. C ) e. ZZ )
2 1 3adant2 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( A x. C ) e. ZZ )
3 zmulcl 
 |-  ( ( B e. ZZ /\ C e. ZZ ) -> ( B x. C ) e. ZZ )
4 3 3adant1 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( B x. C ) e. ZZ )
5 simpl 
 |-  ( ( N e. NN /\ M = ( N / ( C gcd N ) ) ) -> N e. NN )
6 congr 
 |-  ( ( ( A x. C ) e. ZZ /\ ( B x. C ) e. ZZ /\ N e. NN ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) <-> E. k e. ZZ ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) ) )
7 2 4 5 6 syl2an3an 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) <-> E. k e. ZZ ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) ) )
8 simpl 
 |-  ( ( C e. ZZ /\ N e. NN ) -> C e. ZZ )
9 nnz 
 |-  ( N e. NN -> N e. ZZ )
10 nnne0 
 |-  ( N e. NN -> N =/= 0 )
11 9 10 jca 
 |-  ( N e. NN -> ( N e. ZZ /\ N =/= 0 ) )
12 11 adantl 
 |-  ( ( C e. ZZ /\ N e. NN ) -> ( N e. ZZ /\ N =/= 0 ) )
13 eqidd 
 |-  ( ( C e. ZZ /\ N e. NN ) -> ( C gcd N ) = ( C gcd N ) )
14 8 12 13 3jca 
 |-  ( ( C e. ZZ /\ N e. NN ) -> ( C e. ZZ /\ ( N e. ZZ /\ N =/= 0 ) /\ ( C gcd N ) = ( C gcd N ) ) )
15 14 ex 
 |-  ( C e. ZZ -> ( N e. NN -> ( C e. ZZ /\ ( N e. ZZ /\ N =/= 0 ) /\ ( C gcd N ) = ( C gcd N ) ) ) )
16 15 3ad2ant3 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( N e. NN -> ( C e. ZZ /\ ( N e. ZZ /\ N =/= 0 ) /\ ( C gcd N ) = ( C gcd N ) ) ) )
17 16 com12 
 |-  ( N e. NN -> ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( C e. ZZ /\ ( N e. ZZ /\ N =/= 0 ) /\ ( C gcd N ) = ( C gcd N ) ) ) )
18 17 adantr 
 |-  ( ( N e. NN /\ M = ( N / ( C gcd N ) ) ) -> ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( C e. ZZ /\ ( N e. ZZ /\ N =/= 0 ) /\ ( C gcd N ) = ( C gcd N ) ) ) )
19 18 impcom 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( C e. ZZ /\ ( N e. ZZ /\ N =/= 0 ) /\ ( C gcd N ) = ( C gcd N ) ) )
20 divgcdcoprmex 
 |-  ( ( C e. ZZ /\ ( N e. ZZ /\ N =/= 0 ) /\ ( C gcd N ) = ( C gcd N ) ) -> E. r e. ZZ E. s e. ZZ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) )
21 19 20 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> E. r e. ZZ E. s e. ZZ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) )
22 21 adantr 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> E. r e. ZZ E. s e. ZZ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) )
23 oveq2 
 |-  ( N = ( ( C gcd N ) x. s ) -> ( k x. N ) = ( k x. ( ( C gcd N ) x. s ) ) )
24 23 3ad2ant2 
 |-  ( ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) -> ( k x. N ) = ( k x. ( ( C gcd N ) x. s ) ) )
25 24 adantl 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( k x. N ) = ( k x. ( ( C gcd N ) x. s ) ) )
26 oveq2 
 |-  ( C = ( ( C gcd N ) x. r ) -> ( A x. C ) = ( A x. ( ( C gcd N ) x. r ) ) )
27 oveq2 
 |-  ( C = ( ( C gcd N ) x. r ) -> ( B x. C ) = ( B x. ( ( C gcd N ) x. r ) ) )
28 26 27 oveq12d 
 |-  ( C = ( ( C gcd N ) x. r ) -> ( ( A x. C ) - ( B x. C ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) )
29 28 3ad2ant1 
 |-  ( ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) -> ( ( A x. C ) - ( B x. C ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) )
30 29 adantl 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( A x. C ) - ( B x. C ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) )
31 25 30 eqeq12d 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) <-> ( k x. ( ( C gcd N ) x. s ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) ) )
32 simpr 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> k e. ZZ )
33 32 zcnd 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> k e. CC )
34 33 adantr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> k e. CC )
35 simp3 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> C e. ZZ )
36 35 adantr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> C e. ZZ )
37 9 adantr 
 |-  ( ( N e. NN /\ M = ( N / ( C gcd N ) ) ) -> N e. ZZ )
38 37 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> N e. ZZ )
39 36 38 gcdcld 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( C gcd N ) e. NN0 )
40 39 nn0cnd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( C gcd N ) e. CC )
41 40 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( C gcd N ) e. CC )
42 simpr 
 |-  ( ( r e. ZZ /\ s e. ZZ ) -> s e. ZZ )
43 42 zcnd 
 |-  ( ( r e. ZZ /\ s e. ZZ ) -> s e. CC )
44 43 adantl 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> s e. CC )
45 34 41 44 mul12d 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( k x. ( ( C gcd N ) x. s ) ) = ( ( C gcd N ) x. ( k x. s ) ) )
46 simp1 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> A e. ZZ )
47 46 zcnd 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> A e. CC )
48 47 adantr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> A e. CC )
49 48 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> A e. CC )
50 35 ad2antrr 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> C e. ZZ )
51 5 nnzd 
 |-  ( ( N e. NN /\ M = ( N / ( C gcd N ) ) ) -> N e. ZZ )
52 51 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> N e. ZZ )
53 52 adantr 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> N e. ZZ )
54 50 53 gcdcld 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> ( C gcd N ) e. NN0 )
55 54 nn0cnd 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> ( C gcd N ) e. CC )
56 55 adantr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( C gcd N ) e. CC )
57 simpl 
 |-  ( ( r e. ZZ /\ s e. ZZ ) -> r e. ZZ )
58 57 zcnd 
 |-  ( ( r e. ZZ /\ s e. ZZ ) -> r e. CC )
59 58 adantl 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> r e. CC )
60 49 56 59 mul12d 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( A x. ( ( C gcd N ) x. r ) ) = ( ( C gcd N ) x. ( A x. r ) ) )
61 simp2 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> B e. ZZ )
62 61 zcnd 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> B e. CC )
63 62 adantr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> B e. CC )
64 63 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> B e. CC )
65 36 52 gcdcld 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( C gcd N ) e. NN0 )
66 65 nn0cnd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( C gcd N ) e. CC )
67 66 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( C gcd N ) e. CC )
68 64 67 59 mul12d 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( B x. ( ( C gcd N ) x. r ) ) = ( ( C gcd N ) x. ( B x. r ) ) )
69 60 68 oveq12d 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) = ( ( ( C gcd N ) x. ( A x. r ) ) - ( ( C gcd N ) x. ( B x. r ) ) ) )
70 45 69 eqeq12d 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( k x. ( ( C gcd N ) x. s ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) <-> ( ( C gcd N ) x. ( k x. s ) ) = ( ( ( C gcd N ) x. ( A x. r ) ) - ( ( C gcd N ) x. ( B x. r ) ) ) ) )
71 46 adantr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> A e. ZZ )
72 71 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> A e. ZZ )
73 57 adantl 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> r e. ZZ )
74 72 73 zmulcld 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( A x. r ) e. ZZ )
75 74 zcnd 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( A x. r ) e. CC )
76 61 adantr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> B e. ZZ )
77 76 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> B e. ZZ )
78 77 73 zmulcld 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( B x. r ) e. ZZ )
79 78 zcnd 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( B x. r ) e. CC )
80 67 75 79 subdid 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( C gcd N ) x. ( ( A x. r ) - ( B x. r ) ) ) = ( ( ( C gcd N ) x. ( A x. r ) ) - ( ( C gcd N ) x. ( B x. r ) ) ) )
81 80 eqcomd 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( ( C gcd N ) x. ( A x. r ) ) - ( ( C gcd N ) x. ( B x. r ) ) ) = ( ( C gcd N ) x. ( ( A x. r ) - ( B x. r ) ) ) )
82 81 eqeq2d 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( ( C gcd N ) x. ( k x. s ) ) = ( ( ( C gcd N ) x. ( A x. r ) ) - ( ( C gcd N ) x. ( B x. r ) ) ) <-> ( ( C gcd N ) x. ( k x. s ) ) = ( ( C gcd N ) x. ( ( A x. r ) - ( B x. r ) ) ) ) )
83 32 adantr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> k e. ZZ )
84 42 adantl 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> s e. ZZ )
85 83 84 zmulcld 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( k x. s ) e. ZZ )
86 85 zcnd 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( k x. s ) e. CC )
87 simpl 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> A e. ZZ )
88 87 57 anim12i 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( A e. ZZ /\ r e. ZZ ) )
89 zmulcl 
 |-  ( ( A e. ZZ /\ r e. ZZ ) -> ( A x. r ) e. ZZ )
90 88 89 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( A x. r ) e. ZZ )
91 simpr 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> B e. ZZ )
92 91 57 anim12i 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( B e. ZZ /\ r e. ZZ ) )
93 zmulcl 
 |-  ( ( B e. ZZ /\ r e. ZZ ) -> ( B x. r ) e. ZZ )
94 92 93 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( B x. r ) e. ZZ )
95 90 94 zsubcld 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( A x. r ) - ( B x. r ) ) e. ZZ )
96 95 zcnd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( A x. r ) - ( B x. r ) ) e. CC )
97 96 ex 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( ( r e. ZZ /\ s e. ZZ ) -> ( ( A x. r ) - ( B x. r ) ) e. CC ) )
98 97 3adant3 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( ( r e. ZZ /\ s e. ZZ ) -> ( ( A x. r ) - ( B x. r ) ) e. CC ) )
99 98 ad2antrr 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> ( ( r e. ZZ /\ s e. ZZ ) -> ( ( A x. r ) - ( B x. r ) ) e. CC ) )
100 99 imp 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( A x. r ) - ( B x. r ) ) e. CC )
101 10 adantr 
 |-  ( ( N e. NN /\ M = ( N / ( C gcd N ) ) ) -> N =/= 0 )
102 101 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> N =/= 0 )
103 gcd2n0cl 
 |-  ( ( C e. ZZ /\ N e. ZZ /\ N =/= 0 ) -> ( C gcd N ) e. NN )
104 36 52 102 103 syl3anc 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( C gcd N ) e. NN )
105 nnne0 
 |-  ( ( C gcd N ) e. NN -> ( C gcd N ) =/= 0 )
106 104 105 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( C gcd N ) =/= 0 )
107 106 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( C gcd N ) =/= 0 )
108 86 100 67 107 mulcand 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( ( C gcd N ) x. ( k x. s ) ) = ( ( C gcd N ) x. ( ( A x. r ) - ( B x. r ) ) ) <-> ( k x. s ) = ( ( A x. r ) - ( B x. r ) ) ) )
109 70 82 108 3bitrd 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( k x. ( ( C gcd N ) x. s ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) <-> ( k x. s ) = ( ( A x. r ) - ( B x. r ) ) ) )
110 109 adantr 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( k x. ( ( C gcd N ) x. s ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) <-> ( k x. s ) = ( ( A x. r ) - ( B x. r ) ) ) )
111 zcn 
 |-  ( A e. ZZ -> A e. CC )
112 zcn 
 |-  ( B e. ZZ -> B e. CC )
113 111 112 anim12i 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( A e. CC /\ B e. CC ) )
114 113 3adant3 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( A e. CC /\ B e. CC ) )
115 114 ad2antrr 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> ( A e. CC /\ B e. CC ) )
116 115 58 anim12i 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( A e. CC /\ B e. CC ) /\ r e. CC ) )
117 df-3an 
 |-  ( ( A e. CC /\ B e. CC /\ r e. CC ) <-> ( ( A e. CC /\ B e. CC ) /\ r e. CC ) )
118 116 117 sylibr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( A e. CC /\ B e. CC /\ r e. CC ) )
119 subdir 
 |-  ( ( A e. CC /\ B e. CC /\ r e. CC ) -> ( ( A - B ) x. r ) = ( ( A x. r ) - ( B x. r ) ) )
120 118 119 syl 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( A - B ) x. r ) = ( ( A x. r ) - ( B x. r ) ) )
121 120 eqcomd 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( A x. r ) - ( B x. r ) ) = ( ( A - B ) x. r ) )
122 121 adantr 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( A x. r ) - ( B x. r ) ) = ( ( A - B ) x. r ) )
123 122 eqeq2d 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( k x. s ) = ( ( A x. r ) - ( B x. r ) ) <-> ( k x. s ) = ( ( A - B ) x. r ) ) )
124 5 nncnd 
 |-  ( ( N e. NN /\ M = ( N / ( C gcd N ) ) ) -> N e. CC )
125 124 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> N e. CC )
126 125 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> N e. CC )
127 84 zcnd 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> s e. CC )
128 66 106 jca 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( C gcd N ) e. CC /\ ( C gcd N ) =/= 0 ) )
129 128 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( C gcd N ) e. CC /\ ( C gcd N ) =/= 0 ) )
130 divmul2 
 |-  ( ( N e. CC /\ s e. CC /\ ( ( C gcd N ) e. CC /\ ( C gcd N ) =/= 0 ) ) -> ( ( N / ( C gcd N ) ) = s <-> N = ( ( C gcd N ) x. s ) ) )
131 126 127 129 130 syl3anc 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( N / ( C gcd N ) ) = s <-> N = ( ( C gcd N ) x. s ) ) )
132 simpll 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) )
133 73 adantr 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> r e. ZZ )
134 5 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> N e. NN )
135 134 36 jca 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( N e. NN /\ C e. ZZ ) )
136 divgcdnnr 
 |-  ( ( N e. NN /\ C e. ZZ ) -> ( N / ( C gcd N ) ) e. NN )
137 135 136 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( N / ( C gcd N ) ) e. NN )
138 137 adantr 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> ( N / ( C gcd N ) ) e. NN )
139 138 ad2antrr 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( N / ( C gcd N ) ) e. NN )
140 eleq1 
 |-  ( s = ( N / ( C gcd N ) ) -> ( s e. NN <-> ( N / ( C gcd N ) ) e. NN ) )
141 140 eqcoms 
 |-  ( ( N / ( C gcd N ) ) = s -> ( s e. NN <-> ( N / ( C gcd N ) ) e. NN ) )
142 141 adantl 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( s e. NN <-> ( N / ( C gcd N ) ) e. NN ) )
143 139 142 mpbird 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> s e. NN )
144 133 143 jca 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( r e. ZZ /\ s e. NN ) )
145 132 144 jca 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) )
146 simpr 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( N / ( C gcd N ) ) = s )
147 145 146 jca 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) /\ ( N / ( C gcd N ) ) = s ) )
148 nnz 
 |-  ( s e. NN -> s e. ZZ )
149 148 adantl 
 |-  ( ( r e. ZZ /\ s e. NN ) -> s e. ZZ )
150 149 anim2i 
 |-  ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> ( k e. ZZ /\ s e. ZZ ) )
151 150 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( k e. ZZ /\ s e. ZZ ) )
152 dvdsmul2 
 |-  ( ( k e. ZZ /\ s e. ZZ ) -> s || ( k x. s ) )
153 151 152 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> s || ( k x. s ) )
154 breq2 
 |-  ( ( k x. s ) = ( ( A - B ) x. r ) -> ( s || ( k x. s ) <-> s || ( ( A - B ) x. r ) ) )
155 zsubcl 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( A - B ) e. ZZ )
156 155 zcnd 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( A - B ) e. CC )
157 156 adantr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( A - B ) e. CC )
158 zcn 
 |-  ( r e. ZZ -> r e. CC )
159 158 adantr 
 |-  ( ( r e. ZZ /\ s e. NN ) -> r e. CC )
160 159 adantl 
 |-  ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> r e. CC )
161 160 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> r e. CC )
162 157 161 mulcomd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( A - B ) x. r ) = ( r x. ( A - B ) ) )
163 162 breq2d 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( s || ( ( A - B ) x. r ) <-> s || ( r x. ( A - B ) ) ) )
164 148 anim2i 
 |-  ( ( r e. ZZ /\ s e. NN ) -> ( r e. ZZ /\ s e. ZZ ) )
165 gcdcom 
 |-  ( ( r e. ZZ /\ s e. ZZ ) -> ( r gcd s ) = ( s gcd r ) )
166 164 165 syl 
 |-  ( ( r e. ZZ /\ s e. NN ) -> ( r gcd s ) = ( s gcd r ) )
167 166 eqeq1d 
 |-  ( ( r e. ZZ /\ s e. NN ) -> ( ( r gcd s ) = 1 <-> ( s gcd r ) = 1 ) )
168 167 adantl 
 |-  ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> ( ( r gcd s ) = 1 <-> ( s gcd r ) = 1 ) )
169 168 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( r gcd s ) = 1 <-> ( s gcd r ) = 1 ) )
170 164 adantl 
 |-  ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> ( r e. ZZ /\ s e. ZZ ) )
171 170 ancomd 
 |-  ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> ( s e. ZZ /\ r e. ZZ ) )
172 155 171 anim12i 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( A - B ) e. ZZ /\ ( s e. ZZ /\ r e. ZZ ) ) )
173 172 ancomd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( s e. ZZ /\ r e. ZZ ) /\ ( A - B ) e. ZZ ) )
174 df-3an 
 |-  ( ( s e. ZZ /\ r e. ZZ /\ ( A - B ) e. ZZ ) <-> ( ( s e. ZZ /\ r e. ZZ ) /\ ( A - B ) e. ZZ ) )
175 173 174 sylibr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( s e. ZZ /\ r e. ZZ /\ ( A - B ) e. ZZ ) )
176 coprmdvds 
 |-  ( ( s e. ZZ /\ r e. ZZ /\ ( A - B ) e. ZZ ) -> ( ( s || ( r x. ( A - B ) ) /\ ( s gcd r ) = 1 ) -> s || ( A - B ) ) )
177 175 176 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( s || ( r x. ( A - B ) ) /\ ( s gcd r ) = 1 ) -> s || ( A - B ) ) )
178 simpr 
 |-  ( ( r e. ZZ /\ s e. NN ) -> s e. NN )
179 178 adantl 
 |-  ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> s e. NN )
180 179 anim2i 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( A e. ZZ /\ B e. ZZ ) /\ s e. NN ) )
181 180 ancomd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( s e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) )
182 3anass 
 |-  ( ( s e. NN /\ A e. ZZ /\ B e. ZZ ) <-> ( s e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) )
183 181 182 sylibr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( s e. NN /\ A e. ZZ /\ B e. ZZ ) )
184 moddvds 
 |-  ( ( s e. NN /\ A e. ZZ /\ B e. ZZ ) -> ( ( A mod s ) = ( B mod s ) <-> s || ( A - B ) ) )
185 183 184 syl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( A mod s ) = ( B mod s ) <-> s || ( A - B ) ) )
186 177 185 sylibrd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( s || ( r x. ( A - B ) ) /\ ( s gcd r ) = 1 ) -> ( A mod s ) = ( B mod s ) ) )
187 186 expcomd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( s gcd r ) = 1 -> ( s || ( r x. ( A - B ) ) -> ( A mod s ) = ( B mod s ) ) ) )
188 169 187 sylbid 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( r gcd s ) = 1 -> ( s || ( r x. ( A - B ) ) -> ( A mod s ) = ( B mod s ) ) ) )
189 188 com23 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( s || ( r x. ( A - B ) ) -> ( ( r gcd s ) = 1 -> ( A mod s ) = ( B mod s ) ) ) )
190 163 189 sylbid 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( s || ( ( A - B ) x. r ) -> ( ( r gcd s ) = 1 -> ( A mod s ) = ( B mod s ) ) ) )
191 190 com3l 
 |-  ( s || ( ( A - B ) x. r ) -> ( ( r gcd s ) = 1 -> ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( A mod s ) = ( B mod s ) ) ) )
192 154 191 syl6bi 
 |-  ( ( k x. s ) = ( ( A - B ) x. r ) -> ( s || ( k x. s ) -> ( ( r gcd s ) = 1 -> ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( A mod s ) = ( B mod s ) ) ) ) )
193 192 com14 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( s || ( k x. s ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) ) ) )
194 153 193 mpd 
 |-  ( ( ( A e. ZZ /\ B e. ZZ ) /\ ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) ) )
195 194 ex 
 |-  ( ( A e. ZZ /\ B e. ZZ ) -> ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) ) ) )
196 195 3adant3 
 |-  ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) -> ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) ) ) )
197 196 adantr 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( k e. ZZ /\ ( r e. ZZ /\ s e. NN ) ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) ) ) )
198 197 impl 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) ) )
199 198 adantr 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) ) )
200 199 imp 
 |-  ( ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) /\ ( N / ( C gcd N ) ) = s ) /\ ( r gcd s ) = 1 ) -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod s ) = ( B mod s ) ) )
201 eqtr2 
 |-  ( ( ( N / ( C gcd N ) ) = M /\ ( N / ( C gcd N ) ) = s ) -> M = s )
202 oveq2 
 |-  ( M = s -> ( A mod M ) = ( A mod s ) )
203 oveq2 
 |-  ( M = s -> ( B mod M ) = ( B mod s ) )
204 202 203 eqeq12d 
 |-  ( M = s -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) )
205 201 204 syl 
 |-  ( ( ( N / ( C gcd N ) ) = M /\ ( N / ( C gcd N ) ) = s ) -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) )
206 205 ex 
 |-  ( ( N / ( C gcd N ) ) = M -> ( ( N / ( C gcd N ) ) = s -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) ) )
207 206 eqcoms 
 |-  ( M = ( N / ( C gcd N ) ) -> ( ( N / ( C gcd N ) ) = s -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) ) )
208 207 adantl 
 |-  ( ( N e. NN /\ M = ( N / ( C gcd N ) ) ) -> ( ( N / ( C gcd N ) ) = s -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) ) )
209 208 adantl 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( N / ( C gcd N ) ) = s -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) ) )
210 209 ad2antrr 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) -> ( ( N / ( C gcd N ) ) = s -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) ) )
211 210 imp 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) )
212 211 adantr 
 |-  ( ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) /\ ( N / ( C gcd N ) ) = s ) /\ ( r gcd s ) = 1 ) -> ( ( A mod M ) = ( B mod M ) <-> ( A mod s ) = ( B mod s ) ) )
213 200 212 sylibrd 
 |-  ( ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) /\ ( N / ( C gcd N ) ) = s ) /\ ( r gcd s ) = 1 ) -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) )
214 213 ex 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. NN ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) ) )
215 147 214 syl 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( N / ( C gcd N ) ) = s ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) ) )
216 215 ex 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( N / ( C gcd N ) ) = s -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) ) ) )
217 131 216 sylbird 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( N = ( ( C gcd N ) x. s ) -> ( ( r gcd s ) = 1 -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) ) ) )
218 217 com3l 
 |-  ( N = ( ( C gcd N ) x. s ) -> ( ( r gcd s ) = 1 -> ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) ) ) )
219 218 a1i 
 |-  ( C = ( ( C gcd N ) x. r ) -> ( N = ( ( C gcd N ) x. s ) -> ( ( r gcd s ) = 1 -> ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) ) ) ) )
220 219 3imp 
 |-  ( ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) -> ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) ) )
221 220 impcom 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( k x. s ) = ( ( A - B ) x. r ) -> ( A mod M ) = ( B mod M ) ) )
222 123 221 sylbid 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( k x. s ) = ( ( A x. r ) - ( B x. r ) ) -> ( A mod M ) = ( B mod M ) ) )
223 110 222 sylbid 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( k x. ( ( C gcd N ) x. s ) ) = ( ( A x. ( ( C gcd N ) x. r ) ) - ( B x. ( ( C gcd N ) x. r ) ) ) -> ( A mod M ) = ( B mod M ) ) )
224 31 223 sylbid 
 |-  ( ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) /\ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) ) -> ( ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) -> ( A mod M ) = ( B mod M ) ) )
225 224 ex 
 |-  ( ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) /\ ( r e. ZZ /\ s e. ZZ ) ) -> ( ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) -> ( ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) -> ( A mod M ) = ( B mod M ) ) ) )
226 225 rexlimdvva 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> ( E. r e. ZZ E. s e. ZZ ( C = ( ( C gcd N ) x. r ) /\ N = ( ( C gcd N ) x. s ) /\ ( r gcd s ) = 1 ) -> ( ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) -> ( A mod M ) = ( B mod M ) ) ) )
227 22 226 mpd 
 |-  ( ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) /\ k e. ZZ ) -> ( ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) -> ( A mod M ) = ( B mod M ) ) )
228 227 rexlimdva 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( E. k e. ZZ ( k x. N ) = ( ( A x. C ) - ( B x. C ) ) -> ( A mod M ) = ( B mod M ) ) )
229 7 228 sylbid 
 |-  ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) -> ( A mod M ) = ( B mod M ) ) )