Proof of Theorem bitsinv1lem
Step | Hyp | Ref
| Expression |
1 | | oveq2 6658 |
. . 3
⊢
((2↑𝑀) =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑𝑀)) + (2↑𝑀)) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0))) |
2 | 1 | eqeq2d 2632 |
. 2
⊢
((2↑𝑀) =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + (2↑𝑀)) ↔ (𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0)))) |
3 | | oveq2 6658 |
. . 3
⊢ (0 =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑𝑀)) + 0) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0))) |
4 | 3 | eqeq2d 2632 |
. 2
⊢ (0 =
if(𝑀 ∈
(bits‘𝑁),
(2↑𝑀), 0) →
((𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + 0) ↔ (𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0)))) |
5 | | simpl 473 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑁 ∈
ℤ) |
6 | | 2nn 11185 |
. . . . . . . . 9
⊢ 2 ∈
ℕ |
7 | 6 | a1i 11 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℕ) |
8 | | simpr 477 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑀 ∈
ℕ0) |
9 | 7, 8 | nnexpcld 13030 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℕ) |
10 | 5, 9 | zmodcld 12691 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) ∈
ℕ0) |
11 | 10 | nn0cnd 11353 |
. . . . 5
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) ∈
ℂ) |
12 | 11 | adantr 481 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑𝑀)) ∈
ℂ) |
13 | | 1nn0 11308 |
. . . . . . . . . 10
⊢ 1 ∈
ℕ0 |
14 | 13 | a1i 11 |
. . . . . . . . 9
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 1 ∈ ℕ0) |
15 | 8, 14 | nn0addcld 11355 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 + 1) ∈
ℕ0) |
16 | 7, 15 | nnexpcld 13030 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℕ) |
17 | 5, 16 | zmodcld 12691 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) ∈
ℕ0) |
18 | 17 | nn0cnd 11353 |
. . . . 5
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) ∈
ℂ) |
19 | 18 | adantr 481 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) ∈
ℂ) |
20 | 12, 19 | pncan3d 10395 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑𝑀)) + ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) = (𝑁 mod (2↑(𝑀 + 1)))) |
21 | 18, 11 | subcld 10392 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) ∈
ℂ) |
22 | 21 | adantr 481 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ∈ ℂ) |
23 | 6 | a1i 11 |
. . . . . . 7
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) → 2
∈ ℕ) |
24 | | simplr 792 |
. . . . . . 7
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
𝑀 ∈
ℕ0) |
25 | 23, 24 | nnexpcld 13030 |
. . . . . 6
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ∈
ℕ) |
26 | 25 | nncnd 11036 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ∈
ℂ) |
27 | | 2cnd 11093 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℂ) |
28 | | 2ne0 11113 |
. . . . . . . 8
⊢ 2 ≠
0 |
29 | 28 | a1i 11 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ≠ 0) |
30 | 8 | nn0zd 11480 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑀 ∈
ℤ) |
31 | 27, 29, 30 | expne0d 13014 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ≠
0) |
32 | 31 | adantr 481 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ≠
0) |
33 | | 2z 11409 |
. . . . . . . . . . 11
⊢ 2 ∈
ℤ |
34 | | dvds0 14997 |
. . . . . . . . . . 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 4691 |
. . . . . . . . 9
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
38 | | bitsval2 15147 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) ↔ ¬
2 ∥ (⌊‘(𝑁
/ (2↑𝑀))))) |
39 | 5 | zred 11482 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑁 ∈
ℝ) |
40 | 9 | nnrpd 11870 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℝ+) |
41 | | moddiffl 12681 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = (⌊‘(𝑁 / (2↑𝑀)))) |
42 | 39, 40, 41 | syl2anc 693 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = (⌊‘(𝑁 / (2↑𝑀)))) |
43 | 42 | breq2d 4665 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ ((𝑁
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) ↔ 2
∥ (⌊‘(𝑁 /
(2↑𝑀))))) |
44 | 33 | a1i 11 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℤ) |
45 | | moddifz 12682 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ) |
46 | 39, 40, 45 | syl2anc 693 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ) |
47 | 5 | zcnd 11483 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 𝑁 ∈
ℂ) |
48 | 47, 11, 18 | nnncan1d 10426 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) − (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) = ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
49 | 48 | oveq1d 6665 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) / (2↑𝑀)) = (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
50 | 47, 11 | subcld 10392 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 − (𝑁 mod (2↑𝑀))) ∈ ℂ) |
51 | 47, 18 | subcld 10392 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) ∈ ℂ) |
52 | 9 | nncnd 11036 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℂ) |
53 | 50, 51, 52, 31 | divsubdird 10840 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)))) |
54 | 49, 53 | eqtr3d 2658 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)))) |
55 | 27, 51 | mulcomd 10061 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 · (𝑁
− (𝑁 mod
(2↑(𝑀 + 1))))) =
((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) · 2)) |
56 | 27, 52 | mulcomd 10061 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 · (2↑𝑀)) = ((2↑𝑀) · 2)) |
57 | 27, 8 | expp1d 13009 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1)) =
((2↑𝑀) ·
2)) |
58 | 56, 57 | eqtr4d 2659 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 · (2↑𝑀)) = (2↑(𝑀 + 1))) |
59 | 55, 58 | oveq12d 6668 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((2 · (𝑁
− (𝑁 mod
(2↑(𝑀 + 1))))) / (2
· (2↑𝑀))) =
(((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) · 2) / (2↑(𝑀 + 1)))) |
60 | 51, 52, 27, 31, 29 | divcan5d 10827 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((2 · (𝑁
− (𝑁 mod
(2↑(𝑀 + 1))))) / (2
· (2↑𝑀))) =
((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀))) |
61 | 16 | nncnd 11036 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℂ) |
62 | 30 | peano2zd 11485 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 + 1) ∈
ℤ) |
63 | 27, 29, 62 | expne0d 13014 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
≠ 0) |
64 | 51, 27, 61, 63 | div23d 10838 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) · 2) / (2↑(𝑀 + 1))) = (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
65 | 59, 60, 64 | 3eqtr3d 2664 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
66 | 16 | nnrpd 11870 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℝ+) |
67 | | moddifz 12682 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℝ ∧
(2↑(𝑀 + 1)) ∈
ℝ+) → ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) ∈ ℤ) |
68 | 39, 66, 67 | syl2anc 693 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) ∈ ℤ) |
69 | 68, 44 | zmulcld 11488 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2) ∈
ℤ) |
70 | 65, 69 | eqeltrd 2701 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀)) ∈ ℤ) |
71 | 46, 70 | zsubcld 11487 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀))) ∈ ℤ) |
72 | 54, 71 | eqeltrd 2701 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ ℤ) |
73 | | dvdsmul2 15004 |
. . . . . . . . . . . . . . . 16
⊢ ((((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) ∈ ℤ ∧ 2 ∈
ℤ) → 2 ∥ (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
74 | 68, 44, 73 | syl2anc 693 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∥ (((𝑁
− (𝑁 mod
(2↑(𝑀 + 1)))) /
(2↑(𝑀 + 1))) ·
2)) |
75 | 47, 18, 11 | nnncan2d 10427 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 − (𝑁 mod (2↑𝑀))) − ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) = (𝑁 − (𝑁 mod (2↑(𝑀 + 1))))) |
76 | 75 | oveq1d 6665 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) / (2↑𝑀)) = ((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑𝑀))) |
77 | 50, 21, 52, 31 | divsubdird 10840 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) − ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) / (2↑𝑀)) = (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
78 | 76, 77, 65 | 3eqtr3d 2664 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) − (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) = (((𝑁 − (𝑁 mod (2↑(𝑀 + 1)))) / (2↑(𝑀 + 1))) · 2)) |
79 | 74, 78 | breqtrrd 4681 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∥ (((𝑁
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) −
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
80 | | dvdssub2 15023 |
. . . . . . . . . . . . . 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 1329 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ ((𝑁
− (𝑁 mod
(2↑𝑀))) /
(2↑𝑀)) ↔ 2
∥ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
82 | 43, 81 | bitr3d 270 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ (⌊‘(𝑁 / (2↑𝑀))) ↔ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
83 | 82 | notbid 308 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ 2 ∥ (⌊‘(𝑁 / (2↑𝑀))) ↔ ¬ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
84 | 38, 83 | bitrd 268 |
. . . . . . . . . 10
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) ↔ ¬
2 ∥ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
85 | 84 | con2bid 344 |
. . . . . . . . 9
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2 ∥ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ ¬ 𝑀 ∈ (bits‘𝑁))) |
86 | 37, 85 | syl5ib 234 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → ¬ 𝑀 ∈ (bits‘𝑁))) |
87 | 86 | con2d 129 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) → ¬
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0)) |
88 | | df-neg 10269 |
. . . . . . . . . . . . . . 15
⊢ -1 = (0
− 1) |
89 | 52 | mulm1d 10482 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (-1 · (2↑𝑀)) = -(2↑𝑀)) |
90 | 9 | nnred 11035 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑𝑀) ∈
ℝ) |
91 | 90 | renegcld 10457 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(2↑𝑀) ∈
ℝ) |
92 | 39, 40 | modcld 12674 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) ∈
ℝ) |
93 | 92 | renegcld 10457 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(𝑁 mod
(2↑𝑀)) ∈
ℝ) |
94 | 39, 66 | modcld 12674 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) ∈
ℝ) |
95 | 94, 92 | resubcld 10458 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) ∈
ℝ) |
96 | | modlt 12679 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → (𝑁 mod (2↑𝑀)) < (2↑𝑀)) |
97 | 39, 40, 96 | syl2anc 693 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod (2↑𝑀)) < (2↑𝑀)) |
98 | 92, 90 | ltnegd 10605 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑𝑀)) <
(2↑𝑀) ↔
-(2↑𝑀) < -(𝑁 mod (2↑𝑀)))) |
99 | 97, 98 | mpbid 222 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(2↑𝑀) <
-(𝑁 mod (2↑𝑀))) |
100 | | df-neg 10269 |
. . . . . . . . . . . . . . . . . . 19
⊢ -(𝑁 mod (2↑𝑀)) = (0 − (𝑁 mod (2↑𝑀))) |
101 | | 0red 10041 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ∈ ℝ) |
102 | | modge0 12678 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ ((𝑁 ∈ ℝ ∧
(2↑(𝑀 + 1)) ∈
ℝ+) → 0 ≤ (𝑁 mod (2↑(𝑀 + 1)))) |
103 | 39, 66, 102 | syl2anc 693 |
. . . . . . . . . . . . . . . . . . . 20
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ≤ (𝑁 mod
(2↑(𝑀 +
1)))) |
104 | 101, 94, 92, 103 | lesub1dd 10643 |
. . . . . . . . . . . . . . . . . . 19
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 − (𝑁 mod
(2↑𝑀))) ≤ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
105 | 100, 104 | syl5eqbr 4688 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(𝑁 mod
(2↑𝑀)) ≤ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
106 | 91, 93, 95, 99, 105 | ltletrd 10197 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -(2↑𝑀) <
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
107 | 89, 106 | eqbrtrd 4675 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (-1 · (2↑𝑀)) < ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) |
108 | | 1red 10055 |
. . . . . . . . . . . . . . . . . 18
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 1 ∈ ℝ) |
109 | 108 | renegcld 10457 |
. . . . . . . . . . . . . . . . 17
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -1 ∈ ℝ) |
110 | 109, 95, 40 | ltmuldivd 11919 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((-1 · (2↑𝑀)) < ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ↔ -1 < (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
111 | 107, 110 | mpbid 222 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ -1 < (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
112 | 88, 111 | syl5eqbrr 4689 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 − 1) < (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
113 | | 0zd 11389 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ∈ ℤ) |
114 | | zlem1lt 11429 |
. . . . . . . . . . . . . . 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 693 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 ≤ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ (0 − 1) < (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
116 | 112, 115 | mpbird 247 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ≤ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
117 | | elnn0z 11390 |
. . . . . . . . . . . . 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 698 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈
ℕ0) |
119 | | nn0uz 11722 |
. . . . . . . . . . . 12
⊢
ℕ0 = (ℤ≥‘0) |
120 | 118, 119 | syl6eleq 2711 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈
(ℤ≥‘0)) |
121 | 16 | nnred 11035 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (2↑(𝑀 + 1))
∈ ℝ) |
122 | | modge0 12678 |
. . . . . . . . . . . . . . . 16
⊢ ((𝑁 ∈ ℝ ∧
(2↑𝑀) ∈
ℝ+) → 0 ≤ (𝑁 mod (2↑𝑀))) |
123 | 39, 40, 122 | syl2anc 693 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 0 ≤ (𝑁 mod
(2↑𝑀))) |
124 | 94, 92 | subge02d 10619 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (0 ≤ (𝑁 mod
(2↑𝑀)) ↔ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ≤ (𝑁 mod (2↑(𝑀 + 1))))) |
125 | 123, 124 | mpbid 222 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) ≤ (𝑁 mod (2↑(𝑀 + 1)))) |
126 | | modlt 12679 |
. . . . . . . . . . . . . . 15
⊢ ((𝑁 ∈ ℝ ∧
(2↑(𝑀 + 1)) ∈
ℝ+) → (𝑁 mod (2↑(𝑀 + 1))) < (2↑(𝑀 + 1))) |
127 | 39, 66, 126 | syl2anc 693 |
. . . . . . . . . . . . . 14
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) <
(2↑(𝑀 +
1))) |
128 | 95, 94, 121, 125, 127 | lelttrd 10195 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) < (2↑(𝑀 + 1))) |
129 | 128, 57 | breqtrd 4679 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) < ((2↑𝑀) · 2)) |
130 | 7 | nnred 11035 |
. . . . . . . . . . . . 13
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ 2 ∈ ℝ) |
131 | 95, 130, 40 | ltdivmuld 11923 |
. . . . . . . . . . . 12
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ ((((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) < 2 ↔ ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) < ((2↑𝑀) · 2))) |
132 | 129, 131 | mpbird 247 |
. . . . . . . . . . 11
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) < 2) |
133 | | elfzo2 12473 |
. . . . . . . . . . 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 1246 |
. . . . . . . . . 10
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ (0..^2)) |
135 | | fzo0to2pr 12553 |
. . . . . . . . . 10
⊢ (0..^2) =
{0, 1} |
136 | 134, 135 | syl6eleq 2711 |
. . . . . . . . 9
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) ∈ {0, 1}) |
137 | | elpri 4197 |
. . . . . . . . 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 392 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1)) |
140 | 87, 139 | syld 47 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑀 ∈
(bits‘𝑁) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1)) |
141 | 140 | imp 445 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1) |
142 | 22, 26, 32, 141 | diveq1d 10809 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) = (2↑𝑀)) |
143 | 142 | oveq2d 6666 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑𝑀)) + ((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀)))) = ((𝑁 mod (2↑𝑀)) + (2↑𝑀))) |
144 | 20, 143 | eqtr3d 2658 |
. 2
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + (2↑𝑀))) |
145 | 18 | adantr 481 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) ∈
ℂ) |
146 | 11 | adantr 481 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑𝑀)) ∈
ℂ) |
147 | 21 | adantr 481 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) ∈ ℂ) |
148 | 52 | adantr 481 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ∈
ℂ) |
149 | 31 | adantr 481 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(2↑𝑀) ≠
0) |
150 | | n2dvds1 15104 |
. . . . . . . . . 10
⊢ ¬ 2
∥ 1 |
151 | | breq2 4657 |
. . . . . . . . . 10
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1 → (2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) ↔ 2 ∥ 1)) |
152 | 150, 151 | mtbiri 317 |
. . . . . . . . 9
⊢ ((((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 1 → ¬ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀))) |
153 | 139, 152 | syl6 35 |
. . . . . . . 8
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → ¬ 2 ∥ (((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)))) |
154 | 153, 84 | sylibrd 249 |
. . . . . . 7
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ (((𝑁 mod
(2↑(𝑀 + 1))) −
(𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0 → 𝑀 ∈ (bits‘𝑁))) |
155 | 154 | con1d 139 |
. . . . . 6
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (¬ 𝑀 ∈
(bits‘𝑁) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0)) |
156 | 155 | imp 445 |
. . . . 5
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) / (2↑𝑀)) = 0) |
157 | 147, 148,
149, 156 | diveq0d 10808 |
. . . 4
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑(𝑀 + 1))) − (𝑁 mod (2↑𝑀))) = 0) |
158 | 145, 146,
157 | subeq0d 10400 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) = (𝑁 mod (2↑𝑀))) |
159 | 146 | addid1d 10236 |
. . 3
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
((𝑁 mod (2↑𝑀)) + 0) = (𝑁 mod (2↑𝑀))) |
160 | 158, 159 | eqtr4d 2659 |
. 2
⊢ (((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
∧ ¬ 𝑀 ∈
(bits‘𝑁)) →
(𝑁 mod (2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + 0)) |
161 | 2, 4, 144, 160 | ifbothda 4123 |
1
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℕ0)
→ (𝑁 mod
(2↑(𝑀 + 1))) = ((𝑁 mod (2↑𝑀)) + if(𝑀 ∈ (bits‘𝑁), (2↑𝑀), 0))) |