![]() |
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 13113). As proven in dvdsval3 11533, 𝑀 ∥ 𝑁 ↔ (𝑁 mod 𝑀) = 0. See divides 11531 and dvdsval2 11532 for other equivalent expressions. (Contributed by Paul Chapman, 21-Mar-2011.) |
Ref | Expression |
---|---|
divides | ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | df-br 3938 | . . 3 ⊢ (𝑀 ∥ 𝑁 ↔ 〈𝑀, 𝑁〉 ∈ ∥ ) | |
2 | df-dvds 11530 | . . . 4 ⊢ ∥ = {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)} | |
3 | 2 | eleq2i 2207 | . . 3 ⊢ (〈𝑀, 𝑁〉 ∈ ∥ ↔ 〈𝑀, 𝑁〉 ∈ {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)}) |
4 | 1, 3 | bitri 183 | . 2 ⊢ (𝑀 ∥ 𝑁 ↔ 〈𝑀, 𝑁〉 ∈ {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)}) |
5 | oveq2 5790 | . . . . 5 ⊢ (𝑥 = 𝑀 → (𝑛 · 𝑥) = (𝑛 · 𝑀)) | |
6 | 5 | eqeq1d 2149 | . . . 4 ⊢ (𝑥 = 𝑀 → ((𝑛 · 𝑥) = 𝑦 ↔ (𝑛 · 𝑀) = 𝑦)) |
7 | 6 | rexbidv 2439 | . . 3 ⊢ (𝑥 = 𝑀 → (∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑦)) |
8 | eqeq2 2150 | . . . 4 ⊢ (𝑦 = 𝑁 → ((𝑛 · 𝑀) = 𝑦 ↔ (𝑛 · 𝑀) = 𝑁)) | |
9 | 8 | rexbidv 2439 | . . 3 ⊢ (𝑦 = 𝑁 → (∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑦 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
10 | 7, 9 | opelopab2 4200 | . 2 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (〈𝑀, 𝑁〉 ∈ {〈𝑥, 𝑦〉 ∣ ((𝑥 ∈ ℤ ∧ 𝑦 ∈ ℤ) ∧ ∃𝑛 ∈ ℤ (𝑛 · 𝑥) = 𝑦)} ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
11 | 4, 10 | syl5bb 191 | 1 ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ 𝑁 ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = 𝑁)) |
Colors of variables: wff set class |
Syntax hints: → wi 4 ∧ wa 103 ↔ wb 104 = wceq 1332 ∈ wcel 1481 ∃wrex 2418 〈cop 3535 class class class wbr 3937 {copab 3996 (class class class)co 5782 · cmul 7649 ℤcz 9078 ∥ cdvds 11529 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 105 ax-ia2 106 ax-ia3 107 ax-io 699 ax-5 1424 ax-7 1425 ax-gen 1426 ax-ie1 1470 ax-ie2 1471 ax-8 1483 ax-10 1484 ax-11 1485 ax-i12 1486 ax-bndl 1487 ax-4 1488 ax-14 1493 ax-17 1507 ax-i9 1511 ax-ial 1515 ax-i5r 1516 ax-ext 2122 ax-sep 4054 ax-pow 4106 ax-pr 4139 |
This theorem depends on definitions: df-bi 116 df-3an 965 df-tru 1335 df-nf 1438 df-sb 1737 df-eu 2003 df-mo 2004 df-clab 2127 df-cleq 2133 df-clel 2136 df-nfc 2271 df-rex 2423 df-v 2691 df-un 3080 df-in 3082 df-ss 3089 df-pw 3517 df-sn 3538 df-pr 3539 df-op 3541 df-uni 3745 df-br 3938 df-opab 3998 df-iota 5096 df-fv 5139 df-ov 5785 df-dvds 11530 |
This theorem is referenced by: dvdsval2 11532 dvds0lem 11539 dvds1lem 11540 dvds2lem 11541 0dvds 11549 dvdsle 11578 divconjdvds 11583 odd2np1 11606 even2n 11607 oddm1even 11608 opeo 11630 omeo 11631 m1exp1 11634 divalgb 11658 modremain 11662 zeqzmulgcd 11695 gcddiv 11743 dvdssqim 11748 coprmdvds2 11810 congr 11817 divgcdcoprm0 11818 cncongr2 11821 dvdsnprmd 11842 |
Copyright terms: Public domain | W3C validator |