Proof of Theorem bitsinv1lem
Step | Hyp | Ref
| Expression |
1 | | oveq2 6557 |
. . 3
⊢
((2↑𝑀) =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑𝑀)) + (2↑𝑀)) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0))) |
2 | 1 | eqeq2d 2620 |
. 2
⊢
((2↑𝑀) =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + (2↑𝑀)) ↔ (𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0)))) |
3 | | oveq2 6557 |
. . 3
⊢ (0 =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑𝑀)) + 0) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0))) |
4 | 3 | eqeq2d 2620 |
. 2
⊢ (0 =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + 0) ↔ (𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0)))) |
5 | | simpl 472 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑁 ∈
ℤ) |
6 | | 2nn 11062 |
. . . . . . . . 9
⊢ 2 ∈
ℕ |
7 | 6 | a1i 11 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℕ) |
8 | | simpr 476 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑀 ∈
ℕ0) |
9 | 7, 8 | nnexpcld 12892 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℕ) |
10 | 5, 9 | zmodcld 12553 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) ∈
ℕ0) |
11 | 10 | nn0cnd 11230 |
. . . . 5
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) ∈
ℂ) |
12 | 11 | adantr 480 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑𝑀)) ∈
ℂ) |
13 | | 1nn0 11185 |
. . . . . . . . . 10
⊢ 1 ∈
ℕ0 |
14 | 13 | a1i 11 |
. . . . . . . . 9
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 1 ∈ ℕ0) |
15 | 8, 14 | nn0addcld 11232 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 + 1) ∈
ℕ0) |
16 | 7, 15 | nnexpcld 12892 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℕ) |
17 | 5, 16 | zmodcld 12553 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) ∈
ℕ0) |
18 | 17 | nn0cnd 11230 |
. . . . 5
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) ∈
ℂ) |
19 | 18 | adantr 480 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) ∈
ℂ) |
20 | 12, 19 | pncan3d 10274 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑𝑀)) + ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) = (𝑁 mod (2↑(𝑀 + 1)))) |
21 | 18, 11 | subcld 10271 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) ∈
ℂ) |
22 | 21 | adantr 480 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ∈ ℂ) |
23 | 6 | a1i 11 |
. . . . . . 7
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) → 2
∈ ℕ) |
24 | | simplr 788 |
. . . . . . 7
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
𝑀 ∈
ℕ0) |
25 | 23, 24 | nnexpcld 12892 |
. . . . . 6
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ∈
ℕ) |
26 | 25 | nncnd 10913 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ∈
ℂ) |
27 | | 2cnd 10970 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℂ) |
28 | | 2ne0 10990 |
. . . . . . . 8
⊢ 2 ≠
0 |
29 | 28 | a1i 11 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ≠ 0) |
30 | 8 | nn0zd 11356 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑀 ∈
ℤ) |
31 | 27, 29, 30 | expne0d 12876 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ≠
0) |
32 | 31 | adantr 480 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ≠
0) |
33 | | 2z 11286 |
. . . . . . . . . . 11
⊢ 2 ∈
ℤ |
34 | | dvds0 14835 |
. . . . . . . . . . 11
⊢ (2 ∈
ℤ → 2 ∥ 0) |
35 | 33, 34 | ax-mp 5 |
. . . . . . . . . 10
⊢ 2 ∥
0 |
36 | | id 22 |
. . . . . . . . . 10
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0) |
37 | 35, 36 | syl5breqr 4621 |
. . . . . . . . 9
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
38 | | bitsval2 14985 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) ↔ ¬
2 ∥ (⌊‘(𝑁
/ (2↑𝑀))))) |
39 | 5 | zred 11358 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑁 ∈
ℝ) |
40 | 9 | nnrpd 11746 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℝ+) |
41 | | moddiffl 12543 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = (⌊‘(𝑁 / (2↑𝑀)))) |
42 | 39, 40, 41 | syl2anc 691 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = (⌊‘(𝑁 / (2↑𝑀)))) |
43 | 42 | breq2d 4595 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ ((𝑁
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) ↔ 2
∥ (⌊‘(𝑁 /
(2↑𝑀))))) |
44 | 33 | a1i 11 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℤ) |
45 | | moddifz 12544 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ) |
46 | 39, 40, 45 | syl2anc 691 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ) |
47 | 5 | zcnd 11359 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑁 ∈
ℂ) |
48 | 47, 11, 18 | nnncan1d 10305 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) − (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) = ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
49 | 48 | oveq1d 6564 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) / (2↑𝑀)) = (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
50 | 47, 11 | subcld 10271 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 − (𝑁 mod (2↑𝑀))) ∈ ℂ) |
51 | 47, 18 | subcld 10271 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) ∈ ℂ) |
52 | 9 | nncnd 10913 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℂ) |
53 | 50, 51, 52, 31 | divsubdird 10719 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)))) |
54 | 49, 53 | eqtr3d 2646 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)))) |
55 | 27, 51 | mulcomd 9940 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 · (𝑁
− (𝑁 mod
(2↑(𝑀 + 1))))) =
((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) · 2)) |
56 | 27, 52 | mulcomd 9940 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 · (2↑𝑀)) = ((2↑𝑀) · 2)) |
57 | 27, 8 | expp1d 12871 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1)) =
((2↑𝑀) ·
2)) |
58 | 56, 57 | eqtr4d 2647 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 · (2↑𝑀)) = (2↑(𝑀 + 1))) |
59 | 55, 58 | oveq12d 6567 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((2 · (𝑁
− (𝑁 mod
(2↑(𝑀 + 1))))) / (2
· (2↑𝑀))) =
(((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) · 2) / (2↑(𝑀 + 1)))) |
60 | 51, 52, 27, 31, 29 | divcan5d 10706 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((2 · (𝑁
− (𝑁 mod
(2↑(𝑀 + 1))))) / (2
· (2↑𝑀))) =
((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀))) |
61 | 16 | nncnd 10913 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℂ) |
62 | 30 | peano2zd 11361 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 + 1) ∈
ℤ) |
63 | 27, 29, 62 | expne0d 12876 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
≠ 0) |
64 | 51, 27, 61, 63 | div23d 10717 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) · 2) / (2↑(𝑀 + 1))) = (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
65 | 59, 60, 64 | 3eqtr3d 2652 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
66 | 16 | nnrpd 11746 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℝ+) |
67 | | moddifz 12544 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℝ ∧
(2↑(𝑀 + 1)) ∈
ℝ+) → ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) ∈ ℤ) |
68 | 39, 66, 67 | syl2anc 691 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) ∈ ℤ) |
69 | 68, 44 | zmulcld 11364 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2) ∈
ℤ) |
70 | 65, 69 | eqeltrd 2688 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)) ∈ ℤ) |
71 | 46, 70 | zsubcld 11363 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀))) ∈ ℤ) |
72 | 54, 71 | eqeltrd 2688 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ) |
73 | | dvdsmul2 14842 |
. . . . . . . . . . . . . . . 16
⊢ ((((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) ∈ ℤ ∧ 2 ∈
ℤ) → 2 ∥ (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
74 | 68, 44, 73 | syl2anc 691 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∥ (((𝑁
− (𝑁 mod
(2↑(𝑀 + 1)))) /
(2↑(𝑀 + 1))) ·
2)) |
75 | 47, 18, 11 | nnncan2d 10306 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) − ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) = (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) |
76 | 75 | oveq1d 6564 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) / (2↑𝑀)) = ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀))) |
77 | 50, 21, 52, 31 | divsubdird 10719 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
78 | 76, 77, 65 | 3eqtr3d 2652 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) = (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
79 | 74, 78 | breqtrrd 4611 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∥ (((𝑁
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) −
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
80 | | dvdssub2 14861 |
. . . . . . . . . . . . . 14
⊢ (((2
∈ ℤ ∧ ((𝑁
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) ∈ ℤ
∧ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ) ∧ 2 ∥ (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) → (2 ∥ ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
81 | 44, 46, 72, 79, 80 | syl31anc 1321 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ ((𝑁
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) ↔ 2
∥ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
82 | 43, 81 | bitr3d 269 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ (⌊‘(𝑁 / (2↑𝑀))) ↔ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
83 | 82 | notbid 307 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ 2 ∥ (⌊‘(𝑁 / (2↑𝑀))) ↔ ¬ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
84 | 38, 83 | bitrd 267 |
. . . . . . . . . 10
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) ↔ ¬
2 ∥ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
85 | 84 | con2bid 343 |
. . . . . . . . 9
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ ¬ 𝑀 ∈ (bits‘𝑁))) |
86 | 37, 85 | syl5ib 233 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → ¬ 𝑀 ∈ (bits‘𝑁))) |
87 | 86 | con2d 128 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) → ¬
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0)) |
88 | | df-neg 10148 |
. . . . . . . . . . . . . . 15
⊢ -1 = (0
− 1) |
89 | 52 | mulm1d 10361 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (-1 · (2↑𝑀)) = -(2↑𝑀)) |
90 | 9 | nnred 10912 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℝ) |
91 | 90 | renegcld 10336 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(2↑𝑀) ∈
ℝ) |
92 | 39, 40 | modcld 12536 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) ∈
ℝ) |
93 | 92 | renegcld 10336 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(𝑁 mod
(2↑𝑀)) ∈
ℝ) |
94 | 39, 66 | modcld 12536 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) ∈
ℝ) |
95 | 94, 92 | resubcld 10337 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) ∈
ℝ) |
96 | | modlt 12541 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → (𝑁 mod (2↑𝑀)) < (2↑𝑀)) |
97 | 39, 40, 96 | syl2anc 691 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) < (2↑𝑀)) |
98 | 92, 90 | ltnegd 10484 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑𝑀)) <
(2↑𝑀) ↔
-(2↑𝑀) < -(𝑁 mod (2↑𝑀)))) |
99 | 97, 98 | mpbid 221 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(2↑𝑀) <
-(𝑁 mod (2↑𝑀))) |
100 | | df-neg 10148 |
. . . . . . . . . . . . . . . . . . 19
⊢ -(𝑁 mod (2↑𝑀)) = (0 − (𝑁 mod (2↑𝑀))) |
101 | | 0red 9920 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ∈ ℝ) |
102 | | modge0 12540 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ ((𝑁 ∈ ℝ ∧
(2↑(𝑀 + 1)) ∈
ℝ+) → 0 ≤ (𝑁 mod (2↑(𝑀 + 1)))) |
103 | 39, 66, 102 | syl2anc 691 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ≤ (𝑁 mod
(2↑(𝑀 +
1)))) |
104 | 101, 94, 92, 103 | lesub1dd 10522 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 − (𝑁 mod
(2↑𝑀))) ≤ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
105 | 100, 104 | syl5eqbr 4618 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(𝑁 mod
(2↑𝑀)) ≤ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
106 | 91, 93, 95, 99, 105 | ltletrd 10076 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(2↑𝑀) <
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
107 | 89, 106 | eqbrtrd 4605 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (-1 · (2↑𝑀)) < ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
108 | | 1red 9934 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 1 ∈ ℝ) |
109 | 108 | renegcld 10336 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -1 ∈ ℝ) |
110 | 109, 95, 40 | ltmuldivd 11795 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((-1 · (2↑𝑀)) < ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ↔ -1 < (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
111 | 107, 110 | mpbid 221 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -1 < (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
112 | 88, 111 | syl5eqbrr 4619 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 − 1) < (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
113 | | 0zd 11266 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ∈ ℤ) |
114 | | zlem1lt 11306 |
. . . . . . . . . . . . . . 15
⊢ ((0
∈ ℤ ∧ (((𝑁
mod (2↑(𝑀 + 1)))
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) ∈ ℤ)
→ (0 ≤ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ (0 − 1) < (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
115 | 113, 72, 114 | syl2anc 691 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 ≤ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ (0 − 1) < (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
116 | 112, 115 | mpbird 246 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ≤ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
117 | | elnn0z 11267 |
. . . . . . . . . . . . 13
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℕ0 ↔
((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ ∧ 0 ≤ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
118 | 72, 116, 117 | sylanbrc 695 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈
ℕ0) |
119 | | nn0uz 11598 |
. . . . . . . . . . . 12
⊢
ℕ0 = (ℤ≥‘0) |
120 | 118, 119 | syl6eleq 2698 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈
(ℤ≥‘0)) |
121 | 16 | nnred 10912 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℝ) |
122 | | modge0 12540 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → 0 ≤ (𝑁 mod (2↑𝑀))) |
123 | 39, 40, 122 | syl2anc 691 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ≤ (𝑁 mod
(2↑𝑀))) |
124 | 94, 92 | subge02d 10498 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 ≤ (𝑁 mod
(2↑𝑀)) ↔ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ≤ (𝑁 mod (2↑(𝑀 + 1))))) |
125 | 123, 124 | mpbid 221 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) ≤ (𝑁 mod (2↑(𝑀 + 1)))) |
126 | | modlt 12541 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℝ ∧
(2↑(𝑀 + 1)) ∈
ℝ+) → (𝑁 mod (2↑(𝑀 + 1))) < (2↑(𝑀 + 1))) |
127 | 39, 66, 126 | syl2anc 691 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) <
(2↑(𝑀 +
1))) |
128 | 95, 94, 121, 125, 127 | lelttrd 10074 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) < (2↑(𝑀 + 1))) |
129 | 128, 57 | breqtrd 4609 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) < ((2↑𝑀) · 2)) |
130 | 7 | nnred 10912 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℝ) |
131 | 95, 130, 40 | ltdivmuld 11799 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) < 2 ↔ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) < ((2↑𝑀) · 2))) |
132 | 129, 131 | mpbird 246 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) < 2) |
133 | | elfzo2 12342 |
. . . . . . . . . . 11
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ (0..^2) ↔ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ (ℤ≥‘0)
∧ 2 ∈ ℤ ∧ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) < 2)) |
134 | 120, 44, 132, 133 | syl3anbrc 1239 |
. . . . . . . . . 10
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ (0..^2)) |
135 | | fzo0to2pr 12420 |
. . . . . . . . . 10
⊢ (0..^2) =
{0, 1} |
136 | 134, 135 | syl6eleq 2698 |
. . . . . . . . 9
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ {0, 1}) |
137 | | elpri 4145 |
. . . . . . . . 9
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ {0, 1} → ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 ∨ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1)) |
138 | 136, 137 | syl 17 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 ∨ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1)) |
139 | 138 | ord 391 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1)) |
140 | 87, 139 | syld 46 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1)) |
141 | 140 | imp 444 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1) |
142 | 22, 26, 32, 141 | diveq1d 10688 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) = (2↑𝑀)) |
143 | 142 | oveq2d 6565 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑𝑀)) + ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) = ((𝑁 mod (2↑𝑀)) + (2↑𝑀))) |
144 | 20, 143 | eqtr3d 2646 |
. 2
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + (2↑𝑀))) |
145 | 18 | adantr 480 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) ∈
ℂ) |
146 | 11 | adantr 480 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑𝑀)) ∈
ℂ) |
147 | 21 | adantr 480 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ∈ ℂ) |
148 | 52 | adantr 480 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ∈
ℂ) |
149 | 31 | adantr 480 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ≠
0) |
150 | | n2dvds1 14942 |
. . . . . . . . . 10
⊢ ¬ 2
∥ 1 |
151 | | breq2 4587 |
. . . . . . . . . 10
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1 → (2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ 2 ∥ 1)) |
152 | 150, 151 | mtbiri 316 |
. . . . . . . . 9
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1 → ¬ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
153 | 139, 152 | syl6 34 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → ¬ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
154 | 153, 84 | sylibrd 248 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → 𝑀 ∈ (bits‘𝑁))) |
155 | 154 | con1d 138 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ 𝑀 ∈
(bits‘𝑁) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0)) |
156 | 155 | imp 444 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0) |
157 | 147, 148,
149, 156 | diveq0d 10687 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) = 0) |
158 | 145, 146,
157 | subeq0d 10279 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) = (𝑁 mod (2↑𝑀))) |
159 | 146 | addid1d 10115 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑𝑀)) + 0) = (𝑁 mod (2↑𝑀))) |
160 | 158, 159 | eqtr4d 2647 |
. 2
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + 0)) |
161 | 2, 4, 144, 160 | ifbothda 4073 |
1
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0))) |