modaddmodup - Metamath Proof Explorer

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

Theorem modaddmodup 13869

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	⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) → ((𝐵 + (𝐴 mod 𝑀)) − 𝑀) = ((𝐵 + 𝐴) mod 𝑀)))

**Proof of Theorem modaddmodup**
Step	Hyp	Ref	Expression
1		elfzoelz 13587	. . . . . . . 8 ⊢ (𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) → 𝐵 ∈ ℤ)
2	1	zred 12608	. . . . . . 7 ⊢ (𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) → 𝐵 ∈ ℝ)
3	2	adantr 480	. . . . . 6 ⊢ ((𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → 𝐵 ∈ ℝ)
4		zmodcl 13823	. . . . . . . 8 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐴 mod 𝑀) ∈ ℕ₀)
5	4	nn0red 12475	. . . . . . 7 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐴 mod 𝑀) ∈ ℝ)
6	5	adantl 481	. . . . . 6 ⊢ ((𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → (𝐴 mod 𝑀) ∈ ℝ)
7	3, 6	readdcld 11173	. . . . 5 ⊢ ((𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → (𝐵 + (𝐴 mod 𝑀)) ∈ ℝ)
8	7	ancoms 458	. . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → (𝐵 + (𝐴 mod 𝑀)) ∈ ℝ)
9		nnrp 12929	. . . . 5 ⊢ (𝑀 ∈ ℕ → 𝑀 ∈ ℝ⁺)
10	9	ad2antlr 728	. . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → 𝑀 ∈ ℝ⁺)
11		elfzo2 13590	. . . . . 6 ⊢ (𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) ↔ (𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) ∧ 𝑀 ∈ ℤ ∧ 𝐵 < 𝑀))
12		eluz2 12769	. . . . . . . 8 ⊢ (𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) ↔ ((𝑀 − (𝐴 mod 𝑀)) ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ (𝑀 − (𝐴 mod 𝑀)) ≤ 𝐵))
13		nnre 12164	. . . . . . . . . . . . . 14 ⊢ (𝑀 ∈ ℕ → 𝑀 ∈ ℝ)
14	13	adantl 481	. . . . . . . . . . . . 13 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → 𝑀 ∈ ℝ)
15	14	adantl 481	. . . . . . . . . . . 12 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → 𝑀 ∈ ℝ)
16	5	adantl 481	. . . . . . . . . . . 12 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → (𝐴 mod 𝑀) ∈ ℝ)
17		zre 12504	. . . . . . . . . . . . 13 ⊢ (𝐵 ∈ ℤ → 𝐵 ∈ ℝ)
18	17	adantr 480	. . . . . . . . . . . 12 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → 𝐵 ∈ ℝ)
19	15, 16, 18	lesubaddd 11746	. . . . . . . . . . 11 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → ((𝑀 − (𝐴 mod 𝑀)) ≤ 𝐵 ↔ 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀))))
20	19	biimpd 229	. . . . . . . . . 10 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → ((𝑀 − (𝐴 mod 𝑀)) ≤ 𝐵 → 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀))))
21	20	impancom 451	. . . . . . . . 9 ⊢ ((𝐵 ∈ ℤ ∧ (𝑀 − (𝐴 mod 𝑀)) ≤ 𝐵) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀))))
22	21	3adant1 1131	. . . . . . . 8 ⊢ (((𝑀 − (𝐴 mod 𝑀)) ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ (𝑀 − (𝐴 mod 𝑀)) ≤ 𝐵) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀))))
23	12, 22	sylbi 217	. . . . . . 7 ⊢ (𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀))))
24	23	3ad2ant1 1134	. . . . . 6 ⊢ ((𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) ∧ 𝑀 ∈ ℤ ∧ 𝐵 < 𝑀) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀))))
25	11, 24	sylbi 217	. . . . 5 ⊢ (𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀))))
26	25	impcom 407	. . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → 𝑀 ≤ (𝐵 + (𝐴 mod 𝑀)))
27		eluzelz 12773	. . . . . . . . 9 ⊢ (𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) → 𝐵 ∈ ℤ)
28	17, 5	anim12i 614	. . . . . . . . . . . . . . 15 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → (𝐵 ∈ ℝ ∧ (𝐴 mod 𝑀) ∈ ℝ))
29	13, 13	jca 511	. . . . . . . . . . . . . . . . 17 ⊢ (𝑀 ∈ ℕ → (𝑀 ∈ ℝ ∧ 𝑀 ∈ ℝ))
30	29	adantl 481	. . . . . . . . . . . . . . . 16 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝑀 ∈ ℝ ∧ 𝑀 ∈ ℝ))
31	30	adantl 481	. . . . . . . . . . . . . . 15 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → (𝑀 ∈ ℝ ∧ 𝑀 ∈ ℝ))
32	28, 31	jca 511	. . . . . . . . . . . . . 14 ⊢ ((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) → ((𝐵 ∈ ℝ ∧ (𝐴 mod 𝑀) ∈ ℝ) ∧ (𝑀 ∈ ℝ ∧ 𝑀 ∈ ℝ)))
33	32	adantr 480	. . . . . . . . . . . . 13 ⊢ (((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) ∧ 𝐵 < 𝑀) → ((𝐵 ∈ ℝ ∧ (𝐴 mod 𝑀) ∈ ℝ) ∧ (𝑀 ∈ ℝ ∧ 𝑀 ∈ ℝ)))
34		simpr 484	. . . . . . . . . . . . . 14 ⊢ (((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) ∧ 𝐵 < 𝑀) → 𝐵 < 𝑀)
35		zre 12504	. . . . . . . . . . . . . . . . 17 ⊢ (𝐴 ∈ ℤ → 𝐴 ∈ ℝ)
36		modlt 13812	. . . . . . . . . . . . . . . . 17 ⊢ ((𝐴 ∈ ℝ ∧ 𝑀 ∈ ℝ⁺) → (𝐴 mod 𝑀) < 𝑀)
37	35, 9, 36	syl2an 597	. . . . . . . . . . . . . . . 16 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐴 mod 𝑀) < 𝑀)
38	5, 14, 37	ltled 11293	. . . . . . . . . . . . . . 15 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐴 mod 𝑀) ≤ 𝑀)
39	38	ad2antlr 728	. . . . . . . . . . . . . 14 ⊢ (((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) ∧ 𝐵 < 𝑀) → (𝐴 mod 𝑀) ≤ 𝑀)
40	34, 39	jca 511	. . . . . . . . . . . . 13 ⊢ (((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) ∧ 𝐵 < 𝑀) → (𝐵 < 𝑀 ∧ (𝐴 mod 𝑀) ≤ 𝑀))
41		ltleadd 11632	. . . . . . . . . . . . 13 ⊢ (((𝐵 ∈ ℝ ∧ (𝐴 mod 𝑀) ∈ ℝ) ∧ (𝑀 ∈ ℝ ∧ 𝑀 ∈ ℝ)) → ((𝐵 < 𝑀 ∧ (𝐴 mod 𝑀) ≤ 𝑀) → (𝐵 + (𝐴 mod 𝑀)) < (𝑀 + 𝑀)))
42	33, 40, 41	sylc 65	. . . . . . . . . . . 12 ⊢ (((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) ∧ 𝐵 < 𝑀) → (𝐵 + (𝐴 mod 𝑀)) < (𝑀 + 𝑀))
43		nncn 12165	. . . . . . . . . . . . . . 15 ⊢ (𝑀 ∈ ℕ → 𝑀 ∈ ℂ)
44	43	2timesd 12396	. . . . . . . . . . . . . 14 ⊢ (𝑀 ∈ ℕ → (2 · 𝑀) = (𝑀 + 𝑀))
45	44	adantl 481	. . . . . . . . . . . . 13 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (2 · 𝑀) = (𝑀 + 𝑀))
46	45	ad2antlr 728	. . . . . . . . . . . 12 ⊢ (((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) ∧ 𝐵 < 𝑀) → (2 · 𝑀) = (𝑀 + 𝑀))
47	42, 46	breqtrrd 5128	. . . . . . . . . . 11 ⊢ (((𝐵 ∈ ℤ ∧ (𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ)) ∧ 𝐵 < 𝑀) → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀))
48	47	exp31 419	. . . . . . . . . 10 ⊢ (𝐵 ∈ ℤ → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 < 𝑀 → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀))))
49	48	com23 86	. . . . . . . . 9 ⊢ (𝐵 ∈ ℤ → (𝐵 < 𝑀 → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀))))
50	27, 49	syl 17	. . . . . . . 8 ⊢ (𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) → (𝐵 < 𝑀 → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀))))
51	50	imp 406	. . . . . . 7 ⊢ ((𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) ∧ 𝐵 < 𝑀) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀)))
52	51	3adant2 1132	. . . . . 6 ⊢ ((𝐵 ∈ (ℤ_≥‘(𝑀 − (𝐴 mod 𝑀))) ∧ 𝑀 ∈ ℤ ∧ 𝐵 < 𝑀) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀)))
53	11, 52	sylbi 217	. . . . 5 ⊢ (𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) → ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀)))
54	53	impcom 407	. . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀))
55		2submod 13867	. . . . 5 ⊢ ((((𝐵 + (𝐴 mod 𝑀)) ∈ ℝ ∧ 𝑀 ∈ ℝ⁺) ∧ (𝑀 ≤ (𝐵 + (𝐴 mod 𝑀)) ∧ (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀))) → ((𝐵 + (𝐴 mod 𝑀)) mod 𝑀) = ((𝐵 + (𝐴 mod 𝑀)) − 𝑀))
56	55	eqcomd 2743	. . . 4 ⊢ ((((𝐵 + (𝐴 mod 𝑀)) ∈ ℝ ∧ 𝑀 ∈ ℝ⁺) ∧ (𝑀 ≤ (𝐵 + (𝐴 mod 𝑀)) ∧ (𝐵 + (𝐴 mod 𝑀)) < (2 · 𝑀))) → ((𝐵 + (𝐴 mod 𝑀)) − 𝑀) = ((𝐵 + (𝐴 mod 𝑀)) mod 𝑀))
57	8, 10, 26, 54, 56	syl22anc 839	. . 3 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → ((𝐵 + (𝐴 mod 𝑀)) − 𝑀) = ((𝐵 + (𝐴 mod 𝑀)) mod 𝑀))
58	35	adantr 480	. . . . 5 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → 𝐴 ∈ ℝ)
59	58	adantr 480	. . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → 𝐴 ∈ ℝ)
60	2	adantl 481	. . . 4 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → 𝐵 ∈ ℝ)
61		modadd2mod 13856	. . . 4 ⊢ ((𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ ∧ 𝑀 ∈ ℝ⁺) → ((𝐵 + (𝐴 mod 𝑀)) mod 𝑀) = ((𝐵 + 𝐴) mod 𝑀))
62	59, 60, 10, 61	syl3anc 1374	. . 3 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → ((𝐵 + (𝐴 mod 𝑀)) mod 𝑀) = ((𝐵 + 𝐴) mod 𝑀))
63	57, 62	eqtrd 2772	. 2 ⊢ (((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) ∧ 𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀)) → ((𝐵 + (𝐴 mod 𝑀)) − 𝑀) = ((𝐵 + 𝐴) mod 𝑀))
64	63	ex 412	1 ⊢ ((𝐴 ∈ ℤ ∧ 𝑀 ∈ ℕ) → (𝐵 ∈ ((𝑀 − (𝐴 mod 𝑀))..^𝑀) → ((𝐵 + (𝐴 mod 𝑀)) − 𝑀) = ((𝐵 + 𝐴) mod 𝑀)))

