Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
||
Mirrors > Home > MPE Home > Th. List > addmodlteqALT | Structured version Visualization version GIF version |
Description: Two nonnegative integers less than the modulus are equal iff the sums of these integer with another integer are equal modulo the modulus. Shorter proof of addmodlteq 13779 based on the "divides" relation. (Contributed by AV, 14-Mar-2021.) (New usage is discouraged.) (Proof modification is discouraged.) |
Ref | Expression |
---|---|
addmodlteqALT | ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → (((𝐼 + 𝑆) mod 𝑁) = ((𝐽 + 𝑆) mod 𝑁) ↔ 𝐼 = 𝐽)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | elfzo0 13541 | . . . . 5 ⊢ (𝐼 ∈ (0..^𝑁) ↔ (𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ ∧ 𝐼 < 𝑁)) | |
2 | elfzoelz 13500 | . . . . . . . 8 ⊢ (𝐽 ∈ (0..^𝑁) → 𝐽 ∈ ℤ) | |
3 | simplrr 776 | . . . . . . . . . 10 ⊢ (((𝐽 ∈ ℤ ∧ (𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ)) ∧ 𝑆 ∈ ℤ) → 𝑁 ∈ ℕ) | |
4 | nn0z 12456 | . . . . . . . . . . . 12 ⊢ (𝐼 ∈ ℕ0 → 𝐼 ∈ ℤ) | |
5 | 4 | ad2antrl 726 | . . . . . . . . . . 11 ⊢ ((𝐽 ∈ ℤ ∧ (𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ)) → 𝐼 ∈ ℤ) |
6 | zaddcl 12473 | . . . . . . . . . . 11 ⊢ ((𝐼 ∈ ℤ ∧ 𝑆 ∈ ℤ) → (𝐼 + 𝑆) ∈ ℤ) | |
7 | 5, 6 | sylan 580 | . . . . . . . . . 10 ⊢ (((𝐽 ∈ ℤ ∧ (𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ)) ∧ 𝑆 ∈ ℤ) → (𝐼 + 𝑆) ∈ ℤ) |
8 | zaddcl 12473 | . . . . . . . . . . 11 ⊢ ((𝐽 ∈ ℤ ∧ 𝑆 ∈ ℤ) → (𝐽 + 𝑆) ∈ ℤ) | |
9 | 8 | adantlr 713 | . . . . . . . . . 10 ⊢ (((𝐽 ∈ ℤ ∧ (𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ)) ∧ 𝑆 ∈ ℤ) → (𝐽 + 𝑆) ∈ ℤ) |
10 | 3, 7, 9 | 3jca 1128 | . . . . . . . . 9 ⊢ (((𝐽 ∈ ℤ ∧ (𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ)) ∧ 𝑆 ∈ ℤ) → (𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ)) |
11 | 10 | exp31 420 | . . . . . . . 8 ⊢ (𝐽 ∈ ℤ → ((𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ) → (𝑆 ∈ ℤ → (𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ)))) |
12 | 2, 11 | syl 17 | . . . . . . 7 ⊢ (𝐽 ∈ (0..^𝑁) → ((𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ) → (𝑆 ∈ ℤ → (𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ)))) |
13 | 12 | com12 32 | . . . . . 6 ⊢ ((𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ) → (𝐽 ∈ (0..^𝑁) → (𝑆 ∈ ℤ → (𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ)))) |
14 | 13 | 3adant3 1132 | . . . . 5 ⊢ ((𝐼 ∈ ℕ0 ∧ 𝑁 ∈ ℕ ∧ 𝐼 < 𝑁) → (𝐽 ∈ (0..^𝑁) → (𝑆 ∈ ℤ → (𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ)))) |
15 | 1, 14 | sylbi 216 | . . . 4 ⊢ (𝐼 ∈ (0..^𝑁) → (𝐽 ∈ (0..^𝑁) → (𝑆 ∈ ℤ → (𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ)))) |
16 | 15 | 3imp 1111 | . . 3 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → (𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ)) |
17 | moddvds 16081 | . . 3 ⊢ ((𝑁 ∈ ℕ ∧ (𝐼 + 𝑆) ∈ ℤ ∧ (𝐽 + 𝑆) ∈ ℤ) → (((𝐼 + 𝑆) mod 𝑁) = ((𝐽 + 𝑆) mod 𝑁) ↔ 𝑁 ∥ ((𝐼 + 𝑆) − (𝐽 + 𝑆)))) | |
18 | 16, 17 | syl 17 | . 2 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → (((𝐼 + 𝑆) mod 𝑁) = ((𝐽 + 𝑆) mod 𝑁) ↔ 𝑁 ∥ ((𝐼 + 𝑆) − (𝐽 + 𝑆)))) |
19 | elfzoel2 13499 | . . . . 5 ⊢ (𝐼 ∈ (0..^𝑁) → 𝑁 ∈ ℤ) | |
20 | zcn 12437 | . . . . . . 7 ⊢ (𝑁 ∈ ℤ → 𝑁 ∈ ℂ) | |
21 | 20 | subid1d 11434 | . . . . . 6 ⊢ (𝑁 ∈ ℤ → (𝑁 − 0) = 𝑁) |
22 | 21 | eqcomd 2743 | . . . . 5 ⊢ (𝑁 ∈ ℤ → 𝑁 = (𝑁 − 0)) |
23 | 19, 22 | syl 17 | . . . 4 ⊢ (𝐼 ∈ (0..^𝑁) → 𝑁 = (𝑁 − 0)) |
24 | 23 | 3ad2ant1 1133 | . . 3 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → 𝑁 = (𝑁 − 0)) |
25 | elfzoelz 13500 | . . . . 5 ⊢ (𝐼 ∈ (0..^𝑁) → 𝐼 ∈ ℤ) | |
26 | 25 | zcnd 12540 | . . . 4 ⊢ (𝐼 ∈ (0..^𝑁) → 𝐼 ∈ ℂ) |
27 | 2 | zcnd 12540 | . . . 4 ⊢ (𝐽 ∈ (0..^𝑁) → 𝐽 ∈ ℂ) |
28 | zcn 12437 | . . . 4 ⊢ (𝑆 ∈ ℤ → 𝑆 ∈ ℂ) | |
29 | pnpcan2 11374 | . . . 4 ⊢ ((𝐼 ∈ ℂ ∧ 𝐽 ∈ ℂ ∧ 𝑆 ∈ ℂ) → ((𝐼 + 𝑆) − (𝐽 + 𝑆)) = (𝐼 − 𝐽)) | |
30 | 26, 27, 28, 29 | syl3an 1160 | . . 3 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → ((𝐼 + 𝑆) − (𝐽 + 𝑆)) = (𝐼 − 𝐽)) |
31 | 24, 30 | breq12d 5116 | . 2 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → (𝑁 ∥ ((𝐼 + 𝑆) − (𝐽 + 𝑆)) ↔ (𝑁 − 0) ∥ (𝐼 − 𝐽))) |
32 | fzocongeq 16140 | . . 3 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁)) → ((𝑁 − 0) ∥ (𝐼 − 𝐽) ↔ 𝐼 = 𝐽)) | |
33 | 32 | 3adant3 1132 | . 2 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → ((𝑁 − 0) ∥ (𝐼 − 𝐽) ↔ 𝐼 = 𝐽)) |
34 | 18, 31, 33 | 3bitrd 304 | 1 ⊢ ((𝐼 ∈ (0..^𝑁) ∧ 𝐽 ∈ (0..^𝑁) ∧ 𝑆 ∈ ℤ) → (((𝐼 + 𝑆) mod 𝑁) = ((𝐽 + 𝑆) mod 𝑁) ↔ 𝐼 = 𝐽)) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 205 ∧ wa 396 ∧ w3a 1087 = wceq 1541 ∈ wcel 2106 class class class wbr 5103 (class class class)co 7349 ℂcc 10982 0cc0 10984 + caddc 10987 < clt 11122 − cmin 11318 ℕcn 12086 ℕ0cn0 12346 ℤcz 12432 ..^cfzo 13495 mod cmo 13702 ∥ cdvds 16070 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1797 ax-4 1811 ax-5 1913 ax-6 1971 ax-7 2011 ax-8 2108 ax-9 2116 ax-10 2137 ax-11 2154 ax-12 2171 ax-ext 2708 ax-sep 5254 ax-nul 5261 ax-pow 5318 ax-pr 5382 ax-un 7662 ax-cnex 11040 ax-resscn 11041 ax-1cn 11042 ax-icn 11043 ax-addcl 11044 ax-addrcl 11045 ax-mulcl 11046 ax-mulrcl 11047 ax-mulcom 11048 ax-addass 11049 ax-mulass 11050 ax-distr 11051 ax-i2m1 11052 ax-1ne0 11053 ax-1rid 11054 ax-rnegex 11055 ax-rrecex 11056 ax-cnre 11057 ax-pre-lttri 11058 ax-pre-lttrn 11059 ax-pre-ltadd 11060 ax-pre-mulgt0 11061 ax-pre-sup 11062 |
This theorem depends on definitions: df-bi 206 df-an 397 df-or 846 df-3or 1088 df-3an 1089 df-tru 1544 df-fal 1554 df-ex 1782 df-nf 1786 df-sb 2068 df-mo 2539 df-eu 2568 df-clab 2715 df-cleq 2729 df-clel 2815 df-nfc 2887 df-ne 2942 df-nel 3048 df-ral 3063 df-rex 3072 df-rmo 3351 df-reu 3352 df-rab 3406 df-v 3445 df-sbc 3738 df-csb 3854 df-dif 3911 df-un 3913 df-in 3915 df-ss 3925 df-pss 3927 df-nul 4281 df-if 4485 df-pw 4560 df-sn 4585 df-pr 4587 df-op 4591 df-uni 4864 df-iun 4954 df-br 5104 df-opab 5166 df-mpt 5187 df-tr 5221 df-id 5528 df-eprel 5534 df-po 5542 df-so 5543 df-fr 5585 df-we 5587 df-xp 5636 df-rel 5637 df-cnv 5638 df-co 5639 df-dm 5640 df-rn 5641 df-res 5642 df-ima 5643 df-pred 6249 df-ord 6316 df-on 6317 df-lim 6318 df-suc 6319 df-iota 6443 df-fun 6493 df-fn 6494 df-f 6495 df-f1 6496 df-fo 6497 df-f1o 6498 df-fv 6499 df-riota 7305 df-ov 7352 df-oprab 7353 df-mpo 7354 df-om 7793 df-1st 7911 df-2nd 7912 df-frecs 8179 df-wrecs 8210 df-recs 8284 df-rdg 8323 df-er 8581 df-en 8817 df-dom 8818 df-sdom 8819 df-sup 9311 df-inf 9312 df-pnf 11124 df-mnf 11125 df-xr 11126 df-ltxr 11127 df-le 11128 df-sub 11320 df-neg 11321 df-div 11746 df-nn 12087 df-2 12149 df-3 12150 df-n0 12347 df-z 12433 df-uz 12696 df-rp 12844 df-fz 13353 df-fzo 13496 df-fl 13625 df-mod 13703 df-seq 13835 df-exp 13896 df-cj 14917 df-re 14918 df-im 14919 df-sqrt 15053 df-abs 15054 df-dvds 16071 |
This theorem is referenced by: (None) |
Copyright terms: Public domain | W3C validator |