Theorem: LO.FirstOrder.Arith.Model.LenBit.mod (Arithmetization/ISigmaZero/Exponential/Pow2.lean)

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
h : 2 * i ∣ k
⊢ LenBit i (a % k) ↔ LenBit i a
Tactic:
have : 0 ≤ i := zero_le i
State after:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
h : 2 * i ∣ k
this : 0 ≤ i
⊢ LenBit i (a % k) ↔ LenBit i a

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
h : 2 * i ∣ k
this : 0 ≤ i
⊢ LenBit i (a % k) ↔ LenBit i a
Tactic:
rcases (eq_or_lt_of_le this) with (rfl | pos)
State after:
case inl
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
a k : M
h : 2 * 0 ∣ k
this : 0 ≤ 0
⊢ LenBit 0 (a % k) ↔ LenBit 0 a

case inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
h : 2 * i ∣ k
this : 0 ≤ i
pos : 0 < i
⊢ LenBit i (a % k) ↔ LenBit i a

State before:
case inr
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
h : 2 * i ∣ k
this : 0 ≤ i
pos : 0 < i
⊢ LenBit i (a % k) ↔ LenBit i a
Tactic:
rcases h with ⟨k', hk'⟩
State after:
case inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ LenBit i (a % k) ↔ LenBit i a

State before:
case inr.intro
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ LenBit i (a % k) ↔ LenBit i a
Tactic:
calc
  LenBit i (a % k) ↔ ((a % k) / i) % 2 = 1                            := LenBit.iff_rem
  _                  ↔ ((2 * k') * (a / k) + a % k / i) % 2 = 1       := by simp [mul_assoc]
  _                  ↔ (((2 * k') * (a / k) * i + a % k) / i) % 2 = 1 := by simp [div_mul_add_self, pos]
  _                  ↔ ((k * (a / k) + a % k) / i) % 2 = 1            := iff_of_eq (by
                                                                                    congr 3
                                                                                    simp [mul_right_comm _ (a / k), mul_right_comm 2 k' i, ←hk'])
  _                  ↔ LenBit i a                                     := by simp [div_add_mod a k, LenBit.iff_rem]
State after:
no goals

State before:
case inl
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
a k : M
h : 2 * 0 ∣ k
this : 0 ≤ 0
⊢ LenBit 0 (a % k) ↔ LenBit 0 a
Tactic:
simp
State after:
no goals

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ a % k / i % 2 = 1 ↔ (2 * k' * (a / k) + a % k / i) % 2 = 1
Tactic:
simp [mul_assoc]
State after:
no goals

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ (2 * k' * (a / k) + a % k / i) % 2 = 1 ↔ (2 * k' * (a / k) * i + a % k) / i % 2 = 1
Tactic:
simp [div_mul_add_self, pos]
State after:
no goals

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ ((2 * k' * (a / k) * i + a % k) / i % 2 = 1) = ((k * (a / k) + a % k) / i % 2 = 1)
Tactic:
congr 3
State after:
case e_a.e_a.e_a
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ 2 * k' * (a / k) * i + a % k = k * (a / k) + a % k

State before:
case e_a.e_a.e_a
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ 2 * k' * (a / k) * i + a % k = k * (a / k) + a % k
Tactic:
simp [mul_right_comm _ (a / k), mul_right_comm 2 k' i, ←hk']
State after:
no goals

State before:
M : Type u_1
inst✝⁵ : Zero M
inst✝⁴ : One M
inst✝³ : Add M
inst✝² : Mul M
inst✝¹ : LT M
inst✝ : M ⊧ₘ* 𝐈open
i a k : M
this : 0 ≤ i
pos : 0 < i
k' : M
hk' : k = 2 * i * k'
⊢ (k * (a / k) + a % k) / i % 2 = 1 ↔ LenBit i a
Tactic:
simp [div_add_mod a k, LenBit.iff_rem]
State after:
no goals