Colors of variables: wff setvar class

Syntax hints: → wi 4 ∧ wa 395 ∧ w3a 1087 = wceq 1542 ∈ wcel 2114 class class class wbr 5100 ‘cfv 6500 (class class class)co 7368 ℝcr 11037 + caddc 11041 · cmul 11043 < clt 11178 ≤ cle 11179 − cmin 11376 ℕcn 12157 2c2 12212 ℤcz 12500 ℤ_≥cuz 12763 ℝ⁺crp 12917 ..^cfzo 13582 mod cmo 13801

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 1912 ax-6 1969 ax-7 2010 ax-8 2116 ax-9 2124 ax-10 2147 ax-11 2163 ax-12 2185 ax-ext 2709 ax-sep 5243 ax-nul 5253 ax-pow 5312 ax-pr 5379 ax-un 7690 ax-cnex 11094 ax-resscn 11095 ax-1cn 11096 ax-icn 11097 ax-addcl 11098 ax-addrcl 11099 ax-mulcl 11100 ax-mulrcl 11101 ax-mulcom 11102 ax-addass 11103 ax-mulass 11104 ax-distr 11105 ax-i2m1 11106 ax-1ne0 11107 ax-1rid 11108 ax-rnegex 11109 ax-rrecex 11110 ax-cnre 11111 ax-pre-lttri 11112 ax-pre-lttrn 11113 ax-pre-ltadd 11114 ax-pre-mulgt0 11115 ax-pre-sup 11116

