Step |
Hyp |
Ref |
Expression |
1 |
|
sadaddlem.c |
⊢ 𝐶 = seq 0 ( ( 𝑐 ∈ 2o , 𝑚 ∈ ℕ0 ↦ if ( cadd ( 𝑚 ∈ ( bits ‘ 𝐴 ) , 𝑚 ∈ ( bits ‘ 𝐵 ) , ∅ ∈ 𝑐 ) , 1o , ∅ ) ) , ( 𝑛 ∈ ℕ0 ↦ if ( 𝑛 = 0 , ∅ , ( 𝑛 − 1 ) ) ) ) |
2 |
|
sadaddlem.k |
⊢ 𝐾 = ◡ ( bits ↾ ℕ0 ) |
3 |
|
sadaddlem.1 |
⊢ ( 𝜑 → 𝐴 ∈ ℤ ) |
4 |
|
sadaddlem.2 |
⊢ ( 𝜑 → 𝐵 ∈ ℤ ) |
5 |
|
sadaddlem.3 |
⊢ ( 𝜑 → 𝑁 ∈ ℕ0 ) |
6 |
|
2nn |
⊢ 2 ∈ ℕ |
7 |
6
|
a1i |
⊢ ( 𝜑 → 2 ∈ ℕ ) |
8 |
7 5
|
nnexpcld |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ∈ ℕ ) |
9 |
8
|
nnzd |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ∈ ℤ ) |
10 |
|
inss1 |
⊢ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( bits ‘ 𝐴 ) |
11 |
|
bitsss |
⊢ ( bits ‘ 𝐴 ) ⊆ ℕ0 |
12 |
10 11
|
sstri |
⊢ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ℕ0 |
13 |
|
fzofi |
⊢ ( 0 ..^ 𝑁 ) ∈ Fin |
14 |
|
inss2 |
⊢ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( 0 ..^ 𝑁 ) |
15 |
|
ssfi |
⊢ ( ( ( 0 ..^ 𝑁 ) ∈ Fin ∧ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( 0 ..^ 𝑁 ) ) → ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin ) |
16 |
13 14 15
|
mp2an |
⊢ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin |
17 |
|
elfpw |
⊢ ( ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) ↔ ( ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ℕ0 ∧ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin ) ) |
18 |
12 16 17
|
mpbir2an |
⊢ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) |
19 |
|
bitsf1o |
⊢ ( bits ↾ ℕ0 ) : ℕ0 –1-1-onto→ ( 𝒫 ℕ0 ∩ Fin ) |
20 |
|
f1ocnv |
⊢ ( ( bits ↾ ℕ0 ) : ℕ0 –1-1-onto→ ( 𝒫 ℕ0 ∩ Fin ) → ◡ ( bits ↾ ℕ0 ) : ( 𝒫 ℕ0 ∩ Fin ) –1-1-onto→ ℕ0 ) |
21 |
|
f1of |
⊢ ( ◡ ( bits ↾ ℕ0 ) : ( 𝒫 ℕ0 ∩ Fin ) –1-1-onto→ ℕ0 → ◡ ( bits ↾ ℕ0 ) : ( 𝒫 ℕ0 ∩ Fin ) ⟶ ℕ0 ) |
22 |
19 20 21
|
mp2b |
⊢ ◡ ( bits ↾ ℕ0 ) : ( 𝒫 ℕ0 ∩ Fin ) ⟶ ℕ0 |
23 |
2
|
feq1i |
⊢ ( 𝐾 : ( 𝒫 ℕ0 ∩ Fin ) ⟶ ℕ0 ↔ ◡ ( bits ↾ ℕ0 ) : ( 𝒫 ℕ0 ∩ Fin ) ⟶ ℕ0 ) |
24 |
22 23
|
mpbir |
⊢ 𝐾 : ( 𝒫 ℕ0 ∩ Fin ) ⟶ ℕ0 |
25 |
24
|
ffvelrni |
⊢ ( ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) → ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℕ0 ) |
26 |
18 25
|
mp1i |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℕ0 ) |
27 |
26
|
nn0zd |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℤ ) |
28 |
3 27
|
zsubcld |
⊢ ( 𝜑 → ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ∈ ℤ ) |
29 |
|
inss1 |
⊢ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( bits ‘ 𝐵 ) |
30 |
|
bitsss |
⊢ ( bits ‘ 𝐵 ) ⊆ ℕ0 |
31 |
29 30
|
sstri |
⊢ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ℕ0 |
32 |
|
inss2 |
⊢ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( 0 ..^ 𝑁 ) |
33 |
|
ssfi |
⊢ ( ( ( 0 ..^ 𝑁 ) ∈ Fin ∧ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( 0 ..^ 𝑁 ) ) → ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin ) |
34 |
13 32 33
|
mp2an |
⊢ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin |
35 |
|
elfpw |
⊢ ( ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) ↔ ( ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ℕ0 ∧ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin ) ) |
36 |
31 34 35
|
mpbir2an |
⊢ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) |
37 |
24
|
ffvelrni |
⊢ ( ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) → ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℕ0 ) |
38 |
36 37
|
mp1i |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℕ0 ) |
39 |
38
|
nn0zd |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℤ ) |
40 |
4 39
|
zsubcld |
⊢ ( 𝜑 → ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ∈ ℤ ) |
41 |
2
|
fveq1i |
⊢ ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
42 |
3 8
|
zmodcld |
⊢ ( 𝜑 → ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ∈ ℕ0 ) |
43 |
42
|
fvresd |
⊢ ( 𝜑 → ( ( bits ↾ ℕ0 ) ‘ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) = ( bits ‘ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) ) |
44 |
|
bitsmod |
⊢ ( ( 𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) → ( bits ‘ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
45 |
3 5 44
|
syl2anc |
⊢ ( 𝜑 → ( bits ‘ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
46 |
43 45
|
eqtrd |
⊢ ( 𝜑 → ( ( bits ↾ ℕ0 ) ‘ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
47 |
|
f1ocnvfv |
⊢ ( ( ( bits ↾ ℕ0 ) : ℕ0 –1-1-onto→ ( 𝒫 ℕ0 ∩ Fin ) ∧ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ∈ ℕ0 ) → ( ( ( bits ↾ ℕ0 ) ‘ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) → ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) ) |
48 |
19 42 47
|
sylancr |
⊢ ( 𝜑 → ( ( ( bits ↾ ℕ0 ) ‘ ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) → ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) ) |
49 |
46 48
|
mpd |
⊢ ( 𝜑 → ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) |
50 |
41 49
|
eqtrid |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) |
51 |
50
|
oveq2d |
⊢ ( 𝜑 → ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) = ( 𝐴 − ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) ) |
52 |
51
|
oveq1d |
⊢ ( 𝜑 → ( ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) = ( ( 𝐴 − ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) / ( 2 ↑ 𝑁 ) ) ) |
53 |
3
|
zred |
⊢ ( 𝜑 → 𝐴 ∈ ℝ ) |
54 |
8
|
nnrpd |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ∈ ℝ+ ) |
55 |
|
moddifz |
⊢ ( ( 𝐴 ∈ ℝ ∧ ( 2 ↑ 𝑁 ) ∈ ℝ+ ) → ( ( 𝐴 − ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) |
56 |
53 54 55
|
syl2anc |
⊢ ( 𝜑 → ( ( 𝐴 − ( 𝐴 mod ( 2 ↑ 𝑁 ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) |
57 |
52 56
|
eqeltrd |
⊢ ( 𝜑 → ( ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) |
58 |
8
|
nnne0d |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ≠ 0 ) |
59 |
|
dvdsval2 |
⊢ ( ( ( 2 ↑ 𝑁 ) ∈ ℤ ∧ ( 2 ↑ 𝑁 ) ≠ 0 ∧ ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ∈ ℤ ) → ( ( 2 ↑ 𝑁 ) ∥ ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ↔ ( ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) ) |
60 |
9 58 28 59
|
syl3anc |
⊢ ( 𝜑 → ( ( 2 ↑ 𝑁 ) ∥ ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ↔ ( ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) ) |
61 |
57 60
|
mpbird |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ∥ ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) |
62 |
2
|
fveq1i |
⊢ ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
63 |
4 8
|
zmodcld |
⊢ ( 𝜑 → ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ∈ ℕ0 ) |
64 |
63
|
fvresd |
⊢ ( 𝜑 → ( ( bits ↾ ℕ0 ) ‘ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) = ( bits ‘ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) ) |
65 |
|
bitsmod |
⊢ ( ( 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) → ( bits ‘ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
66 |
4 5 65
|
syl2anc |
⊢ ( 𝜑 → ( bits ‘ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
67 |
64 66
|
eqtrd |
⊢ ( 𝜑 → ( ( bits ↾ ℕ0 ) ‘ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) |
68 |
|
f1ocnvfv |
⊢ ( ( ( bits ↾ ℕ0 ) : ℕ0 –1-1-onto→ ( 𝒫 ℕ0 ∩ Fin ) ∧ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ∈ ℕ0 ) → ( ( ( bits ↾ ℕ0 ) ‘ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) → ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) ) |
69 |
19 63 68
|
sylancr |
⊢ ( 𝜑 → ( ( ( bits ↾ ℕ0 ) ‘ ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) = ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) → ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) ) |
70 |
67 69
|
mpd |
⊢ ( 𝜑 → ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) |
71 |
62 70
|
eqtrid |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) |
72 |
71
|
oveq2d |
⊢ ( 𝜑 → ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) = ( 𝐵 − ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) ) |
73 |
72
|
oveq1d |
⊢ ( 𝜑 → ( ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) = ( ( 𝐵 − ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) / ( 2 ↑ 𝑁 ) ) ) |
74 |
4
|
zred |
⊢ ( 𝜑 → 𝐵 ∈ ℝ ) |
75 |
|
moddifz |
⊢ ( ( 𝐵 ∈ ℝ ∧ ( 2 ↑ 𝑁 ) ∈ ℝ+ ) → ( ( 𝐵 − ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) |
76 |
74 54 75
|
syl2anc |
⊢ ( 𝜑 → ( ( 𝐵 − ( 𝐵 mod ( 2 ↑ 𝑁 ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) |
77 |
73 76
|
eqeltrd |
⊢ ( 𝜑 → ( ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) |
78 |
|
dvdsval2 |
⊢ ( ( ( 2 ↑ 𝑁 ) ∈ ℤ ∧ ( 2 ↑ 𝑁 ) ≠ 0 ∧ ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ∈ ℤ ) → ( ( 2 ↑ 𝑁 ) ∥ ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ↔ ( ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) ) |
79 |
9 58 40 78
|
syl3anc |
⊢ ( 𝜑 → ( ( 2 ↑ 𝑁 ) ∥ ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ↔ ( ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) / ( 2 ↑ 𝑁 ) ) ∈ ℤ ) ) |
80 |
77 79
|
mpbird |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ∥ ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) |
81 |
9 28 40 61 80
|
dvds2addd |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ∥ ( ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) + ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) ) |
82 |
3
|
zcnd |
⊢ ( 𝜑 → 𝐴 ∈ ℂ ) |
83 |
4
|
zcnd |
⊢ ( 𝜑 → 𝐵 ∈ ℂ ) |
84 |
26
|
nn0cnd |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℂ ) |
85 |
38
|
nn0cnd |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℂ ) |
86 |
82 83 84 85
|
addsub4d |
⊢ ( 𝜑 → ( ( 𝐴 + 𝐵 ) − ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) = ( ( 𝐴 − ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) + ( 𝐵 − ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) ) |
87 |
81 86
|
breqtrrd |
⊢ ( 𝜑 → ( 2 ↑ 𝑁 ) ∥ ( ( 𝐴 + 𝐵 ) − ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) ) |
88 |
3 4
|
zaddcld |
⊢ ( 𝜑 → ( 𝐴 + 𝐵 ) ∈ ℤ ) |
89 |
27 39
|
zaddcld |
⊢ ( 𝜑 → ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ∈ ℤ ) |
90 |
|
moddvds |
⊢ ( ( ( 2 ↑ 𝑁 ) ∈ ℕ ∧ ( 𝐴 + 𝐵 ) ∈ ℤ ∧ ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ∈ ℤ ) → ( ( ( 𝐴 + 𝐵 ) mod ( 2 ↑ 𝑁 ) ) = ( ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) mod ( 2 ↑ 𝑁 ) ) ↔ ( 2 ↑ 𝑁 ) ∥ ( ( 𝐴 + 𝐵 ) − ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) ) ) |
91 |
8 88 89 90
|
syl3anc |
⊢ ( 𝜑 → ( ( ( 𝐴 + 𝐵 ) mod ( 2 ↑ 𝑁 ) ) = ( ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) mod ( 2 ↑ 𝑁 ) ) ↔ ( 2 ↑ 𝑁 ) ∥ ( ( 𝐴 + 𝐵 ) − ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) ) ) |
92 |
87 91
|
mpbird |
⊢ ( 𝜑 → ( ( 𝐴 + 𝐵 ) mod ( 2 ↑ 𝑁 ) ) = ( ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) mod ( 2 ↑ 𝑁 ) ) ) |
93 |
11
|
a1i |
⊢ ( 𝜑 → ( bits ‘ 𝐴 ) ⊆ ℕ0 ) |
94 |
30
|
a1i |
⊢ ( 𝜑 → ( bits ‘ 𝐵 ) ⊆ ℕ0 ) |
95 |
93 94 1 5 2
|
sadadd3 |
⊢ ( 𝜑 → ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) mod ( 2 ↑ 𝑁 ) ) = ( ( ( 𝐾 ‘ ( ( bits ‘ 𝐴 ) ∩ ( 0 ..^ 𝑁 ) ) ) + ( 𝐾 ‘ ( ( bits ‘ 𝐵 ) ∩ ( 0 ..^ 𝑁 ) ) ) ) mod ( 2 ↑ 𝑁 ) ) ) |
96 |
|
inss1 |
⊢ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) |
97 |
|
sadcl |
⊢ ( ( ( bits ‘ 𝐴 ) ⊆ ℕ0 ∧ ( bits ‘ 𝐵 ) ⊆ ℕ0 ) → ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ⊆ ℕ0 ) |
98 |
11 30 97
|
mp2an |
⊢ ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ⊆ ℕ0 |
99 |
96 98
|
sstri |
⊢ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ℕ0 |
100 |
|
inss2 |
⊢ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( 0 ..^ 𝑁 ) |
101 |
|
ssfi |
⊢ ( ( ( 0 ..^ 𝑁 ) ∈ Fin ∧ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ( 0 ..^ 𝑁 ) ) → ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin ) |
102 |
13 100 101
|
mp2an |
⊢ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin |
103 |
|
elfpw |
⊢ ( ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) ↔ ( ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ⊆ ℕ0 ∧ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ Fin ) ) |
104 |
99 102 103
|
mpbir2an |
⊢ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) |
105 |
24
|
ffvelrni |
⊢ ( ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) → ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℕ0 ) |
106 |
104 105
|
mp1i |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℕ0 ) |
107 |
106
|
nn0red |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℝ ) |
108 |
106
|
nn0ge0d |
⊢ ( 𝜑 → 0 ≤ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) |
109 |
2
|
fveq1i |
⊢ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) = ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) |
110 |
109
|
fveq2i |
⊢ ( ( bits ↾ ℕ0 ) ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) = ( ( bits ↾ ℕ0 ) ‘ ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) |
111 |
106
|
fvresd |
⊢ ( 𝜑 → ( ( bits ↾ ℕ0 ) ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) = ( bits ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) |
112 |
104
|
a1i |
⊢ ( 𝜑 → ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) ) |
113 |
|
f1ocnvfv2 |
⊢ ( ( ( bits ↾ ℕ0 ) : ℕ0 –1-1-onto→ ( 𝒫 ℕ0 ∩ Fin ) ∧ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ∈ ( 𝒫 ℕ0 ∩ Fin ) ) → ( ( bits ↾ ℕ0 ) ‘ ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) = ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) |
114 |
19 112 113
|
sylancr |
⊢ ( 𝜑 → ( ( bits ↾ ℕ0 ) ‘ ( ◡ ( bits ↾ ℕ0 ) ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) = ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) |
115 |
110 111 114
|
3eqtr3a |
⊢ ( 𝜑 → ( bits ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) = ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) |
116 |
115 100
|
eqsstrdi |
⊢ ( 𝜑 → ( bits ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ⊆ ( 0 ..^ 𝑁 ) ) |
117 |
106
|
nn0zd |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℤ ) |
118 |
|
bitsfzo |
⊢ ( ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℤ ∧ 𝑁 ∈ ℕ0 ) → ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ( 0 ..^ ( 2 ↑ 𝑁 ) ) ↔ ( bits ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ⊆ ( 0 ..^ 𝑁 ) ) ) |
119 |
117 5 118
|
syl2anc |
⊢ ( 𝜑 → ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ( 0 ..^ ( 2 ↑ 𝑁 ) ) ↔ ( bits ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ⊆ ( 0 ..^ 𝑁 ) ) ) |
120 |
116 119
|
mpbird |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ( 0 ..^ ( 2 ↑ 𝑁 ) ) ) |
121 |
|
elfzolt2 |
⊢ ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ( 0 ..^ ( 2 ↑ 𝑁 ) ) → ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) < ( 2 ↑ 𝑁 ) ) |
122 |
120 121
|
syl |
⊢ ( 𝜑 → ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) < ( 2 ↑ 𝑁 ) ) |
123 |
|
modid |
⊢ ( ( ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∈ ℝ ∧ ( 2 ↑ 𝑁 ) ∈ ℝ+ ) ∧ ( 0 ≤ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ∧ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) < ( 2 ↑ 𝑁 ) ) ) → ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) mod ( 2 ↑ 𝑁 ) ) = ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) |
124 |
107 54 108 122 123
|
syl22anc |
⊢ ( 𝜑 → ( ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) mod ( 2 ↑ 𝑁 ) ) = ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) |
125 |
92 95 124
|
3eqtr2d |
⊢ ( 𝜑 → ( ( 𝐴 + 𝐵 ) mod ( 2 ↑ 𝑁 ) ) = ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) |
126 |
125
|
fveq2d |
⊢ ( 𝜑 → ( bits ‘ ( ( 𝐴 + 𝐵 ) mod ( 2 ↑ 𝑁 ) ) ) = ( bits ‘ ( 𝐾 ‘ ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) ) ) ) |
127 |
126 115
|
eqtr2d |
⊢ ( 𝜑 → ( ( ( bits ‘ 𝐴 ) sadd ( bits ‘ 𝐵 ) ) ∩ ( 0 ..^ 𝑁 ) ) = ( bits ‘ ( ( 𝐴 + 𝐵 ) mod ( 2 ↑ 𝑁 ) ) ) ) |