ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  moddvds Unicode version

Theorem moddvds 11699
Description: Two ways to say  A  ==  B (mod  N), see also definition in [ApostolNT] p. 106. (Contributed by Mario Carneiro, 18-Feb-2014.)
Assertion
Ref Expression
moddvds  |-  ( ( N  e.  NN  /\  A  e.  ZZ  /\  B  e.  ZZ )  ->  (
( A  mod  N
)  =  ( B  mod  N )  <->  N  ||  ( A  -  B )
) )

Proof of Theorem moddvds
StepHypRef Expression
1 nnq 9543 . . . . . 6  |-  ( N  e.  NN  ->  N  e.  QQ )
21adantr 274 . . . . 5  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  N  e.  QQ )
3 nngt0 8859 . . . . . 6  |-  ( N  e.  NN  ->  0  <  N )
43adantr 274 . . . . 5  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  0  <  N )
5 q0mod 10258 . . . . 5  |-  ( ( N  e.  QQ  /\  0  <  N )  -> 
( 0  mod  N
)  =  0 )
62, 4, 5syl2anc 409 . . . 4  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( 0  mod  N )  =  0 )
76eqeq2d 2169 . . 3  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  -  B
)  mod  N )  =  ( 0  mod 
N )  <->  ( ( A  -  B )  mod  N )  =  0 ) )
8 zq 9536 . . . . . . . . 9  |-  ( A  e.  ZZ  ->  A  e.  QQ )
98ad2antrl 482 . . . . . . . 8  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  A  e.  QQ )
109adantr 274 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  A  e.  QQ )
11 zq 9536 . . . . . . . . 9  |-  ( B  e.  ZZ  ->  B  e.  QQ )
1211ad2antll 483 . . . . . . . 8  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  B  e.  QQ )
1312adantr 274 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  B  e.  QQ )
14 qnegcl 9546 . . . . . . . 8  |-  ( B  e.  QQ  ->  -u B  e.  QQ )
1513, 14syl 14 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  -u B  e.  QQ )
162adantr 274 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  N  e.  QQ )
174adantr 274 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  0  <  N )
18 simpr 109 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  ( A  mod  N )  =  ( B  mod  N
) )
1910, 13, 15, 16, 17, 18modqadd1 10264 . . . . . 6  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  (
( A  +  -u B )  mod  N
)  =  ( ( B  +  -u B
)  mod  N )
)
2019ex 114 . . . . 5  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  mod  N )  =  ( B  mod  N
)  ->  ( ( A  +  -u B )  mod  N )  =  ( ( B  +  -u B )  mod  N
) ) )
21 simprl 521 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  A  e.  ZZ )
2221zcnd 9288 . . . . . . . 8  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  A  e.  CC )
23 simprr 522 . . . . . . . . 9  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  B  e.  ZZ )
2423zcnd 9288 . . . . . . . 8  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  B  e.  CC )
2522, 24negsubd 8193 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( A  +  -u B )  =  ( A  -  B
) )
2625oveq1d 5840 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  +  -u B )  mod  N )  =  ( ( A  -  B )  mod  N
) )
2724negidd 8177 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( B  +  -u B )  =  0 )
2827oveq1d 5840 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( B  +  -u B )  mod  N )  =  ( 0  mod  N
) )
2926, 28eqeq12d 2172 . . . . 5  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  +  -u B )  mod  N
)  =  ( ( B  +  -u B
)  mod  N )  <->  ( ( A  -  B
)  mod  N )  =  ( 0  mod 
N ) ) )
3020, 29sylibd 148 . . . 4  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  mod  N )  =  ( B  mod  N
)  ->  ( ( A  -  B )  mod  N )  =  ( 0  mod  N ) ) )
319adantr 274 . . . . . . . 8  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  A  e.  QQ )
3212adantr 274 . . . . . . . 8  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  B  e.  QQ )
33 qsubcl 9548 . . . . . . . 8  |-  ( ( A  e.  QQ  /\  B  e.  QQ )  ->  ( A  -  B
)  e.  QQ )
3431, 32, 33syl2anc 409 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  ( A  -  B )  e.  QQ )
35 0z 9179 . . . . . . . 8  |-  0  e.  ZZ
36 zq 9536 . . . . . . . 8  |-  ( 0  e.  ZZ  ->  0  e.  QQ )
3735, 36mp1i 10 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  0  e.  QQ )
382adantr 274 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  N  e.  QQ )
394adantr 274 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  0  <  N )
40 simpr 109 . . . . . . 7  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  (
( A  -  B
)  mod  N )  =  ( 0  mod 
N ) )
4134, 37, 32, 38, 39, 40modqadd1 10264 . . . . . 6  |-  ( ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  /\  ( ( A  -  B )  mod  N )  =  ( 0  mod  N
) )  ->  (
( ( A  -  B )  +  B
)  mod  N )  =  ( ( 0  +  B )  mod 
N ) )
4241ex 114 . . . . 5  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  -  B
)  mod  N )  =  ( 0  mod 
N )  ->  (
( ( A  -  B )  +  B
)  mod  N )  =  ( ( 0  +  B )  mod 
N ) ) )
4322, 24npcand 8191 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  -  B )  +  B )  =  A )
4443oveq1d 5840 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  -  B
)  +  B )  mod  N )  =  ( A  mod  N
) )
4524addid2d 8026 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( 0  +  B )  =  B )
4645oveq1d 5840 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
0  +  B )  mod  N )  =  ( B  mod  N
) )
4744, 46eqeq12d 2172 . . . . 5  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( ( A  -  B )  +  B
)  mod  N )  =  ( ( 0  +  B )  mod 
N )  <->  ( A  mod  N )  =  ( B  mod  N ) ) )
4842, 47sylibd 148 . . . 4  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  -  B
)  mod  N )  =  ( 0  mod 
N )  ->  ( A  mod  N )  =  ( B  mod  N
) ) )
4930, 48impbid 128 . . 3  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  mod  N )  =  ( B  mod  N
)  <->  ( ( A  -  B )  mod 
N )  =  ( 0  mod  N ) ) )
50 zsubcl 9209 . . . 4  |-  ( ( A  e.  ZZ  /\  B  e.  ZZ )  ->  ( A  -  B
)  e.  ZZ )
51 dvdsval3 11691 . . . 4  |-  ( ( N  e.  NN  /\  ( A  -  B
)  e.  ZZ )  ->  ( N  ||  ( A  -  B
)  <->  ( ( A  -  B )  mod 
N )  =  0 ) )
5250, 51sylan2 284 . . 3  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( N  ||  ( A  -  B
)  <->  ( ( A  -  B )  mod 
N )  =  0 ) )
537, 49, 523bitr4d 219 . 2  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  mod  N )  =  ( B  mod  N
)  <->  N  ||  ( A  -  B ) ) )
54533impb 1181 1  |-  ( ( N  e.  NN  /\  A  e.  ZZ  /\  B  e.  ZZ )  ->  (
( A  mod  N
)  =  ( B  mod  N )  <->  N  ||  ( A  -  B )
) )
Colors of variables: wff set class
Syntax hints:    -> wi 4    /\ wa 103    <-> wb 104    /\ w3a 963    = wceq 1335    e. wcel 2128   class class class wbr 3966  (class class class)co 5825   0cc0 7733    + caddc 7736    < clt 7913    - cmin 8047   -ucneg 8048   NNcn 8834   ZZcz 9168   QQcq 9529    mod cmo 10225    || cdvds 11687
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1427  ax-7 1428  ax-gen 1429  ax-ie1 1473  ax-ie2 1474  ax-8 1484  ax-10 1485  ax-11 1486  ax-i12 1487  ax-bndl 1489  ax-4 1490  ax-17 1506  ax-i9 1510  ax-ial 1514  ax-i5r 1515  ax-13 2130  ax-14 2131  ax-ext 2139  ax-sep 4083  ax-pow 4136  ax-pr 4170  ax-un 4394  ax-setind 4497  ax-cnex 7824  ax-resscn 7825  ax-1cn 7826  ax-1re 7827  ax-icn 7828  ax-addcl 7829  ax-addrcl 7830  ax-mulcl 7831  ax-mulrcl 7832  ax-addcom 7833  ax-mulcom 7834  ax-addass 7835  ax-mulass 7836  ax-distr 7837  ax-i2m1 7838  ax-0lt1 7839  ax-1rid 7840  ax-0id 7841  ax-rnegex 7842  ax-precex 7843  ax-cnre 7844  ax-pre-ltirr 7845  ax-pre-ltwlin 7846  ax-pre-lttrn 7847  ax-pre-apti 7848  ax-pre-ltadd 7849  ax-pre-mulgt0 7850  ax-pre-mulext 7851  ax-arch 7852
This theorem depends on definitions:  df-bi 116  df-3or 964  df-3an 965  df-tru 1338  df-fal 1341  df-nf 1441  df-sb 1743  df-eu 2009  df-mo 2010  df-clab 2144  df-cleq 2150  df-clel 2153  df-nfc 2288  df-ne 2328  df-nel 2423  df-ral 2440  df-rex 2441  df-reu 2442  df-rmo 2443  df-rab 2444  df-v 2714  df-sbc 2938  df-csb 3032  df-dif 3104  df-un 3106  df-in 3108  df-ss 3115  df-pw 3545  df-sn 3566  df-pr 3567  df-op 3569  df-uni 3774  df-int 3809  df-iun 3852  df-br 3967  df-opab 4027  df-mpt 4028  df-id 4254  df-po 4257  df-iso 4258  df-xp 4593  df-rel 4594  df-cnv 4595  df-co 4596  df-dm 4597  df-rn 4598  df-res 4599  df-ima 4600  df-iota 5136  df-fun 5173  df-fn 5174  df-f 5175  df-fv 5179  df-riota 5781  df-ov 5828  df-oprab 5829  df-mpo 5830  df-1st 6089  df-2nd 6090  df-pnf 7915  df-mnf 7916  df-xr 7917  df-ltxr 7918  df-le 7919  df-sub 8049  df-neg 8050  df-reap 8451  df-ap 8458  df-div 8547  df-inn 8835  df-n0 9092  df-z 9169  df-q 9530  df-rp 9562  df-fl 10173  df-mod 10226  df-dvds 11688
This theorem is referenced by:  modm1div  11700  summodnegmod  11722  modmulconst  11723  addmodlteqALT  11755  dvdsmod  11758  congr  11981  cncongr1  11984  cncongr2  11985  crth  12103  eulerthlemh  12110  eulerthlemth  12111  prmdiv  12114  prmdiveq  12115  odzcllem  12121  odzdvds  12124  odzphi  12125
  Copyright terms: Public domain W3C validator