This theorem depends on definitions: df-bi 207 df-an 396 df-or 849 df-3or 1088 df-3an 1089 df-tru 1545 df-fal 1555 df-ex 1782 df-nf 1786 df-sb 2069 df-mo 2540 df-eu 2570 df-clab 2716 df-cleq 2729 df-clel 2812 df-nfc 2886 df-ne 2934 df-nel 3038 df-ral 3053 df-rex 3063 df-rmo 3352 df-reu 3353 df-rab 3402 df-v 3444 df-sbc 3743 df-csb 3852 df-dif 3906 df-un 3908 df-in 3910 df-ss 3920 df-pss 3923 df-nul 4288 df-if 4482 df-pw 4558 df-sn 4583 df-pr 4585 df-op 4589 df-uni 4866 df-iun 4950 df-br 5101 df-opab 5163 df-mpt 5182 df-tr 5208 df-id 5527 df-eprel 5532 df-po 5540 df-so 5541 df-fr 5585 df-we 5587 df-xp 5638 df-rel 5639 df-cnv 5640 df-co 5641 df-dm 5642 df-rn 5643 df-res 5644 df-ima 5645 df-pred 6267 df-ord 6328 df-on 6329 df-lim 6330 df-suc 6331 df-iota 6456 df-fun 6502 df-fn 6503 df-f 6504 df-f1 6505 df-fo 6506 df-f1o 6507 df-fv 6508 df-riota 7325 df-ov 7371 df-oprab 7372 df-mpo 7373 df-om 7819 df-1st 7943 df-2nd 7944 df-frecs 8233 df-wrecs 8264 df-recs 8313 df-rdg 8351 df-er 8645 df-en 8896 df-dom 8897 df-sdom 8898 df-sup 9357 df-inf 9358 df-pnf 11180 df-mnf 11181 df-xr 11182 df-ltxr 11183 df-le 11184 df-sub 11378 df-neg 11379 df-div 11807 df-nn 12158 df-2 12220 df-n0 12414 df-z 12501 df-uz 12764 df-rp 12918 df-fz 13436 df-fzo 13583 df-fl 13724 df-mod 13802

This theorem is referenced by: cshwidxmod 14738

W3C validator