![]() |
Intuitionistic Logic Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > ILE Home > Th. List > divides | GIF version |
Description: Define the divides relation. 𝑀 ∥ 𝑁 means 𝑀 divides into 𝑁 with no remainder. For example, 3 ∥ 6 (ex-dvds 14753). As proven in dvdsval3 11811, 𝑀 ∥ 𝑁 ↔ (𝑁 mod 𝑀) = 0. See divides 11809 and dvdsval2 11810 for other equivalent expressions. (Contributed by Paul Chapman, 21-Mar-2011.) |
Ref | Expression |
---|---|
divides | ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | df-br 4016 | . . 3 ⊢ (𝑀 ∥ 𝑁 ↔ 〈𝑀, 𝑁〉 ∈ ∥ ) | |
2 | df-dvds 11808 | . . . 4 ⊢ ∥ = {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)} | |
3 | 2 | eleq2i 2254 | . . 3 ⊢ (〈𝑀, 𝑁〉 ∈ ∥ ↔ 〈𝑀, 𝑁〉 ∈ {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)}) |
4 | 1, 3 | bitri 184 | . 2 ⊢ (𝑀 ∥ 𝑁 ↔ 〈𝑀, 𝑁〉 ∈ {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)}) |
5 | oveq2 5896 | . . . . 5 ⊢ (𝑥 = 𝑀 → (𝑛 · 𝑥) = (𝑛 · 𝑀)) | |
6 | 5 | eqeq1d 2196 | . . . 4 ⊢ (𝑥 = 𝑀 → ((𝑛 · 𝑥) = 𝑦 ↔ (𝑛 · 𝑀) = 𝑦)) |
7 | 6 | rexbidv 2488 | . . 3 ⊢ (𝑥 = 𝑀 → (∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑦)) |
8 | eqeq2 2197 | . . . 4 ⊢ (𝑦 = 𝑁 → ((𝑛 · 𝑀) = 𝑦 ↔ (𝑛 · 𝑀) = 𝑁)) | |
9 | 8 | rexbidv 2488 | . . 3 ⊢ (𝑦 = 𝑁 → (∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑦 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
10 | 7, 9 | opelopab2 4282 | . 2 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (〈𝑀, 𝑁〉 ∈ {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)} ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
11 | 4, 10 | bitrid 192 | 1 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
Colors of variables: wff set class |
Syntax hints: → wi 4 ∧ wa 104 ↔ wb 105 = wceq 1363 ∈ wcel 2158 ∃wrex 2466 〈cop 3607 class class class wbr 4015 {copab 4075 (class class class)co 5888 · cmul 7829 ℤcz 9266 ∥ cdvds 11807 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 106 ax-ia2 107 ax-ia3 108 ax-io 710 ax-5 1457 ax-7 1458 ax-gen 1459 ax-ie1 1503 ax-ie2 1504 ax-8 1514 ax-10 1515 ax-11 1516 ax-i12 1517 ax-bndl 1519 ax-4 1520 ax-17 1536 ax-i9 1540 ax-ial 1544 ax-i5r 1545 ax-14 2161 ax-ext 2169 ax-sep 4133 ax-pow 4186 ax-pr 4221 |
This theorem depends on definitions: df-bi 117 df-3an 981 df-tru 1366 df-nf 1471 df-sb 1773 df-eu 2039 df-mo 2040 df-clab 2174 df-cleq 2180 df-clel 2183 df-nfc 2318 df-rex 2471 df-v 2751 df-un 3145 df-in 3147 df-ss 3154 df-pw 3589 df-sn 3610 df-pr 3611 df-op 3613 df-uni 3822 df-br 4016 df-opab 4077 df-iota 5190 df-fv 5236 df-ov 5891 df-dvds 11808 |
This theorem is referenced by: dvdsval2 11810 dvds0lem 11821 dvds1lem 11822 dvds2lem 11823 0dvds 11831 dvdsle 11863 divconjdvds 11868 odd2np1 11891 even2n 11892 oddm1even 11893 opeo 11915 omeo 11916 m1exp1 11919 divalgb 11943 modremain 11947 zeqzmulgcd 11984 gcddiv 12033 dvdssqim 12038 coprmdvds2 12106 congr 12113 divgcdcoprm0 12114 cncongr2 12117 dvdsnprmd 12138 prmpwdvds 12366 |
Copyright terms: Public domain | W3C validator |