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

Theorem cncongr2 15555
Description: The other direction of the bicondition in cncongr 15556. (Contributed by AV, 11-Jul-2021.)
Assertion
Ref Expression
cncongr2 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁)))

Proof of Theorem cncongr2
Dummy variable 𝑘 is distinct from all other variables.
StepHypRef Expression
1 zcn 11545 . . . . . . . . . 10 (𝐴 ∈ ℤ → 𝐴 ∈ ℂ)
21mul01d 10398 . . . . . . . . 9 (𝐴 ∈ ℤ → (𝐴 · 0) = 0)
323ad2ant1 1125 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐴 · 0) = 0)
4 zcn 11545 . . . . . . . . . 10 (𝐵 ∈ ℤ → 𝐵 ∈ ℂ)
54mul01d 10398 . . . . . . . . 9 (𝐵 ∈ ℤ → (𝐵 · 0) = 0)
653ad2ant2 1126 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐵 · 0) = 0)
73, 6eqtr4d 2785 . . . . . . 7 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐴 · 0) = (𝐵 · 0))
87adantr 472 . . . . . 6 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝐴 · 0) = (𝐵 · 0))
98oveq1d 6816 . . . . 5 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 · 0) mod 𝑁) = ((𝐵 · 0) mod 𝑁))
109adantr 472 . . . 4 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ (𝐴 mod 𝑀) = (𝐵 mod 𝑀)) → ((𝐴 · 0) mod 𝑁) = ((𝐵 · 0) mod 𝑁))
11 oveq2 6809 . . . . . 6 (𝐶 = 0 → (𝐴 · 𝐶) = (𝐴 · 0))
1211oveq1d 6816 . . . . 5 (𝐶 = 0 → ((𝐴 · 𝐶) mod 𝑁) = ((𝐴 · 0) mod 𝑁))
13 oveq2 6809 . . . . . 6 (𝐶 = 0 → (𝐵 · 𝐶) = (𝐵 · 0))
1413oveq1d 6816 . . . . 5 (𝐶 = 0 → ((𝐵 · 𝐶) mod 𝑁) = ((𝐵 · 0) mod 𝑁))
1512, 14eqeq12d 2763 . . . 4 (𝐶 = 0 → (((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁) ↔ ((𝐴 · 0) mod 𝑁) = ((𝐵 · 0) mod 𝑁)))
1610, 15syl5ibr 236 . . 3 (𝐶 = 0 → ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ (𝐴 mod 𝑀) = (𝐵 mod 𝑀)) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁)))
17 oveq2 6809 . . . . . . . . . 10 (𝑀 = (𝑁 / (𝐶 gcd 𝑁)) → (𝐴 mod 𝑀) = (𝐴 mod (𝑁 / (𝐶 gcd 𝑁))))
18 oveq2 6809 . . . . . . . . . 10 (𝑀 = (𝑁 / (𝐶 gcd 𝑁)) → (𝐵 mod 𝑀) = (𝐵 mod (𝑁 / (𝐶 gcd 𝑁))))
1917, 18eqeq12d 2763 . . . . . . . . 9 (𝑀 = (𝑁 / (𝐶 gcd 𝑁)) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) ↔ (𝐴 mod (𝑁 / (𝐶 gcd 𝑁))) = (𝐵 mod (𝑁 / (𝐶 gcd 𝑁)))))
2019adantl 473 . . . . . . . 8 ((𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁))) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) ↔ (𝐴 mod (𝑁 / (𝐶 gcd 𝑁))) = (𝐵 mod (𝑁 / (𝐶 gcd 𝑁)))))
2120adantl 473 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) ↔ (𝐴 mod (𝑁 / (𝐶 gcd 𝑁))) = (𝐵 mod (𝑁 / (𝐶 gcd 𝑁)))))
22 simpl 474 . . . . . . . . 9 ((𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁))) → 𝑁 ∈ ℕ)
23 simp3 1130 . . . . . . . . 9 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → 𝐶 ∈ ℤ)
24 divgcdnnr 15410 . . . . . . . . 9 ((𝑁 ∈ ℕ ∧ 𝐶 ∈ ℤ) → (𝑁 / (𝐶 gcd 𝑁)) ∈ ℕ)
2522, 23, 24syl2anr 496 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝑁 / (𝐶 gcd 𝑁)) ∈ ℕ)
26 simpl1 1204 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → 𝐴 ∈ ℤ)
27 simpl2 1206 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → 𝐵 ∈ ℤ)
28 moddvds 15164 . . . . . . . 8 (((𝑁 / (𝐶 gcd 𝑁)) ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝐴 mod (𝑁 / (𝐶 gcd 𝑁))) = (𝐵 mod (𝑁 / (𝐶 gcd 𝑁))) ↔ (𝑁 / (𝐶 gcd 𝑁)) ∥ (𝐴𝐵)))
2925, 26, 27, 28syl3anc 1463 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 mod (𝑁 / (𝐶 gcd 𝑁))) = (𝐵 mod (𝑁 / (𝐶 gcd 𝑁))) ↔ (𝑁 / (𝐶 gcd 𝑁)) ∥ (𝐴𝐵)))
3025nnzd 11644 . . . . . . . . 9 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝑁 / (𝐶 gcd 𝑁)) ∈ ℤ)
31 zsubcl 11582 . . . . . . . . . . 11 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝐴𝐵) ∈ ℤ)
32313adant3 1124 . . . . . . . . . 10 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐴𝐵) ∈ ℤ)
3332adantr 472 . . . . . . . . 9 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝐴𝐵) ∈ ℤ)
3430, 33jca 555 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝑁 / (𝐶 gcd 𝑁)) ∈ ℤ ∧ (𝐴𝐵) ∈ ℤ))
35 divides 15155 . . . . . . . 8 (((𝑁 / (𝐶 gcd 𝑁)) ∈ ℤ ∧ (𝐴𝐵) ∈ ℤ) → ((𝑁 / (𝐶 gcd 𝑁)) ∥ (𝐴𝐵) ↔ ∃𝑘 ∈ ℤ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵)))
3634, 35syl 17 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝑁 / (𝐶 gcd 𝑁)) ∥ (𝐴𝐵) ↔ ∃𝑘 ∈ ℤ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵)))
3721, 29, 363bitrd 294 . . . . . 6 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) ↔ ∃𝑘 ∈ ℤ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵)))
38 simpr 479 . . . . . . . . . . . . . . 15 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → 𝑘 ∈ ℤ)
3930adantr 472 . . . . . . . . . . . . . . . 16 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) → (𝑁 / (𝐶 gcd 𝑁)) ∈ ℤ)
4039adantr 472 . . . . . . . . . . . . . . 15 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → (𝑁 / (𝐶 gcd 𝑁)) ∈ ℤ)
4138, 40zmulcld 11651 . . . . . . . . . . . . . 14 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) ∈ ℤ)
4241zcnd 11646 . . . . . . . . . . . . 13 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) ∈ ℂ)
4331zcnd 11646 . . . . . . . . . . . . . . 15 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝐴𝐵) ∈ ℂ)
44433adant3 1124 . . . . . . . . . . . . . 14 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐴𝐵) ∈ ℂ)
4544ad3antrrr 768 . . . . . . . . . . . . 13 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → (𝐴𝐵) ∈ ℂ)
4623zcnd 11646 . . . . . . . . . . . . . 14 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → 𝐶 ∈ ℂ)
4746ad3antrrr 768 . . . . . . . . . . . . 13 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → 𝐶 ∈ ℂ)
48 simpr 479 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) → 𝐶 ≠ 0)
4948adantr 472 . . . . . . . . . . . . 13 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → 𝐶 ≠ 0)
5042, 45, 47, 49mulcan2d 10824 . . . . . . . . . . . 12 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → (((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = ((𝐴𝐵) · 𝐶) ↔ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵)))
51 zcn 11545 . . . . . . . . . . . . . . 15 (𝐶 ∈ ℤ → 𝐶 ∈ ℂ)
52 subdir 10627 . . . . . . . . . . . . . . 15 ((𝐴 ∈ ℂ ∧ 𝐵 ∈ ℂ ∧ 𝐶 ∈ ℂ) → ((𝐴𝐵) · 𝐶) = ((𝐴 · 𝐶) − (𝐵 · 𝐶)))
531, 4, 51, 52syl3an 1505 . . . . . . . . . . . . . 14 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → ((𝐴𝐵) · 𝐶) = ((𝐴 · 𝐶) − (𝐵 · 𝐶)))
5453ad3antrrr 768 . . . . . . . . . . . . 13 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → ((𝐴𝐵) · 𝐶) = ((𝐴 · 𝐶) − (𝐵 · 𝐶)))
5554eqeq2d 2758 . . . . . . . . . . . 12 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → (((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = ((𝐴𝐵) · 𝐶) ↔ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
5650, 55bitr3d 270 . . . . . . . . . . 11 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵) ↔ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
57 nnz 11562 . . . . . . . . . . . . . . . . . . . 20 (𝑁 ∈ ℕ → 𝑁 ∈ ℤ)
5857adantr 472 . . . . . . . . . . . . . . . . . . 19 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → 𝑁 ∈ ℤ)
59 simpr 479 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → 𝑘 ∈ ℤ)
6059zcnd 11646 . . . . . . . . . . . . . . . . . . . . . 22 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → 𝑘 ∈ ℂ)
6160adantl 473 . . . . . . . . . . . . . . . . . . . . 21 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → 𝑘 ∈ ℂ)
6246adantr 472 . . . . . . . . . . . . . . . . . . . . 21 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → 𝐶 ∈ ℂ)
63 simpl 474 . . . . . . . . . . . . . . . . . . . . . . . . 25 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → 𝑁 ∈ ℕ)
6463nnzd 11644 . . . . . . . . . . . . . . . . . . . . . . . 24 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → 𝑁 ∈ ℤ)
6523, 64anim12i 591 . . . . . . . . . . . . . . . . . . . . . . 23 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝐶 ∈ ℤ ∧ 𝑁 ∈ ℤ))
66 gcdcl 15401 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝐶 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝐶 gcd 𝑁) ∈ ℕ0)
6765, 66syl 17 . . . . . . . . . . . . . . . . . . . . . 22 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝐶 gcd 𝑁) ∈ ℕ0)
6867nn0cnd 11516 . . . . . . . . . . . . . . . . . . . . 21 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝐶 gcd 𝑁) ∈ ℂ)
69 nnne0 11216 . . . . . . . . . . . . . . . . . . . . . . . . . 26 (𝑁 ∈ ℕ → 𝑁 ≠ 0)
7069neneqd 2925 . . . . . . . . . . . . . . . . . . . . . . . . 25 (𝑁 ∈ ℕ → ¬ 𝑁 = 0)
7170adantr 472 . . . . . . . . . . . . . . . . . . . . . . . 24 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → ¬ 𝑁 = 0)
7271adantl 473 . . . . . . . . . . . . . . . . . . . . . . 23 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → ¬ 𝑁 = 0)
7372intnand 1000 . . . . . . . . . . . . . . . . . . . . . 22 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → ¬ (𝐶 = 0 ∧ 𝑁 = 0))
74 gcdeq0 15411 . . . . . . . . . . . . . . . . . . . . . . . 24 ((𝐶 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝐶 gcd 𝑁) = 0 ↔ (𝐶 = 0 ∧ 𝑁 = 0)))
7565, 74syl 17 . . . . . . . . . . . . . . . . . . . . . . 23 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → ((𝐶 gcd 𝑁) = 0 ↔ (𝐶 = 0 ∧ 𝑁 = 0)))
7675necon3abid 2956 . . . . . . . . . . . . . . . . . . . . . 22 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → ((𝐶 gcd 𝑁) ≠ 0 ↔ ¬ (𝐶 = 0 ∧ 𝑁 = 0)))
7773, 76mpbird 247 . . . . . . . . . . . . . . . . . . . . 21 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝐶 gcd 𝑁) ≠ 0)
7861, 62, 68, 77divassd 10999 . . . . . . . . . . . . . . . . . . . 20 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → ((𝑘 · 𝐶) / (𝐶 gcd 𝑁)) = (𝑘 · (𝐶 / (𝐶 gcd 𝑁))))
7959adantl 473 . . . . . . . . . . . . . . . . . . . . 21 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → 𝑘 ∈ ℤ)
8057, 69jca 555 . . . . . . . . . . . . . . . . . . . . . . . . 25 (𝑁 ∈ ℕ → (𝑁 ∈ ℤ ∧ 𝑁 ≠ 0))
8180adantr 472 . . . . . . . . . . . . . . . . . . . . . . . 24 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → (𝑁 ∈ ℤ ∧ 𝑁 ≠ 0))
8223, 81anim12i 591 . . . . . . . . . . . . . . . . . . . . . . 23 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝐶 ∈ ℤ ∧ (𝑁 ∈ ℤ ∧ 𝑁 ≠ 0)))
83 3anass 1081 . . . . . . . . . . . . . . . . . . . . . . 23 ((𝐶 ∈ ℤ ∧ 𝑁 ∈ ℤ ∧ 𝑁 ≠ 0) ↔ (𝐶 ∈ ℤ ∧ (𝑁 ∈ ℤ ∧ 𝑁 ≠ 0)))
8482, 83sylibr 224 . . . . . . . . . . . . . . . . . . . . . 22 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝐶 ∈ ℤ ∧ 𝑁 ∈ ℤ ∧ 𝑁 ≠ 0))
85 divgcdz 15406 . . . . . . . . . . . . . . . . . . . . . 22 ((𝐶 ∈ ℤ ∧ 𝑁 ∈ ℤ ∧ 𝑁 ≠ 0) → (𝐶 / (𝐶 gcd 𝑁)) ∈ ℤ)
8684, 85syl 17 . . . . . . . . . . . . . . . . . . . . 21 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝐶 / (𝐶 gcd 𝑁)) ∈ ℤ)
8779, 86zmulcld 11651 . . . . . . . . . . . . . . . . . . . 20 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → (𝑘 · (𝐶 / (𝐶 gcd 𝑁))) ∈ ℤ)
8878, 87eqeltrd 2827 . . . . . . . . . . . . . . . . . . 19 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → ((𝑘 · 𝐶) / (𝐶 gcd 𝑁)) ∈ ℤ)
89 dvdsmul1 15176 . . . . . . . . . . . . . . . . . . 19 ((𝑁 ∈ ℤ ∧ ((𝑘 · 𝐶) / (𝐶 gcd 𝑁)) ∈ ℤ) → 𝑁 ∥ (𝑁 · ((𝑘 · 𝐶) / (𝐶 gcd 𝑁))))
9058, 88, 89syl2an2 910 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → 𝑁 ∥ (𝑁 · ((𝑘 · 𝐶) / (𝐶 gcd 𝑁))))
9163nncnd 11199 . . . . . . . . . . . . . . . . . . . 20 ((𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ) → 𝑁 ∈ ℂ)
9291adantl 473 . . . . . . . . . . . . . . . . . . 19 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → 𝑁 ∈ ℂ)
93 divmulasscom 10872 . . . . . . . . . . . . . . . . . . 19 (((𝑘 ∈ ℂ ∧ 𝑁 ∈ ℂ ∧ 𝐶 ∈ ℂ) ∧ ((𝐶 gcd 𝑁) ∈ ℂ ∧ (𝐶 gcd 𝑁) ≠ 0)) → ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = (𝑁 · ((𝑘 · 𝐶) / (𝐶 gcd 𝑁))))
9461, 92, 62, 68, 77, 93syl32anc 1471 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = (𝑁 · ((𝑘 · 𝐶) / (𝐶 gcd 𝑁))))
9590, 94breqtrrd 4820 . . . . . . . . . . . . . . . . 17 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑘 ∈ ℤ)) → 𝑁 ∥ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶))
9695exp32 632 . . . . . . . . . . . . . . . 16 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝑁 ∈ ℕ → (𝑘 ∈ ℤ → 𝑁 ∥ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶))))
9796adantrd 485 . . . . . . . . . . . . . . 15 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → ((𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁))) → (𝑘 ∈ ℤ → 𝑁 ∥ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶))))
9897imp 444 . . . . . . . . . . . . . 14 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝑘 ∈ ℤ → 𝑁 ∥ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶)))
9998adantr 472 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) → (𝑘 ∈ ℤ → 𝑁 ∥ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶)))
10099imp 444 . . . . . . . . . . . 12 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → 𝑁 ∥ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶))
101 breq2 4796 . . . . . . . . . . . 12 (((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = ((𝐴 · 𝐶) − (𝐵 · 𝐶)) → (𝑁 ∥ ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) ↔ 𝑁 ∥ ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
102100, 101syl5ibcom 235 . . . . . . . . . . 11 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → (((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) · 𝐶) = ((𝐴 · 𝐶) − (𝐵 · 𝐶)) → 𝑁 ∥ ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
10356, 102sylbid 230 . . . . . . . . . 10 (((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) ∧ 𝑘 ∈ ℤ) → ((𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵) → 𝑁 ∥ ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
104103rexlimdva 3157 . . . . . . . . 9 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) → (∃𝑘 ∈ ℤ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵) → 𝑁 ∥ ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
10522adantl 473 . . . . . . . . . . 11 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → 𝑁 ∈ ℕ)
106 zmulcl 11589 . . . . . . . . . . . . 13 ((𝐴 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐴 · 𝐶) ∈ ℤ)
1071063adant2 1123 . . . . . . . . . . . 12 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐴 · 𝐶) ∈ ℤ)
108107adantr 472 . . . . . . . . . . 11 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝐴 · 𝐶) ∈ ℤ)
109 zmulcl 11589 . . . . . . . . . . . . 13 ((𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐵 · 𝐶) ∈ ℤ)
1101093adant1 1122 . . . . . . . . . . . 12 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐵 · 𝐶) ∈ ℤ)
111110adantr 472 . . . . . . . . . . 11 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝐵 · 𝐶) ∈ ℤ)
112 moddvds 15164 . . . . . . . . . . 11 ((𝑁 ∈ ℕ ∧ (𝐴 · 𝐶) ∈ ℤ ∧ (𝐵 · 𝐶) ∈ ℤ) → (((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁) ↔ 𝑁 ∥ ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
113105, 108, 111, 112syl3anc 1463 . . . . . . . . . 10 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁) ↔ 𝑁 ∥ ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
114113adantr 472 . . . . . . . . 9 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) → (((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁) ↔ 𝑁 ∥ ((𝐴 · 𝐶) − (𝐵 · 𝐶))))
115104, 114sylibrd 249 . . . . . . . 8 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ 𝐶 ≠ 0) → (∃𝑘 ∈ ℤ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁)))
116115ex 449 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (𝐶 ≠ 0 → (∃𝑘 ∈ ℤ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁))))
117116com23 86 . . . . . 6 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (∃𝑘 ∈ ℤ (𝑘 · (𝑁 / (𝐶 gcd 𝑁))) = (𝐴𝐵) → (𝐶 ≠ 0 → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁))))
11837, 117sylbid 230 . . . . 5 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) → (𝐶 ≠ 0 → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁))))
119118imp 444 . . . 4 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ (𝐴 mod 𝑀) = (𝐵 mod 𝑀)) → (𝐶 ≠ 0 → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁)))
120119com12 32 . . 3 (𝐶 ≠ 0 → ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ (𝐴 mod 𝑀) = (𝐵 mod 𝑀)) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁)))
12116, 120pm2.61ine 3003 . 2 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) ∧ (𝐴 mod 𝑀) = (𝐵 mod 𝑀)) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁))
122121ex 449 1 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁)))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 196  wa 383  w3a 1072   = wceq 1620  wcel 2127  wne 2920  wrex 3039   class class class wbr 4792  (class class class)co 6801  cc 10097  0cc0 10099   · cmul 10104  cmin 10429   / cdiv 10847  cn 11183  0cn0 11455  cz 11540   mod cmo 12833  cdvds 15153   gcd cgcd 15389
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1859  ax-4 1874  ax-5 1976  ax-6 2042  ax-7 2078  ax-8 2129  ax-9 2136  ax-10 2156  ax-11 2171  ax-12 2184  ax-13 2379  ax-ext 2728  ax-sep 4921  ax-nul 4929  ax-pow 4980  ax-pr 5043  ax-un 7102  ax-cnex 10155  ax-resscn 10156  ax-1cn 10157  ax-icn 10158  ax-addcl 10159  ax-addrcl 10160  ax-mulcl 10161  ax-mulrcl 10162  ax-mulcom 10163  ax-addass 10164  ax-mulass 10165  ax-distr 10166  ax-i2m1 10167  ax-1ne0 10168  ax-1rid 10169  ax-rnegex 10170  ax-rrecex 10171  ax-cnre 10172  ax-pre-lttri 10173  ax-pre-lttrn 10174  ax-pre-ltadd 10175  ax-pre-mulgt0 10176  ax-pre-sup 10177
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1623  df-ex 1842  df-nf 1847  df-sb 2035  df-eu 2599  df-mo 2600  df-clab 2735  df-cleq 2741  df-clel 2744  df-nfc 2879  df-ne 2921  df-nel 3024  df-ral 3043  df-rex 3044  df-reu 3045  df-rmo 3046  df-rab 3047  df-v 3330  df-sbc 3565  df-csb 3663  df-dif 3706  df-un 3708  df-in 3710  df-ss 3717  df-pss 3719  df-nul 4047  df-if 4219  df-pw 4292  df-sn 4310  df-pr 4312  df-tp 4314  df-op 4316  df-uni 4577  df-iun 4662  df-br 4793  df-opab 4853  df-mpt 4870  df-tr 4893  df-id 5162  df-eprel 5167  df-po 5175  df-so 5176  df-fr 5213  df-we 5215  df-xp 5260  df-rel 5261  df-cnv 5262  df-co 5263  df-dm 5264  df-rn 5265  df-res 5266  df-ima 5267  df-pred 5829  df-ord 5875  df-on 5876  df-lim 5877  df-suc 5878  df-iota 6000  df-fun 6039  df-fn 6040  df-f 6041  df-f1 6042  df-fo 6043  df-f1o 6044  df-fv 6045  df-riota 6762  df-ov 6804  df-oprab 6805  df-mpt2 6806  df-om 7219  df-2nd 7322  df-wrecs 7564  df-recs 7625  df-rdg 7663  df-er 7899  df-en 8110  df-dom 8111  df-sdom 8112  df-sup 8501  df-inf 8502  df-pnf 10239  df-mnf 10240  df-xr 10241  df-ltxr 10242  df-le 10243  df-sub 10431  df-neg 10432  df-div 10848  df-nn 11184  df-2 11242  df-3 11243  df-n0 11456  df-z 11541  df-uz 11851  df-rp 11997  df-fl 12758  df-mod 12834  df-seq 12967  df-exp 13026  df-cj 14009  df-re 14010  df-im 14011  df-sqrt 14145  df-abs 14146  df-dvds 15154  df-gcd 15390
This theorem is referenced by:  cncongr  15556
  Copyright terms: Public domain W3C validator