ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  moddvds Unicode version
Theorem moddvds 12481
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 9964 . . . . . 6 |- ( N e. NN -> N e. QQ )
21adantr 276 . . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> N e. QQ )
3 nngt0 9261 . . . . . 6 |- ( N e. NN -> 0 < N )
43adantr 276 . . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> 0 < N )
5 q0mod 10716 . . . . 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 2244 . . 3 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) mod N ) = ( 0 mod N ) <-> ( ( A - B ) mod N ) = 0 ) )
8 zq 9957 . . . . . . . . 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 9957 . . . . . . . . 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 9967 . . . . . . . 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 10722 . . . . . 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 531 . . . . . . . . 9 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. ZZ )
2221zcnd 9700 . . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. CC )
23 simprr 533 . . . . . . . . 9 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. ZZ )
2423zcnd 9700 . . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. CC )
2522, 24negsubd 8589 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( A + -u B ) = ( A - B ) )
2625oveq1d 6064 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A + -u B ) mod N ) = ( ( A - B ) mod N ) )
2724negidd 8573 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( B + -u B ) = 0 )
2827oveq1d 6064 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( B + -u B ) mod N ) = ( 0 mod N ) )
2926, 28eqeq12d 2247 . . . . 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 9969 . . . . . . . 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 9587 . . . . . . . 8 |- 0 e. ZZ
36 zq 9957 . . . . . . . 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 10722 . . . . . 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 8587 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A - B ) + B ) = A )
4443oveq1d 6064 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) + B ) mod N ) = ( A mod N ) )
4524addlidd 8422 . . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( 0 + B ) = B )
4645oveq1d 6064 . . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( 0 + B ) mod N ) = ( B mod N ) )
4744, 46eqeq12d 2247 . . . . 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 9617 . . . 4 |- ( ( A e. ZZ /\ B e. ZZ ) -> ( A - B ) e. ZZ )
51 dvdsval3 12473 . . . 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 1226 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 1005   = wceq 1398   e. wcel 2203   class class class wbr 4108  (class class class)co 6049   0cc0 8126   + caddc 8129   < clt 8307   - cmin 8443   -ucneg 8444   NNcn 9236   ZZcz 9576   QQcq 9950   mod cmo 10683   || cdvds 12469
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 619  ax-in2 620  ax-io 717  ax-5 1496  ax-7 1497  ax-gen 1498  ax-ie1 1542  ax-ie2 1543  ax-8 1553  ax-10 1554  ax-11 1555  ax-i12 1556  ax-bndl 1558  ax-4 1559  ax-17 1575  ax-i9 1579  ax-ial 1583  ax-i5r 1584  ax-13 2205  ax-14 2206  ax-ext 2214  ax-sep 4227  ax-pow 4286  ax-pr 4321  ax-un 4553  ax-setind 4658  ax-cnex 8217  ax-resscn 8218  ax-1cn 8219  ax-1re 8220  ax-icn 8221  ax-addcl 8222  ax-addrcl 8223  ax-mulcl 8224  ax-mulrcl 8225  ax-addcom 8226  ax-mulcom 8227  ax-addass 8228  ax-mulass 8229  ax-distr 8230  ax-i2m1 8231  ax-0lt1 8232  ax-1rid 8233  ax-0id 8234  ax-rnegex 8235  ax-precex 8236  ax-cnre 8237  ax-pre-ltirr 8238  ax-pre-ltwlin 8239  ax-pre-lttrn 8240  ax-pre-apti 8241  ax-pre-ltadd 8242  ax-pre-mulgt0 8243  ax-pre-mulext 8244  ax-arch 8245
This theorem depends on definitions:  df-bi 117  df-3or 1006  df-3an 1007  df-tru 1401  df-fal 1404  df-nf 1510  df-sb 1812  df-eu 2083  df-mo 2084  df-clab 2219  df-cleq 2225  df-clel 2228  df-nfc 2373  df-ne 2413  df-nel 2508  df-ral 2525  df-rex 2526  df-reu 2527  df-rmo 2528  df-rab 2529  df-v 2814  df-sbc 3042  df-csb 3138  df-dif 3212  df-un 3214  df-in 3216  df-ss 3223  df-pw 3670  df-sn 3694  df-pr 3695  df-op 3697  df-uni 3914  df-int 3949  df-iun 3992  df-br 4109  df-opab 4171  df-mpt 4172  df-id 4413  df-po 4416  df-iso 4417  df-xp 4754  df-rel 4755  df-cnv 4756  df-co 4757  df-dm 4758  df-rn 4759  df-res 4760  df-ima 4761  df-iota 5311  df-fun 5353  df-fn 5354  df-f 5355  df-fv 5359  df-riota 6002  df-ov 6052  df-oprab 6053  df-mpo 6054  df-1st 6333  df-2nd 6334  df-pnf 8309  df-mnf 8310  df-xr 8311  df-ltxr 8312  df-le 8313  df-sub 8445  df-neg 8446  df-reap 8848  df-ap 8855  df-div 8946  df-inn 9237  df-n0 9496  df-z 9577  df-q 9951  df-rp 9986  df-fl 10629  df-mod 10684  df-dvds 12470
This theorem is referenced by:  modm1div  12482  summodnegmod  12504  modmulconst  12505  addmodlteqALT  12541  dvdsmod  12544  congr  12793  cncongr1  12796  cncongr2  12797  crth  12917  eulerthlemh  12924  eulerthlemth  12925  prmdiv  12928  prmdiveq  12929  odzcllem  12936  odzdvds  12939  odzphi  12940  pockthlem  13050  4sqlem11  13095  4sqlem12  13096  znf1o  14791  wilthlem1  15840  lgslem1  15865  lgsmod  15891  lgsdirprm  15899  lgseisenlem2  15936  lgseisenlem3  15937  lgseisenlem4  15938  m1lgs  15950
  Copyright terms: Public domain W3C validator