Metamath Proof Explorer


Theorem modremain

Description: The result of the modulo operation is the remainder of the division algorithm. (Contributed by AV, 19-Aug-2021)

Ref Expression
Assertion modremain ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( ( 𝑁 mod 𝐷 ) = 𝑅 ↔ ∃ 𝑧 ∈ ℤ ( ( 𝑧 · 𝐷 ) + 𝑅 ) = 𝑁 ) )

Proof

Step Hyp Ref Expression
1 eqcom ( ( 𝑁 mod 𝐷 ) = 𝑅𝑅 = ( 𝑁 mod 𝐷 ) )
2 divalgmodcl ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ 𝑅 ∈ ℕ0 ) → ( 𝑅 = ( 𝑁 mod 𝐷 ) ↔ ( 𝑅 < 𝐷𝐷 ∥ ( 𝑁𝑅 ) ) ) )
3 2 3adant3r ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( 𝑅 = ( 𝑁 mod 𝐷 ) ↔ ( 𝑅 < 𝐷𝐷 ∥ ( 𝑁𝑅 ) ) ) )
4 ibar ( 𝑅 < 𝐷 → ( 𝐷 ∥ ( 𝑁𝑅 ) ↔ ( 𝑅 < 𝐷𝐷 ∥ ( 𝑁𝑅 ) ) ) )
5 4 adantl ( ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) → ( 𝐷 ∥ ( 𝑁𝑅 ) ↔ ( 𝑅 < 𝐷𝐷 ∥ ( 𝑁𝑅 ) ) ) )
6 5 3ad2ant3 ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( 𝐷 ∥ ( 𝑁𝑅 ) ↔ ( 𝑅 < 𝐷𝐷 ∥ ( 𝑁𝑅 ) ) ) )
7 nnz ( 𝐷 ∈ ℕ → 𝐷 ∈ ℤ )
8 7 3ad2ant2 ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → 𝐷 ∈ ℤ )
9 simp1 ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → 𝑁 ∈ ℤ )
10 nn0z ( 𝑅 ∈ ℕ0𝑅 ∈ ℤ )
11 10 adantr ( ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) → 𝑅 ∈ ℤ )
12 11 3ad2ant3 ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → 𝑅 ∈ ℤ )
13 9 12 zsubcld ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( 𝑁𝑅 ) ∈ ℤ )
14 divides ( ( 𝐷 ∈ ℤ ∧ ( 𝑁𝑅 ) ∈ ℤ ) → ( 𝐷 ∥ ( 𝑁𝑅 ) ↔ ∃ 𝑧 ∈ ℤ ( 𝑧 · 𝐷 ) = ( 𝑁𝑅 ) ) )
15 8 13 14 syl2anc ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( 𝐷 ∥ ( 𝑁𝑅 ) ↔ ∃ 𝑧 ∈ ℤ ( 𝑧 · 𝐷 ) = ( 𝑁𝑅 ) ) )
16 eqcom ( ( 𝑧 · 𝐷 ) = ( 𝑁𝑅 ) ↔ ( 𝑁𝑅 ) = ( 𝑧 · 𝐷 ) )
17 zcn ( 𝑁 ∈ ℤ → 𝑁 ∈ ℂ )
18 17 3ad2ant1 ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → 𝑁 ∈ ℂ )
19 18 adantr ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → 𝑁 ∈ ℂ )
20 nn0cn ( 𝑅 ∈ ℕ0𝑅 ∈ ℂ )
21 20 adantr ( ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) → 𝑅 ∈ ℂ )
22 21 3ad2ant3 ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → 𝑅 ∈ ℂ )
23 22 adantr ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → 𝑅 ∈ ℂ )
24 simpr ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → 𝑧 ∈ ℤ )
25 8 adantr ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → 𝐷 ∈ ℤ )
26 24 25 zmulcld ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → ( 𝑧 · 𝐷 ) ∈ ℤ )
27 26 zcnd ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → ( 𝑧 · 𝐷 ) ∈ ℂ )
28 19 23 27 subadd2d ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → ( ( 𝑁𝑅 ) = ( 𝑧 · 𝐷 ) ↔ ( ( 𝑧 · 𝐷 ) + 𝑅 ) = 𝑁 ) )
29 16 28 syl5bb ( ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) ∧ 𝑧 ∈ ℤ ) → ( ( 𝑧 · 𝐷 ) = ( 𝑁𝑅 ) ↔ ( ( 𝑧 · 𝐷 ) + 𝑅 ) = 𝑁 ) )
30 29 rexbidva ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( ∃ 𝑧 ∈ ℤ ( 𝑧 · 𝐷 ) = ( 𝑁𝑅 ) ↔ ∃ 𝑧 ∈ ℤ ( ( 𝑧 · 𝐷 ) + 𝑅 ) = 𝑁 ) )
31 15 30 bitrd ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( 𝐷 ∥ ( 𝑁𝑅 ) ↔ ∃ 𝑧 ∈ ℤ ( ( 𝑧 · 𝐷 ) + 𝑅 ) = 𝑁 ) )
32 3 6 31 3bitr2d ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( 𝑅 = ( 𝑁 mod 𝐷 ) ↔ ∃ 𝑧 ∈ ℤ ( ( 𝑧 · 𝐷 ) + 𝑅 ) = 𝑁 ) )
33 1 32 syl5bb ( ( 𝑁 ∈ ℤ ∧ 𝐷 ∈ ℕ ∧ ( 𝑅 ∈ ℕ0𝑅 < 𝐷 ) ) → ( ( 𝑁 mod 𝐷 ) = 𝑅 ↔ ∃ 𝑧 ∈ ℤ ( ( 𝑧 · 𝐷 ) + 𝑅 ) = 𝑁 ) )