ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  moddvds Unicode version
Theorem moddvds 12276
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 9796 . . . . . 6 |- ( N e. NN -> N e. QQ )
21adantr 276 . . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> N e. QQ )
3 nngt0 9103 . . . . . 6 |- ( N e. NN -> 0 < N )
43adantr 276 . . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> 0 < N )
5 q0mod 10544 . . . . 5 |- ( ( N e. QQ /\ 0 < N ) -> ( 0 mod N ) = 0 )
62, 4, 5syl2anc 411 . . . 4 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( 0 mod N ) = 0 )
76eqeq2d 2221 . . 3 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) mod N ) = ( 0 mod N ) <-> ( ( A - B ) mod N ) = 0 ) )
8 zq 9789 . . . . . . . . 9 |- ( A e. ZZ -> A e. QQ )
98ad2antrl 490 . . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. QQ )
109adantr 276 . . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> A e. QQ )
11 zq 9789 . . . . . . . . 9 |- ( B e. ZZ -> B e. QQ )
1211ad2antll 491 . . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. QQ )
1312adantr 276 . . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> B e. QQ )
14 qnegcl 9799 . . . . . . . 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 276 . . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> N e. QQ )
174adantr 276 . . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> 0 < N )
18 simpr 110 . . . . . . 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 10550 . . . . . 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 115 . . . . 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 529 . . . . . . . . 9 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. ZZ )
2221zcnd 9538 . . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. CC )
23 simprr 531 . . . . . . . . 9 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. ZZ )
2423zcnd 9538 . . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. CC )
2522, 24negsubd 8431 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( A + -u B ) = ( A - B ) )
2625oveq1d 5989 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A + -u B ) mod N ) = ( ( A - B ) mod N ) )
2724negidd 8415 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( B + -u B ) = 0 )
2827oveq1d 5989 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( B + -u B ) mod N ) = ( 0 mod N ) )
2926, 28eqeq12d 2224 . . . . 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 149 . . . 4 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A mod N ) = ( B mod N ) -> ( ( A - B ) mod N ) = ( 0 mod N ) ) )
319adantr 276 . . . . . . . 8 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> A e. QQ )
3212adantr 276 . . . . . . . 8 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> B e. QQ )
33 qsubcl 9801 . . . . . . . 8 |- ( ( A e. QQ /\ B e. QQ ) -> ( A - B ) e. QQ )
3431, 32, 33syl2anc 411 . . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> ( A - B ) e. QQ )
35 0z 9425 . . . . . . . 8 |- 0 e. ZZ
36 zq 9789 . . . . . . . 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 276 . . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> N e. QQ )
394adantr 276 . . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> 0 < N )
40 simpr 110 . . . . . . 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 10550 . . . . . 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 115 . . . . 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 8429 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A - B ) + B ) = A )
4443oveq1d 5989 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) + B ) mod N ) = ( A mod N ) )
4524addlidd 8264 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( 0 + B ) = B )
4645oveq1d 5989 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( 0 + B ) mod N ) = ( B mod N ) )
4744, 46eqeq12d 2224 . . . . 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 149 . . . 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 129 . . 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 9455 . . . 4 |- ( ( A e. ZZ /\ B e. ZZ ) -> ( A - B ) e. ZZ )
51 dvdsval3 12268 . . . 4 |- ( ( N e. NN /\ ( A - B ) e. ZZ ) -> ( N || ( A - B ) <-> ( ( A - B ) mod N ) = 0 ) )
5250, 51sylan2 286 . . 3 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( N || ( A - B ) <-> ( ( A - B ) mod N ) = 0 ) )
537, 49, 523bitr4d 220 . 2 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A mod N ) = ( B mod N ) <-> N || ( A - B ) ) )
54533impb 1204 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 104   <-> wb 105   /\ w3a 983   = wceq 1375   e. wcel 2180   class class class wbr 4062  (class class class)co 5974   0cc0 7967   + caddc 7970   < clt 8149   - cmin 8285   -ucneg 8286   NNcn 9078   ZZcz 9414   QQcq 9782   mod cmo 10511   || cdvds 12264
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 617  ax-in2 618  ax-io 713  ax-5 1473  ax-7 1474  ax-gen 1475  ax-ie1 1519  ax-ie2 1520  ax-8 1530  ax-10 1531  ax-11 1532  ax-i12 1533  ax-bndl 1535  ax-4 1536  ax-17 1552  ax-i9 1556  ax-ial 1560  ax-i5r 1561  ax-13 2182  ax-14 2183  ax-ext 2191  ax-sep 4181  ax-pow 4237  ax-pr 4272  ax-un 4501  ax-setind 4606  ax-cnex 8058  ax-resscn 8059  ax-1cn 8060  ax-1re 8061  ax-icn 8062  ax-addcl 8063  ax-addrcl 8064  ax-mulcl 8065  ax-mulrcl 8066  ax-addcom 8067  ax-mulcom 8068  ax-addass 8069  ax-mulass 8070  ax-distr 8071  ax-i2m1 8072  ax-0lt1 8073  ax-1rid 8074  ax-0id 8075  ax-rnegex 8076  ax-precex 8077  ax-cnre 8078  ax-pre-ltirr 8079  ax-pre-ltwlin 8080  ax-pre-lttrn 8081  ax-pre-apti 8082  ax-pre-ltadd 8083  ax-pre-mulgt0 8084  ax-pre-mulext 8085  ax-arch 8086
This theorem depends on definitions:  df-bi 117  df-3or 984  df-3an 985  df-tru 1378  df-fal 1381  df-nf 1487  df-sb 1789  df-eu 2060  df-mo 2061  df-clab 2196  df-cleq 2202  df-clel 2205  df-nfc 2341  df-ne 2381  df-nel 2476  df-ral 2493  df-rex 2494  df-reu 2495  df-rmo 2496  df-rab 2497  df-v 2781  df-sbc 3009  df-csb 3105  df-dif 3179  df-un 3181  df-in 3183  df-ss 3190  df-pw 3631  df-sn 3652  df-pr 3653  df-op 3655  df-uni 3868  df-int 3903  df-iun 3946  df-br 4063  df-opab 4125  df-mpt 4126  df-id 4361  df-po 4364  df-iso 4365  df-xp 4702  df-rel 4703  df-cnv 4704  df-co 4705  df-dm 4706  df-rn 4707  df-res 4708  df-ima 4709  df-iota 5254  df-fun 5296  df-fn 5297  df-f 5298  df-fv 5302  df-riota 5927  df-ov 5977  df-oprab 5978  df-mpo 5979  df-1st 6256  df-2nd 6257  df-pnf 8151  df-mnf 8152  df-xr 8153  df-ltxr 8154  df-le 8155  df-sub 8287  df-neg 8288  df-reap 8690  df-ap 8697  df-div 8788  df-inn 9079  df-n0 9338  df-z 9415  df-q 9783  df-rp 9818  df-fl 10457  df-mod 10512  df-dvds 12265
This theorem is referenced by:  modm1div  12277  summodnegmod  12299  modmulconst  12300  addmodlteqALT  12336  dvdsmod  12339  congr  12588  cncongr1  12591  cncongr2  12592  crth  12712  eulerthlemh  12719  eulerthlemth  12720  prmdiv  12723  prmdiveq  12724  odzcllem  12731  odzdvds  12734  odzphi  12735  pockthlem  12845  4sqlem11  12890  4sqlem12  12891  znf1o  14580  wilthlem1  15619  lgslem1  15644  lgsmod  15670  lgsdirprm  15678  lgseisenlem2  15715  lgseisenlem3  15716  lgseisenlem4  15717  m1lgs  15729
  Copyright terms: Public domain W3C validator