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

Theorem moddvds 13867
Description: Two ways to say  A  ==  B (  mod  N
). (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 nnrp 11235 . . . . . 6  |-  ( N  e.  NN  ->  N  e.  RR+ )
21adantr 465 . . . . 5  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  N  e.  RR+ )
3 0mod 12003 . . . . 5  |-  ( N  e.  RR+  ->  ( 0  mod  N )  =  0 )
42, 3syl 16 . . . 4  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( 0  mod  N )  =  0 )
54eqeq2d 2455 . . 3  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  -  B
)  mod  N )  =  ( 0  mod 
N )  <->  ( ( A  -  B )  mod  N )  =  0 ) )
6 zre 10871 . . . . . . 7  |-  ( A  e.  ZZ  ->  A  e.  RR )
76ad2antrl 727 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  A  e.  RR )
8 zre 10871 . . . . . . 7  |-  ( B  e.  ZZ  ->  B  e.  RR )
98ad2antll 728 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  B  e.  RR )
109renegcld 9989 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  -u B  e.  RR )
11 modadd1 12009 . . . . . . 7  |-  ( ( ( A  e.  RR  /\  B  e.  RR )  /\  ( -u B  e.  RR  /\  N  e.  RR+ )  /\  ( A  mod  N )  =  ( B  mod  N
) )  ->  (
( A  +  -u B )  mod  N
)  =  ( ( B  +  -u B
)  mod  N )
)
12113expia 1197 . . . . . 6  |-  ( ( ( A  e.  RR  /\  B  e.  RR )  /\  ( -u B  e.  RR  /\  N  e.  RR+ ) )  ->  (
( A  mod  N
)  =  ( B  mod  N )  -> 
( ( A  +  -u B )  mod  N
)  =  ( ( B  +  -u B
)  mod  N )
) )
137, 9, 10, 2, 12syl22anc 1228 . . . . 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
) ) )
147recnd 9622 . . . . . . . 8  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  A  e.  CC )
159recnd 9622 . . . . . . . 8  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  B  e.  CC )
1614, 15negsubd 9939 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( A  +  -u B )  =  ( A  -  B
) )
1716oveq1d 6293 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  +  -u B )  mod  N )  =  ( ( A  -  B )  mod  N
) )
1815negidd 9923 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( B  +  -u B )  =  0 )
1918oveq1d 6293 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( B  +  -u B )  mod  N )  =  ( 0  mod  N
) )
2017, 19eqeq12d 2463 . . . . 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 ) ) )
2113, 20sylibd 214 . . . 4  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  mod  N )  =  ( B  mod  N
)  ->  ( ( A  -  B )  mod  N )  =  ( 0  mod  N ) ) )
227, 9resubcld 9990 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( A  -  B )  e.  RR )
23 0red 9597 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  0  e.  RR )
24 modadd1 12009 . . . . . . 7  |-  ( ( ( ( A  -  B )  e.  RR  /\  0  e.  RR )  /\  ( B  e.  RR  /\  N  e.  RR+ )  /\  (
( A  -  B
)  mod  N )  =  ( 0  mod 
N ) )  -> 
( ( ( A  -  B )  +  B )  mod  N
)  =  ( ( 0  +  B )  mod  N ) )
25243expia 1197 . . . . . 6  |-  ( ( ( ( A  -  B )  e.  RR  /\  0  e.  RR )  /\  ( B  e.  RR  /\  N  e.  RR+ ) )  ->  (
( ( A  -  B )  mod  N
)  =  ( 0  mod  N )  -> 
( ( ( A  -  B )  +  B )  mod  N
)  =  ( ( 0  +  B )  mod  N ) ) )
2622, 23, 9, 2, 25syl22anc 1228 . . . . 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 ) ) )
2714, 15npcand 9937 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  -  B )  +  B )  =  A )
2827oveq1d 6293 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  -  B
)  +  B )  mod  N )  =  ( A  mod  N
) )
2915addid2d 9781 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( 0  +  B )  =  B )
3029oveq1d 6293 . . . . . 6  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
0  +  B )  mod  N )  =  ( B  mod  N
) )
3128, 30eqeq12d 2463 . . . . 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 ) ) )
3226, 31sylibd 214 . . . 4  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( (
( A  -  B
)  mod  N )  =  ( 0  mod 
N )  ->  ( A  mod  N )  =  ( B  mod  N
) ) )
3321, 32impbid 191 . . 3  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  mod  N )  =  ( B  mod  N
)  <->  ( ( A  -  B )  mod 
N )  =  ( 0  mod  N ) ) )
34 zsubcl 10909 . . . 4  |-  ( ( A  e.  ZZ  /\  B  e.  ZZ )  ->  ( A  -  B
)  e.  ZZ )
35 dvdsval3 13864 . . . 4  |-  ( ( N  e.  NN  /\  ( A  -  B
)  e.  ZZ )  ->  ( N  ||  ( A  -  B
)  <->  ( ( A  -  B )  mod 
N )  =  0 ) )
3634, 35sylan2 474 . . 3  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( N  ||  ( A  -  B
)  <->  ( ( A  -  B )  mod 
N )  =  0 ) )
375, 33, 363bitr4d 285 . 2  |-  ( ( N  e.  NN  /\  ( A  e.  ZZ  /\  B  e.  ZZ ) )  ->  ( ( A  mod  N )  =  ( B  mod  N
)  <->  N  ||  ( A  -  B ) ) )
38373impb 1191 1  |-  ( ( N  e.  NN  /\  A  e.  ZZ  /\  B  e.  ZZ )  ->  (
( A  mod  N
)  =  ( B  mod  N )  <->  N  ||  ( A  -  B )
) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 184    /\ wa 369    /\ w3a 972    = wceq 1381    e. wcel 1802   class class class wbr 4434  (class class class)co 6278   RRcr 9491   0cc0 9492    + caddc 9495    - cmin 9807   -ucneg 9808   NNcn 10539   ZZcz 10867   RR+crp 11226    mod cmo 11972    || cdvds 13860
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1603  ax-4 1616  ax-5 1689  ax-6 1732  ax-7 1774  ax-8 1804  ax-9 1806  ax-10 1821  ax-11 1826  ax-12 1838  ax-13 1983  ax-ext 2419  ax-sep 4555  ax-nul 4563  ax-pow 4612  ax-pr 4673  ax-un 6574  ax-cnex 9548  ax-resscn 9549  ax-1cn 9550  ax-icn 9551  ax-addcl 9552  ax-addrcl 9553  ax-mulcl 9554  ax-mulrcl 9555  ax-mulcom 9556  ax-addass 9557  ax-mulass 9558  ax-distr 9559  ax-i2m1 9560  ax-1ne0 9561  ax-1rid 9562  ax-rnegex 9563  ax-rrecex 9564  ax-cnre 9565  ax-pre-lttri 9566  ax-pre-lttrn 9567  ax-pre-ltadd 9568  ax-pre-mulgt0 9569  ax-pre-sup 9570
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 973  df-3an 974  df-tru 1384  df-ex 1598  df-nf 1602  df-sb 1725  df-eu 2270  df-mo 2271  df-clab 2427  df-cleq 2433  df-clel 2436  df-nfc 2591  df-ne 2638  df-nel 2639  df-ral 2796  df-rex 2797  df-reu 2798  df-rmo 2799  df-rab 2800  df-v 3095  df-sbc 3312  df-csb 3419  df-dif 3462  df-un 3464  df-in 3466  df-ss 3473  df-pss 3475  df-nul 3769  df-if 3924  df-pw 3996  df-sn 4012  df-pr 4014  df-tp 4016  df-op 4018  df-uni 4232  df-iun 4314  df-br 4435  df-opab 4493  df-mpt 4494  df-tr 4528  df-eprel 4778  df-id 4782  df-po 4787  df-so 4788  df-fr 4825  df-we 4827  df-ord 4868  df-on 4869  df-lim 4870  df-suc 4871  df-xp 4992  df-rel 4993  df-cnv 4994  df-co 4995  df-dm 4996  df-rn 4997  df-res 4998  df-ima 4999  df-iota 5538  df-fun 5577  df-fn 5578  df-f 5579  df-f1 5580  df-fo 5581  df-f1o 5582  df-fv 5583  df-riota 6239  df-ov 6281  df-oprab 6282  df-mpt2 6283  df-om 6683  df-recs 7041  df-rdg 7075  df-er 7310  df-en 7516  df-dom 7517  df-sdom 7518  df-sup 7900  df-pnf 9630  df-mnf 9631  df-xr 9632  df-ltxr 9633  df-le 9634  df-sub 9809  df-neg 9810  df-div 10210  df-nn 10540  df-n0 10799  df-z 10868  df-uz 11088  df-rp 11227  df-fl 11905  df-mod 11973  df-dvds 13861
This theorem is referenced by:  dvdsmod  13917  sadadd3  13985  sadaddlem  13990  crt  14182  eulerthlem2  14186  prmdiv  14189  prmdiveq  14190  odzcllem  14193  odzdvds  14196  odzphi  14197  modprm1div  14198  pockthlem  14297  4sqlem11  14347  4sqlem12  14348  mndodcong  16437  dfod2  16457  sylow3lem6  16523  znf1o  18460  wilthlem1  23211  wilthlem2  23212  wilthlem3  23213  ppiub  23348  lgslem1  23440  lgsmod  23465  lgsdirprm  23473  lgsqrlem1  23485  lgsqrlem2  23486  lgsqr  23490  lgsdchrval  23491  lgseisenlem2  23494  lgseisenlem3  23495  lgseisenlem4  23496  m1lgs  23506  dvdsabsmod0  30900
  Copyright terms: Public domain W3C validator