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

Theorem modaddmodup 11783
Description: The sum of an integer modulo a positive integer and another integer minus the positive integer equals the sum of the two integers modulo the positive integer if the other integer is in the upper part of the range between 0 and the positive integer. (Contributed by AV, 30-Oct-2018.)
Assertion
Ref Expression
modaddmodup  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  ->  (
( B  +  ( A  mod  M ) )  -  M )  =  ( ( B  +  A )  mod 
M ) ) )

Proof of Theorem modaddmodup
StepHypRef Expression
1 elfzoelz 11574 . . . . . . . 8  |-  ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  ->  B  e.  ZZ )
21zred 10768 . . . . . . 7  |-  ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  ->  B  e.  RR )
32adantr 465 . . . . . 6  |-  ( ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  B  e.  RR )
4 zmodcl 11748 . . . . . . . 8  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( A  mod  M
)  e.  NN0 )
54nn0red 10658 . . . . . . 7  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( A  mod  M
)  e.  RR )
65adantl 466 . . . . . 6  |-  ( ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  -> 
( A  mod  M
)  e.  RR )
73, 6readdcld 9434 . . . . 5  |-  ( ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  -> 
( B  +  ( A  mod  M ) )  e.  RR )
87ancoms 453 . . . 4  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  -> 
( B  +  ( A  mod  M ) )  e.  RR )
9 nnrp 11021 . . . . 5  |-  ( M  e.  NN  ->  M  e.  RR+ )
109ad2antlr 726 . . . 4  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  ->  M  e.  RR+ )
11 elfzo2 11577 . . . . . 6  |-  ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  <-> 
( B  e.  (
ZZ>= `  ( M  -  ( A  mod  M ) ) )  /\  M  e.  ZZ  /\  B  < 
M ) )
12 eluz2 10888 . . . . . . . 8  |-  ( B  e.  ( ZZ>= `  ( M  -  ( A  mod  M ) ) )  <-> 
( ( M  -  ( A  mod  M ) )  e.  ZZ  /\  B  e.  ZZ  /\  ( M  -  ( A  mod  M ) )  <_  B ) )
13 nnre 10350 . . . . . . . . . . . . . 14  |-  ( M  e.  NN  ->  M  e.  RR )
1413adantl 466 . . . . . . . . . . . . 13  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  M  e.  RR )
1514adantl 466 . . . . . . . . . . . 12  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  M  e.  RR )
165adantl 466 . . . . . . . . . . . 12  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  ( A  mod  M )  e.  RR )
17 zre 10671 . . . . . . . . . . . . 13  |-  ( B  e.  ZZ  ->  B  e.  RR )
1817adantr 465 . . . . . . . . . . . 12  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  B  e.  RR )
1915, 16, 18lesubaddd 9957 . . . . . . . . . . 11  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  ( ( M  -  ( A  mod  M ) )  <_  B 
<->  M  <_  ( B  +  ( A  mod  M ) ) ) )
2019biimpd 207 . . . . . . . . . 10  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  ( ( M  -  ( A  mod  M ) )  <_  B  ->  M  <_  ( B  +  ( A  mod  M ) ) ) )
2120impancom 440 . . . . . . . . 9  |-  ( ( B  e.  ZZ  /\  ( M  -  ( A  mod  M ) )  <_  B )  -> 
( ( A  e.  ZZ  /\  M  e.  NN )  ->  M  <_  ( B  +  ( A  mod  M ) ) ) )
22213adant1 1006 . . . . . . . 8  |-  ( ( ( M  -  ( A  mod  M ) )  e.  ZZ  /\  B  e.  ZZ  /\  ( M  -  ( A  mod  M ) )  <_  B
)  ->  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  M  <_  ( B  +  ( A  mod  M ) ) ) )
2312, 22sylbi 195 . . . . . . 7  |-  ( B  e.  ( ZZ>= `  ( M  -  ( A  mod  M ) ) )  ->  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  M  <_  ( B  +  ( A  mod  M ) ) ) )
24233ad2ant1 1009 . . . . . 6  |-  ( ( B  e.  ( ZZ>= `  ( M  -  ( A  mod  M ) ) )  /\  M  e.  ZZ  /\  B  < 
M )  ->  (
( A  e.  ZZ  /\  M  e.  NN )  ->  M  <_  ( B  +  ( A  mod  M ) ) ) )
2511, 24sylbi 195 . . . . 5  |-  ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  ->  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  M  <_  ( B  +  ( A  mod  M ) ) ) )
2625impcom 430 . . . 4  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  ->  M  <_  ( B  +  ( A  mod  M ) ) )
27 eluzelz 10891 . . . . . . . . 9  |-  ( B  e.  ( ZZ>= `  ( M  -  ( A  mod  M ) ) )  ->  B  e.  ZZ )
2817, 5anim12i 566 . . . . . . . . . . . . . . 15  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  ( B  e.  RR  /\  ( A  mod  M )  e.  RR ) )
2913, 13jca 532 . . . . . . . . . . . . . . . . 17  |-  ( M  e.  NN  ->  ( M  e.  RR  /\  M  e.  RR ) )
3029adantl 466 . . . . . . . . . . . . . . . 16  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( M  e.  RR  /\  M  e.  RR ) )
3130adantl 466 . . . . . . . . . . . . . . 15  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  ( M  e.  RR  /\  M  e.  RR ) )
3228, 31jca 532 . . . . . . . . . . . . . 14  |-  ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  ->  ( ( B  e.  RR  /\  ( A  mod  M )  e.  RR )  /\  ( M  e.  RR  /\  M  e.  RR ) ) )
3332adantr 465 . . . . . . . . . . . . 13  |-  ( ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  /\  B  < 
M )  ->  (
( B  e.  RR  /\  ( A  mod  M
)  e.  RR )  /\  ( M  e.  RR  /\  M  e.  RR ) ) )
34 simpr 461 . . . . . . . . . . . . . 14  |-  ( ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  /\  B  < 
M )  ->  B  <  M )
35 zre 10671 . . . . . . . . . . . . . . . . 17  |-  ( A  e.  ZZ  ->  A  e.  RR )
36 modlt 11739 . . . . . . . . . . . . . . . . 17  |-  ( ( A  e.  RR  /\  M  e.  RR+ )  -> 
( A  mod  M
)  <  M )
3735, 9, 36syl2an 477 . . . . . . . . . . . . . . . 16  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( A  mod  M
)  <  M )
385, 14, 37ltled 9543 . . . . . . . . . . . . . . 15  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( A  mod  M
)  <_  M )
3938ad2antlr 726 . . . . . . . . . . . . . 14  |-  ( ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  /\  B  < 
M )  ->  ( A  mod  M )  <_  M )
4034, 39jca 532 . . . . . . . . . . . . 13  |-  ( ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  /\  B  < 
M )  ->  ( B  <  M  /\  ( A  mod  M )  <_  M ) )
41 ltleadd 9843 . . . . . . . . . . . . 13  |-  ( ( ( B  e.  RR  /\  ( A  mod  M
)  e.  RR )  /\  ( M  e.  RR  /\  M  e.  RR ) )  -> 
( ( B  < 
M  /\  ( A  mod  M )  <_  M
)  ->  ( B  +  ( A  mod  M ) )  <  ( M  +  M )
) )
4233, 40, 41sylc 60 . . . . . . . . . . . 12  |-  ( ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  /\  B  < 
M )  ->  ( B  +  ( A  mod  M ) )  < 
( M  +  M
) )
43 nncn 10351 . . . . . . . . . . . . . . 15  |-  ( M  e.  NN  ->  M  e.  CC )
44432timesd 10588 . . . . . . . . . . . . . 14  |-  ( M  e.  NN  ->  (
2  x.  M )  =  ( M  +  M ) )
4544adantl 466 . . . . . . . . . . . . 13  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( 2  x.  M
)  =  ( M  +  M ) )
4645ad2antlr 726 . . . . . . . . . . . 12  |-  ( ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  /\  B  < 
M )  ->  (
2  x.  M )  =  ( M  +  M ) )
4742, 46breqtrrd 4339 . . . . . . . . . . 11  |-  ( ( ( B  e.  ZZ  /\  ( A  e.  ZZ  /\  M  e.  NN ) )  /\  B  < 
M )  ->  ( B  +  ( A  mod  M ) )  < 
( 2  x.  M
) )
4847exp31 604 . . . . . . . . . 10  |-  ( B  e.  ZZ  ->  (
( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  < 
M  ->  ( B  +  ( A  mod  M ) )  <  (
2  x.  M ) ) ) )
4948com23 78 . . . . . . . . 9  |-  ( B  e.  ZZ  ->  ( B  <  M  ->  (
( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  +  ( A  mod  M ) )  <  ( 2  x.  M ) ) ) )
5027, 49syl 16 . . . . . . . 8  |-  ( B  e.  ( ZZ>= `  ( M  -  ( A  mod  M ) ) )  ->  ( B  < 
M  ->  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  +  ( A  mod  M ) )  < 
( 2  x.  M
) ) ) )
5150imp 429 . . . . . . 7  |-  ( ( B  e.  ( ZZ>= `  ( M  -  ( A  mod  M ) ) )  /\  B  < 
M )  ->  (
( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  +  ( A  mod  M ) )  <  ( 2  x.  M ) ) )
52513adant2 1007 . . . . . 6  |-  ( ( B  e.  ( ZZ>= `  ( M  -  ( A  mod  M ) ) )  /\  M  e.  ZZ  /\  B  < 
M )  ->  (
( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  +  ( A  mod  M ) )  <  ( 2  x.  M ) ) )
5311, 52sylbi 195 . . . . 5  |-  ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  ->  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  +  ( A  mod  M ) )  < 
( 2  x.  M
) ) )
5453impcom 430 . . . 4  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  -> 
( B  +  ( A  mod  M ) )  <  ( 2  x.  M ) )
55 2submod 11781 . . . . 5  |-  ( ( ( ( B  +  ( A  mod  M ) )  e.  RR  /\  M  e.  RR+ )  /\  ( M  <_  ( B  +  ( A  mod  M ) )  /\  ( B  +  ( A  mod  M ) )  < 
( 2  x.  M
) ) )  -> 
( ( B  +  ( A  mod  M ) )  mod  M )  =  ( ( B  +  ( A  mod  M ) )  -  M
) )
5655eqcomd 2448 . . . 4  |-  ( ( ( ( B  +  ( A  mod  M ) )  e.  RR  /\  M  e.  RR+ )  /\  ( M  <_  ( B  +  ( A  mod  M ) )  /\  ( B  +  ( A  mod  M ) )  < 
( 2  x.  M
) ) )  -> 
( ( B  +  ( A  mod  M ) )  -  M )  =  ( ( B  +  ( A  mod  M ) )  mod  M
) )
578, 10, 26, 54, 56syl22anc 1219 . . 3  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  -> 
( ( B  +  ( A  mod  M ) )  -  M )  =  ( ( B  +  ( A  mod  M ) )  mod  M
) )
5835adantr 465 . . . . 5  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  A  e.  RR )
5958adantr 465 . . . 4  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  ->  A  e.  RR )
602adantl 466 . . . 4  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  ->  B  e.  RR )
61 modadd2mod 11770 . . . 4  |-  ( ( A  e.  RR  /\  B  e.  RR  /\  M  e.  RR+ )  ->  (
( B  +  ( A  mod  M ) )  mod  M )  =  ( ( B  +  A )  mod 
M ) )
6259, 60, 10, 61syl3anc 1218 . . 3  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  -> 
( ( B  +  ( A  mod  M ) )  mod  M )  =  ( ( B  +  A )  mod 
M ) )
6357, 62eqtrd 2475 . 2  |-  ( ( ( A  e.  ZZ  /\  M  e.  NN )  /\  B  e.  ( ( M  -  ( A  mod  M ) )..^ M ) )  -> 
( ( B  +  ( A  mod  M ) )  -  M )  =  ( ( B  +  A )  mod 
M ) )
6463ex 434 1  |-  ( ( A  e.  ZZ  /\  M  e.  NN )  ->  ( B  e.  ( ( M  -  ( A  mod  M ) )..^ M )  ->  (
( B  +  ( A  mod  M ) )  -  M )  =  ( ( B  +  A )  mod 
M ) ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    /\ wa 369    /\ w3a 965    = wceq 1369    e. wcel 1756   class class class wbr 4313   ` cfv 5439  (class class class)co 6112   RRcr 9302    + caddc 9306    x. cmul 9308    < clt 9439    <_ cle 9440    - cmin 9616   NNcn 10343   2c2 10392   ZZcz 10667   ZZ>=cuz 10882   RR+crp 11012  ..^cfzo 11569    mod cmo 11729
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1591  ax-4 1602  ax-5 1670  ax-6 1708  ax-7 1728  ax-8 1758  ax-9 1760  ax-10 1775  ax-11 1780  ax-12 1792  ax-13 1943  ax-ext 2423  ax-sep 4434  ax-nul 4442  ax-pow 4491  ax-pr 4552  ax-un 6393  ax-cnex 9359  ax-resscn 9360  ax-1cn 9361  ax-icn 9362  ax-addcl 9363  ax-addrcl 9364  ax-mulcl 9365  ax-mulrcl 9366  ax-mulcom 9367  ax-addass 9368  ax-mulass 9369  ax-distr 9370  ax-i2m1 9371  ax-1ne0 9372  ax-1rid 9373  ax-rnegex 9374  ax-rrecex 9375  ax-cnre 9376  ax-pre-lttri 9377  ax-pre-lttrn 9378  ax-pre-ltadd 9379  ax-pre-mulgt0 9380  ax-pre-sup 9381
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1372  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2257  df-mo 2258  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2577  df-ne 2622  df-nel 2623  df-ral 2741  df-rex 2742  df-reu 2743  df-rmo 2744  df-rab 2745  df-v 2995  df-sbc 3208  df-csb 3310  df-dif 3352  df-un 3354  df-in 3356  df-ss 3363  df-pss 3365  df-nul 3659  df-if 3813  df-pw 3883  df-sn 3899  df-pr 3901  df-tp 3903  df-op 3905  df-uni 4113  df-iun 4194  df-br 4314  df-opab 4372  df-mpt 4373  df-tr 4407  df-eprel 4653  df-id 4657  df-po 4662  df-so 4663  df-fr 4700  df-we 4702  df-ord 4743  df-on 4744  df-lim 4745  df-suc 4746  df-xp 4867  df-rel 4868  df-cnv 4869  df-co 4870  df-dm 4871  df-rn 4872  df-res 4873  df-ima 4874  df-iota 5402  df-fun 5441  df-fn 5442  df-f 5443  df-f1 5444  df-fo 5445  df-f1o 5446  df-fv 5447  df-riota 6073  df-ov 6115  df-oprab 6116  df-mpt2 6117  df-om 6498  df-1st 6598  df-2nd 6599  df-recs 6853  df-rdg 6887  df-er 7122  df-en 7332  df-dom 7333  df-sdom 7334  df-sup 7712  df-pnf 9441  df-mnf 9442  df-xr 9443  df-ltxr 9444  df-le 9445  df-sub 9618  df-neg 9619  df-div 10015  df-nn 10344  df-2 10401  df-n0 10601  df-z 10668  df-uz 10883  df-rp 11013  df-fz 11459  df-fzo 11570  df-fl 11663  df-mod 11730
This theorem is referenced by:  cshwidxmod  12461
  Copyright terms: Public domain W3C validator