data.nat.modeq
⟷
Mathlib.Data.Nat.ModEq
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
a/c ≡ b/c mod m/c → a ≡ b mod m
(#18666)
Also prove -a ≡ -b [ZMOD n] ↔ a ≡ b [ZMOD n]
, a ≡ b [ZMOD -n] ↔ a ≡ b [ZMOD n]
, generalise int.modeq.mul_left'
/int.modeq.mul_right'
, and rename
int.gcd_pos_of_non_zero_left
→ int.gcd_pos_of_ne_zero_left
int.gcd_pos_of_non_zero_right
→ int.gcd_pos_of_ne_zero_right
eq_iff_modeq_int
, char_p.int_coe_eq_int_coe_iff
→ char_p.int_cast_eq_int_cast
(they were duplicates)@@ -160,6 +160,10 @@ by { rw [modeq_iff_dvd] at *, exact (dvd_mul_left (n : ℤ) (m : ℤ)).trans h }
For cancelling right multiplication on both sides of the `≡`, see `nat.modeq.mul_right_cancel'`. -/
theorem of_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] := mul_comm m n ▸ of_mul_left _
+lemma of_div (h : a / c ≡ b / c [MOD m / c]) (ha : c ∣ a) (ha : c ∣ b) (ha : c ∣ m) :
+ a ≡ b [MOD m] :=
+by convert h.mul_left' c; rwa nat.mul_div_cancel'
+
end modeq
lemma modeq_sub (h : b ≤ a) : a ≡ b [MOD a - b] := (modeq_of_dvd $ by rw [int.coe_nat_sub h]).symm
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
Quite a few modeq
lemmas are still called nat.modeq.modeq_something
or int.modeq.modeq_something
. I'm deleting the duplicated modeq
, so that lemmas (usually) become nat.modeq.something
and int.modeq.something
.
Also add nat.modeq.eq_of_lt_of_lt
as a corollary to nat.modeq.eq_of_abs_lt
.
@@ -61,8 +61,7 @@ theorem modeq_iff_dvd : a ≡ b [MOD n] ↔ (n:ℤ) ∣ b - a :=
by rw [modeq, eq_comm, ← int.coe_nat_inj', int.coe_nat_mod, int.coe_nat_mod,
int.mod_eq_mod_iff_mod_sub_eq_zero, int.dvd_iff_mod_eq_zero]
-protected theorem modeq.dvd : a ≡ b [MOD n] → (n:ℤ) ∣ b - a := modeq_iff_dvd.1
-theorem modeq_of_dvd : (n:ℤ) ∣ b - a → a ≡ b [MOD n] := modeq_iff_dvd.2
+alias modeq_iff_dvd ↔ modeq.dvd modeq_of_dvd
/-- A variant of `modeq_iff_dvd` with `nat` divisibility -/
theorem modeq_iff_dvd' (h : a ≤ b) : a ≡ b [MOD n] ↔ n ∣ b - a :=
@@ -72,14 +71,14 @@ theorem mod_modeq (a n) : a % n ≡ a [MOD n] := mod_mod _ _
namespace modeq
-protected theorem modeq_of_dvd (d : m ∣ n) (h : a ≡ b [MOD n]) : a ≡ b [MOD m] :=
+protected theorem of_dvd (d : m ∣ n) (h : a ≡ b [MOD n]) : a ≡ b [MOD m] :=
modeq_of_dvd ((int.coe_nat_dvd.2 d).trans h.dvd)
protected theorem mul_left' (c : ℕ) (h : a ≡ b [MOD n]) : c * a ≡ c * b [MOD (c * n)] :=
by unfold modeq at *; rw [mul_mod_mul_left, mul_mod_mul_left, h]
protected theorem mul_left (c : ℕ) (h : a ≡ b [MOD n]) : c * a ≡ c * b [MOD n] :=
-(h.mul_left' _ ).modeq_of_dvd (dvd_mul_left _ _)
+(h.mul_left' _ ).of_dvd (dvd_mul_left _ _)
protected theorem mul_right' (c : ℕ) (h : a ≡ b [MOD n]) : a * c ≡ b * c [MOD (n * c)] :=
by rw [mul_comm a, mul_comm b, mul_comm n]; exact h.mul_left' c
@@ -128,6 +127,9 @@ by { rw [add_comm a, add_comm b] at h₂, exact h₁.add_left_cancel h₂ }
protected theorem add_right_cancel' (c : ℕ) (h : a + c ≡ b + c [MOD n]) : a ≡ b [MOD n] :=
modeq.rfl.add_right_cancel h
+/-- Cancel left multiplication on both sides of the `≡` and in the modulus.
+
+For cancelling left multiplication in the modulus, see `nat.modeq.of_mul_left`. -/
protected theorem mul_left_cancel' {a b c m : ℕ} (hc : c ≠ 0) :
c * a ≡ c * b [MOD c * m] → a ≡ b [MOD m] :=
by simp [modeq_iff_dvd, ←mul_sub, mul_dvd_mul_iff_left (by simp [hc] : (c : ℤ) ≠ 0)]
@@ -136,6 +138,9 @@ protected theorem mul_left_cancel_iff' {a b c m : ℕ} (hc : c ≠ 0) :
c * a ≡ c * b [MOD c * m] ↔ a ≡ b [MOD m] :=
⟨modeq.mul_left_cancel' hc, modeq.mul_left' _⟩
+/-- Cancel right multiplication on both sides of the `≡` and in the modulus.
+
+For cancelling right multiplication in the modulus, see `nat.modeq.of_mul_right`. -/
protected theorem mul_right_cancel' {a b c m : ℕ} (hc : c ≠ 0) :
a * c ≡ b * c [MOD m * c] → a ≡ b [MOD m] :=
by simp [modeq_iff_dvd, ←sub_mul, mul_dvd_mul_iff_right (by simp [hc] : (c : ℤ) ≠ 0)]
@@ -144,26 +149,27 @@ protected theorem mul_right_cancel_iff' {a b c m : ℕ} (hc : c ≠ 0) :
a * c ≡ b * c [MOD m * c] ↔ a ≡ b [MOD m] :=
⟨modeq.mul_right_cancel' hc, modeq.mul_right' _⟩
-theorem of_modeq_mul_left (m : ℕ) (h : a ≡ b [MOD m * n]) : a ≡ b [MOD n] :=
+/-- Cancel left multiplication in the modulus.
+
+For cancelling left multiplication on both sides of the `≡`, see `nat.modeq.mul_left_cancel'`. -/
+theorem of_mul_left (m : ℕ) (h : a ≡ b [MOD m * n]) : a ≡ b [MOD n] :=
by { rw [modeq_iff_dvd] at *, exact (dvd_mul_left (n : ℤ) (m : ℤ)).trans h }
-theorem of_modeq_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] :=
-mul_comm m n ▸ of_modeq_mul_left _
+/-- Cancel right multiplication in the modulus.
+
+For cancelling right multiplication on both sides of the `≡`, see `nat.modeq.mul_right_cancel'`. -/
+theorem of_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] := mul_comm m n ▸ of_mul_left _
end modeq
-theorem modeq_one : a ≡ b [MOD 1] := modeq_of_dvd (one_dvd _)
+lemma modeq_sub (h : b ≤ a) : a ≡ b [MOD a - b] := (modeq_of_dvd $ by rw [int.coe_nat_sub h]).symm
-lemma modeq_sub (h : b ≤ a) : a ≡ b [MOD a - b] :=
-(modeq_of_dvd $ by rw [int.coe_nat_sub h]).symm
+lemma modeq_one : a ≡ b [MOD 1] := modeq_of_dvd $ one_dvd _
-@[simp] lemma modeq_zero_iff {a b : ℕ} : a ≡ b [MOD 0] ↔ a = b :=
-by rw [nat.modeq, nat.mod_zero, nat.mod_zero]
+@[simp] lemma modeq_zero_iff : a ≡ b [MOD 0] ↔ a = b := by rw [modeq, mod_zero, mod_zero]
-@[simp] lemma add_modeq_left {a n : ℕ} : n + a ≡ a [MOD n] :=
-by rw [nat.modeq, nat.add_mod_left]
-@[simp] lemma add_modeq_right {a n : ℕ} : a + n ≡ a [MOD n] :=
-by rw [nat.modeq, nat.add_mod_right]
+@[simp] lemma add_modeq_left : n + a ≡ a [MOD n] := by rw [modeq, add_mod_left]
+@[simp] lemma add_modeq_right : a + n ≡ a [MOD n] := by rw [modeq, add_mod_right]
namespace modeq
@@ -174,33 +180,36 @@ lemma le_of_lt_add (h1 : a ≡ b [MOD m]) (h2 : a < b + m) : a ≤ b :=
lemma add_le_of_lt (h1 : a ≡ b [MOD m]) (h2 : a < b) : a + m ≤ b :=
le_of_lt_add (add_modeq_right.trans h1) (add_lt_add_right h2 m)
-lemma dvd_iff_of_modeq_of_dvd {a b d m : ℕ} (h : a ≡ b [MOD m]) (hdm : d ∣ m) :
- d ∣ a ↔ d ∣ b :=
+lemma dvd_iff (h : a ≡ b [MOD m]) (hdm : d ∣ m) : d ∣ a ↔ d ∣ b :=
begin
simp only [←modeq_zero_iff_dvd],
- replace h := h.modeq_of_dvd hdm,
+ replace h := h.of_dvd hdm,
exact ⟨h.symm.trans, h.trans⟩,
end
-lemma gcd_eq_of_modeq {a b m : ℕ} (h : a ≡ b [MOD m]) : gcd a m = gcd b m :=
+lemma gcd_eq (h : a ≡ b [MOD m]) : gcd a m = gcd b m :=
begin
have h1 := gcd_dvd_right a m,
have h2 := gcd_dvd_right b m,
exact dvd_antisymm
- (dvd_gcd ((dvd_iff_of_modeq_of_dvd h h1).mp (gcd_dvd_left a m)) h1)
- (dvd_gcd ((dvd_iff_of_modeq_of_dvd h h2).mpr (gcd_dvd_left b m)) h2),
+ (dvd_gcd ((h.dvd_iff h1).mp (gcd_dvd_left a m)) h1)
+ (dvd_gcd ((h.dvd_iff h2).mpr (gcd_dvd_left b m)) h2),
end
-lemma eq_of_modeq_of_abs_lt {a b m : ℕ} (h : a ≡ b [MOD m]) (h2 : | (b:ℤ) - a | < m) : a = b :=
+lemma eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b - a : ℤ)| < m) : a = b :=
begin
apply int.coe_nat_inj,
rw [eq_comm, ←sub_eq_zero],
exact int.eq_zero_of_abs_lt_dvd (modeq_iff_dvd.mp h) h2,
end
+lemma eq_of_lt_of_lt (h : a ≡ b [MOD m]) (ha : a < m) (hb : b < m) : a = b :=
+h.eq_of_abs_lt $ abs_sub_lt_iff.2
+ ⟨(sub_le_self _ $ int.coe_nat_nonneg _).trans_lt $ cast_lt.2 hb,
+ (sub_le_self _ $ int.coe_nat_nonneg _).trans_lt $ cast_lt.2 ha⟩
+
/-- To cancel a common factor `c` from a `modeq` we must divide the modulus `m` by `gcd m c` -/
-lemma modeq_cancel_left_div_gcd {a b c m : ℕ} (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) :
- a ≡ b [MOD m / gcd m c] :=
+lemma cancel_left_div_gcd (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) : a ≡ b [MOD m / gcd m c] :=
begin
let d := gcd m c,
have hmd := gcd_dvd_left m c,
@@ -217,35 +226,30 @@ begin
nat.div_self (gcd_pos_of_pos_left c hm)] },
end
-lemma modeq_cancel_right_div_gcd {a b c m : ℕ} (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) :
- a ≡ b [MOD m / gcd m c] :=
-by { apply modeq_cancel_left_div_gcd hm, simpa [mul_comm] using h }
+lemma cancel_right_div_gcd (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m / gcd m c] :=
+by { apply cancel_left_div_gcd hm, simpa [mul_comm] using h }
-lemma modeq_cancel_left_div_gcd' {a b c d m : ℕ} (hm : 0 < m) (hcd : c ≡ d [MOD m])
- (h : c * a ≡ d * b [MOD m]) :
+lemma cancel_left_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : c * a ≡ d * b [MOD m]) :
a ≡ b [MOD m / gcd m c] :=
-modeq_cancel_left_div_gcd hm (h.trans (modeq.mul_right b hcd).symm)
+(h.trans (modeq.mul_right b hcd).symm).cancel_left_div_gcd hm
-lemma modeq_cancel_right_div_gcd' {a b c d m : ℕ} (hm : 0 < m) (hcd : c ≡ d [MOD m])
- (h : a * c ≡ b * d [MOD m]) :
+lemma cancel_right_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : a * c ≡ b * d [MOD m]) :
a ≡ b [MOD m / gcd m c] :=
-by { apply modeq_cancel_left_div_gcd' hm hcd, simpa [mul_comm] using h }
+hcd.cancel_left_div_gcd' hm $ by simpa [mul_comm] using h
/-- A common factor that's coprime with the modulus can be cancelled from a `modeq` -/
-lemma modeq_cancel_left_of_coprime {a b c m : ℕ} (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) :
- a ≡ b [MOD m] :=
+lemma cancel_left_of_coprime (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) : a ≡ b [MOD m] :=
begin
rcases m.eq_zero_or_pos with rfl | hm,
{ simp only [gcd_zero_left] at hmc,
simp only [gcd_zero_left, hmc, one_mul, modeq_zero_iff] at h,
subst h },
- simpa [hmc] using modeq_cancel_left_div_gcd hm h
+ simpa [hmc] using h.cancel_left_div_gcd hm
end
/-- A common factor that's coprime with the modulus can be cancelled from a `modeq` -/
-lemma modeq_cancel_right_of_coprime {a b c m : ℕ} (hmc : gcd m c = 1) (h : a * c ≡ b * c [MOD m]) :
- a ≡ b [MOD m] :=
-by { apply modeq_cancel_left_of_coprime hmc, simpa [mul_comm] using h }
+lemma cancel_right_of_coprime (hmc : gcd m c = 1) (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m] :=
+cancel_left_of_coprime hmc $ by simpa [mul_comm] using h
end modeq
@@ -306,22 +310,22 @@ lemma modeq_and_modeq_iff_modeq_mul {a b m n : ℕ} (hmn : coprime m n) :
rw [nat.modeq_iff_dvd, ← int.dvd_nat_abs, int.coe_nat_dvd],
exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2
end,
-λ h, ⟨h.of_modeq_mul_right _, h.of_modeq_mul_left _⟩⟩
+λ h, ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
lemma coprime_of_mul_modeq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : coprime a n :=
begin
obtain ⟨g, hh⟩ := nat.gcd_dvd_right a n,
rw [nat.coprime_iff_gcd_eq_one, ← nat.dvd_one, ← nat.modeq_zero_iff_dvd],
- calc 1 ≡ a * b [MOD a.gcd n] : nat.modeq.of_modeq_mul_right g (hh.subst h).symm
+ calc 1 ≡ a * b [MOD a.gcd n] : nat.modeq.of_mul_right g (hh.subst h).symm
... ≡ 0 * b [MOD a.gcd n] : (nat.modeq_zero_iff_dvd.mpr (nat.gcd_dvd_left _ _)).mul_right b
... = 0 : by rw zero_mul,
end
@[simp] lemma mod_mul_right_mod (a b c : ℕ) : a % (b * c) % b = a % b :=
-(mod_modeq _ _).of_modeq_mul_right _
+(mod_modeq _ _).of_mul_right _
@[simp] lemma mod_mul_left_mod (a b c : ℕ) : a % (b * c) % c = a % c :=
-(mod_modeq _ _).of_modeq_mul_left _
+(mod_modeq _ _).of_mul_left _
lemma div_mod_eq_mod_mul_div (a b c : ℕ) : a / b % c = a % (b * c) / b :=
if hb0 : b = 0 then by simp [hb0]
@@ -414,11 +418,11 @@ by rw [mul_add, two_mul_odd_div_two hm1, mul_left_comm, two_mul_odd_div_two hn1,
tsub_add_cancel_of_le (le_mul_of_one_le_right (nat.zero_le _) hn0)]
lemma odd_of_mod_four_eq_one {n : ℕ} : n % 4 = 1 → n % 2 = 1 :=
-by simpa [modeq, show 2 * 2 = 4, by norm_num] using @modeq.of_modeq_mul_left 2 n 1 2
+by simpa [modeq, show 2 * 2 = 4, by norm_num] using @modeq.of_mul_left 2 n 1 2
lemma odd_of_mod_four_eq_three {n : ℕ} : n % 4 = 3 → n % 2 = 1 :=
by simpa [modeq, show 2 * 2 = 4, by norm_num, show 3 % 4 = 3, by norm_num]
- using @modeq.of_modeq_mul_left 2 n 3 2
+ using @modeq.of_mul_left 2 n 3 2
/-- A natural number is odd iff it has residue `1` or `3` mod `4`-/
lemma odd_mod_four_iff {n : ℕ} : n % 2 = 1 ↔ n % 4 = 1 ∨ n % 4 = 3 :=
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(first ported)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -3,7 +3,7 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-/
-import Data.Int.Gcd
+import Data.Int.GCD
import Tactic.Abel
#align_import data.nat.modeq from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
@@ -101,7 +101,7 @@ theorem Dvd.dvd.zero_modEq_nat (h : n ∣ a) : 0 ≡ a [MOD n] :=
#print Nat.modEq_iff_dvd /-
theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
- rw [modeq, eq_comm, ← Int.coe_nat_inj', Int.coe_nat_mod, Int.coe_nat_mod,
+ rw [modeq, eq_comm, ← Int.natCast_inj, Int.natCast_mod, Int.natCast_mod,
Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.dvd_iff_emod_eq_zero]
#align nat.modeq_iff_dvd Nat.modEq_iff_dvd
-/
@@ -113,7 +113,7 @@ alias ⟨modeq.dvd, modeq_of_dvd⟩ := modeq_iff_dvd
#print Nat.modEq_iff_dvd' /-
/-- A variant of `modeq_iff_dvd` with `nat` divisibility -/
theorem modEq_iff_dvd' (h : a ≤ b) : a ≡ b [MOD n] ↔ n ∣ b - a := by
- rw [modeq_iff_dvd, ← Int.coe_nat_dvd, Int.ofNat_sub h]
+ rw [modeq_iff_dvd, ← Int.natCast_dvd_natCast, Int.ofNat_sub h]
#align nat.modeq_iff_dvd' Nat.modEq_iff_dvd'
-/
@@ -127,7 +127,7 @@ namespace Modeq
#print Nat.ModEq.of_dvd /-
protected theorem of_dvd (d : m ∣ n) (h : a ≡ b [MOD n]) : a ≡ b [MOD m] :=
- modEq_of_dvd ((Int.coe_nat_dvd.2 d).trans h.Dvd)
+ modEq_of_dvd ((Int.natCast_dvd_natCast.2 d).trans h.Dvd)
#align nat.modeq.of_dvd Nat.ModEq.of_dvd
-/
@@ -165,7 +165,7 @@ protected theorem mul (h₁ : a ≡ b [MOD n]) (h₂ : c ≡ d [MOD n]) : a * c
protected theorem pow (m : ℕ) (h : a ≡ b [MOD n]) : a ^ m ≡ b ^ m [MOD n] :=
by
induction' m with d hd; · rfl
- rw [pow_succ, pow_succ]
+ rw [pow_succ', pow_succ']
exact h.mul hd
#align nat.modeq.pow Nat.ModEq.pow
-/
@@ -196,7 +196,7 @@ protected theorem add_left_cancel (h₁ : a ≡ b [MOD n]) (h₂ : a + c ≡ b +
simp only [modeq_iff_dvd, Int.ofNat_add] at *
rw [add_sub_add_comm] at h₂
convert _root_.dvd_sub h₂ h₁ using 1
- rw [add_sub_cancel']
+ rw [add_sub_cancel_left]
#align nat.modeq.add_left_cancel Nat.ModEq.add_left_cancel
-/
@@ -357,8 +357,8 @@ theorem eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b - a : ℤ)| < m) : a = b :=
theorem eq_of_lt_of_lt (h : a ≡ b [MOD m]) (ha : a < m) (hb : b < m) : a = b :=
h.eq_of_abs_lt <|
abs_sub_lt_iff.2
- ⟨(sub_le_self _ <| Int.coe_nat_nonneg _).trans_lt <| cast_lt.2 hb,
- (sub_le_self _ <| Int.coe_nat_nonneg _).trans_lt <| cast_lt.2 ha⟩
+ ⟨(sub_le_self _ <| Int.natCast_nonneg _).trans_lt <| cast_lt.2 hb,
+ (sub_le_self _ <| Int.natCast_nonneg _).trans_lt <| cast_lt.2 ha⟩
#align nat.modeq.eq_of_lt_of_lt Nat.ModEq.eq_of_lt_of_lt
-/
@@ -378,7 +378,7 @@ theorem cancel_left_div_gcd (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) : a ≡ b
exact modeq_iff_dvd.mp h
show Int.gcd (m / d) (c / d) = 1
·
- simp only [← Int.coe_nat_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
+ simp only [← Int.natCast_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
Nat.div_self (gcd_pos_of_pos_left c hm)]
#align nat.modeq.cancel_left_div_gcd Nat.ModEq.cancel_left_div_gcd
-/
@@ -437,7 +437,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
rw [xgcd_val]
dsimp [chinese_remainder'._match_1]
rw [modeq_iff_dvd, modeq_iff_dvd,
- Int.toNat_of_nonneg (Int.emod_nonneg _ (Int.coe_nat_ne_zero.2 (lcm_ne_zero hn hm)))]
+ Int.toNat_of_nonneg (Int.emod_nonneg _ (Int.natCast_ne_zero.2 (lcm_ne_zero hn hm)))]
have hnonzero : (gcd n m : ℤ) ≠ 0 := by
norm_cast
rw [Nat.gcd_eq_zero_iff, not_and]
@@ -476,7 +476,7 @@ theorem chineseRemainder'_lt_lcm (h : a ≡ b [MOD gcd n m]) (hn : n ≠ 0) (hm
↑(chineseRemainder' h) < lcm n m :=
by
dsimp only [chinese_remainder']
- rw [dif_neg hn, dif_neg hm, Subtype.coe_mk, xgcd_val, ← Int.toNat_coe_nat (lcm n m)]
+ rw [dif_neg hn, dif_neg hm, Subtype.coe_mk, xgcd_val, ← Int.toNat_natCast (lcm n m)]
have lcm_pos := int.coe_nat_pos.mpr (Nat.pos_of_ne_zero (lcm_ne_zero hn hm))
exact (Int.toNat_lt_toNat lcm_pos).mpr (Int.emod_lt_of_pos _ lcm_pos)
#align nat.chinese_remainder'_lt_lcm Nat.chineseRemainder'_lt_lcm
@@ -494,9 +494,9 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : Coprime m n) :
a ≡ b [MOD m] ∧ a ≡ b [MOD n] ↔ a ≡ b [MOD m * n] :=
⟨fun h =>
by
- rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
- Int.coe_nat_dvd] at h
- rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd]
+ rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.natCast_dvd_natCast, ←
+ Int.dvd_natAbs, Int.natCast_dvd_natCast] at h
+ rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.natCast_dvd_natCast]
exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2, fun h => ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -194,7 +194,7 @@ protected theorem add_right (c : ℕ) (h : a ≡ b [MOD n]) : a + c ≡ b + c [M
protected theorem add_left_cancel (h₁ : a ≡ b [MOD n]) (h₂ : a + c ≡ b + d [MOD n]) :
c ≡ d [MOD n] := by
simp only [modeq_iff_dvd, Int.ofNat_add] at *
- rw [add_sub_add_comm] at h₂
+ rw [add_sub_add_comm] at h₂
convert _root_.dvd_sub h₂ h₁ using 1
rw [add_sub_cancel']
#align nat.modeq.add_left_cancel Nat.ModEq.add_left_cancel
@@ -208,7 +208,7 @@ protected theorem add_left_cancel' (c : ℕ) (h : c + a ≡ c + b [MOD n]) : a
#print Nat.ModEq.add_right_cancel /-
protected theorem add_right_cancel (h₁ : c ≡ d [MOD n]) (h₂ : a + c ≡ b + d [MOD n]) :
- a ≡ b [MOD n] := by rw [add_comm a, add_comm b] at h₂ ; exact h₁.add_left_cancel h₂
+ a ≡ b [MOD n] := by rw [add_comm a, add_comm b] at h₂; exact h₁.add_left_cancel h₂
#align nat.modeq.add_right_cancel Nat.ModEq.add_right_cancel
-/
@@ -408,8 +408,8 @@ theorem cancel_right_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : a * c
theorem cancel_left_of_coprime (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) : a ≡ b [MOD m] :=
by
rcases m.eq_zero_or_pos with (rfl | hm)
- · simp only [gcd_zero_left] at hmc
- simp only [gcd_zero_left, hmc, one_mul, modeq_zero_iff] at h
+ · simp only [gcd_zero_left] at hmc
+ simp only [gcd_zero_left, hmc, one_mul, modeq_zero_iff] at h
subst h
simpa [hmc] using h.cancel_left_div_gcd hm
#align nat.modeq.cancel_left_of_coprime Nat.ModEq.cancel_left_of_coprime
@@ -427,9 +427,9 @@ end Modeq
#print Nat.chineseRemainder' /-
/-- The natural number less than `lcm n m` congruent to `a` mod `n` and `b` mod `m` -/
def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
- if hn : n = 0 then ⟨a, by rw [hn, gcd_zero_left] at h ; constructor; rfl; exact h⟩
+ if hn : n = 0 then ⟨a, by rw [hn, gcd_zero_left] at h; constructor; rfl; exact h⟩
else
- if hm : m = 0 then ⟨b, by rw [hm, gcd_zero_right] at h ; constructor; exact h.symm; rfl⟩
+ if hm : m = 0 then ⟨b, by rw [hm, gcd_zero_right] at h; constructor; exact h.symm; rfl⟩
else
⟨let (c, d) := xgcd n m
Int.toNat ((n * c * b + m * d * a) / gcd n m % lcm n m),
@@ -447,14 +447,14 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
constructor <;> rw [Int.mod_def, ← sub_add] <;>
refine' dvd_add _ (dvd_mul_of_dvd_left _ _) <;>
try norm_cast
- · rw [← sub_eq_iff_eq_add'] at this
+ · rw [← sub_eq_iff_eq_add'] at this
rw [← this, sub_mul, ← add_sub_assoc, add_comm, add_sub_assoc, ← mul_sub,
Int.add_ediv_of_dvd_left, Int.mul_ediv_cancel_left _ hnonzero,
Int.mul_ediv_assoc _ h.dvd, ← sub_sub, sub_self, zero_sub, dvd_neg, mul_assoc]
exact dvd_mul_right _ _
norm_cast; exact dvd_mul_right _ _
· exact dvd_lcm_left n m
- · rw [← sub_eq_iff_eq_add] at this
+ · rw [← sub_eq_iff_eq_add] at this
rw [← this, sub_mul, sub_add, ← mul_sub, Int.sub_ediv_of_dvd,
Int.mul_ediv_cancel_left _ hnonzero, Int.mul_ediv_assoc _ h.dvd, ← sub_add, sub_self,
zero_add, mul_assoc]
@@ -495,7 +495,7 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : Coprime m n) :
⟨fun h =>
by
rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
- Int.coe_nat_dvd] at h
+ Int.coe_nat_dvd] at h
rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd]
exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2, fun h => ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,8 +3,8 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-/
-import Mathbin.Data.Int.Gcd
-import Mathbin.Tactic.Abel
+import Data.Int.Gcd
+import Tactic.Abel
#align_import data.nat.modeq from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -466,7 +466,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
#print Nat.chineseRemainder /-
/-- The natural number less than `n*m` congruent to `a` mod `n` and `b` mod `m` -/
-def chineseRemainder (co : coprime n m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
+def chineseRemainder (co : Coprime n m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
chineseRemainder' (by convert modeq_one)
#align nat.chinese_remainder Nat.chineseRemainder
-/
@@ -483,14 +483,14 @@ theorem chineseRemainder'_lt_lcm (h : a ≡ b [MOD gcd n m]) (hn : n ≠ 0) (hm
-/
#print Nat.chineseRemainder_lt_mul /-
-theorem chineseRemainder_lt_mul (co : coprime n m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
+theorem chineseRemainder_lt_mul (co : Coprime n m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
↑(chineseRemainder co a b) < n * m :=
lt_of_lt_of_le (chineseRemainder'_lt_lcm _ hn hm) (le_of_eq co.lcm_eq_mul)
#align nat.chinese_remainder_lt_mul Nat.chineseRemainder_lt_mul
-/
#print Nat.modEq_and_modEq_iff_modEq_mul /-
-theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : coprime m n) :
+theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : Coprime m n) :
a ≡ b [MOD m] ∧ a ≡ b [MOD n] ↔ a ≡ b [MOD m * n] :=
⟨fun h =>
by
@@ -502,7 +502,7 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : coprime m n) :
-/
#print Nat.coprime_of_mul_modEq_one /-
-theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : coprime a n :=
+theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : Coprime a n :=
by
obtain ⟨g, hh⟩ := Nat.gcd_dvd_right a n
rw [Nat.coprime_iff_gcd_eq_one, ← Nat.dvd_one, ← Nat.modEq_zero_iff_dvd]
mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504
@@ -106,7 +106,7 @@ theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
#align nat.modeq_iff_dvd Nat.modEq_iff_dvd
-/
-alias modeq_iff_dvd ↔ modeq.dvd modeq_of_dvd
+alias ⟨modeq.dvd, modeq_of_dvd⟩ := modeq_iff_dvd
#align nat.modeq.dvd Nat.ModEq.dvd
#align nat.modeq_of_dvd Nat.modEq_of_dvd
mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504
@@ -157,7 +157,7 @@ protected theorem mul_right (c : ℕ) (h : a ≡ b [MOD n]) : a * c ≡ b * c [M
#print Nat.ModEq.mul /-
protected theorem mul (h₁ : a ≡ b [MOD n]) (h₂ : c ≡ d [MOD n]) : a * c ≡ b * d [MOD n] :=
- (h₂.mul_left _).trans (h₁.mul_right _)
+ (h₂.hMul_left _).trans (h₁.hMul_right _)
#align nat.modeq.mul Nat.ModEq.mul
-/
@@ -508,7 +508,7 @@ theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n])
rw [Nat.coprime_iff_gcd_eq_one, ← Nat.dvd_one, ← Nat.modEq_zero_iff_dvd]
calc
1 ≡ a * b [MOD a.gcd n] := Nat.ModEq.of_mul_right g (hh.subst h).symm
- _ ≡ 0 * b [MOD a.gcd n] := ((nat.modeq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).mul_right b)
+ _ ≡ 0 * b [MOD a.gcd n] := ((nat.modeq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).hMul_right b)
_ = 0 := by rw [MulZeroClass.zero_mul]
#align nat.coprime_of_mul_modeq_one Nat.coprime_of_mul_modEq_one
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,15 +2,12 @@
Copyright (c) 2017 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.modeq
-! leanprover-community/mathlib commit 47a1a73351de8dd6c8d3d32b569c8e434b03ca47
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Data.Int.Gcd
import Mathbin.Tactic.Abel
+#align_import data.nat.modeq from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
+
/-!
# Congruences modulo a natural number
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -41,7 +41,6 @@ deriving Decidable
#align nat.modeq Nat.ModEq
-/
--- mathport name: «expr ≡ [MOD ]»
notation:50 a " ≡ " b " [MOD " n "]" => ModEq n a b
variable {m n a b c d : ℕ}
@@ -103,10 +102,12 @@ theorem Dvd.dvd.zero_modEq_nat (h : n ∣ a) : 0 ≡ a [MOD n] :=
#align has_dvd.dvd.zero_modeq_nat Dvd.dvd.zero_modEq_nat
-/
+#print Nat.modEq_iff_dvd /-
theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
rw [modeq, eq_comm, ← Int.coe_nat_inj', Int.coe_nat_mod, Int.coe_nat_mod,
Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.dvd_iff_emod_eq_zero]
#align nat.modeq_iff_dvd Nat.modEq_iff_dvd
+-/
alias modeq_iff_dvd ↔ modeq.dvd modeq_of_dvd
#align nat.modeq.dvd Nat.ModEq.dvd
@@ -346,12 +347,14 @@ theorem gcd_eq (h : a ≡ b [MOD m]) : gcd a m = gcd b m :=
#align nat.modeq.gcd_eq Nat.ModEq.gcd_eq
-/
+#print Nat.ModEq.eq_of_abs_lt /-
theorem eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b - a : ℤ)| < m) : a = b :=
by
apply Int.ofNat.inj
rw [eq_comm, ← sub_eq_zero]
exact Int.eq_zero_of_abs_lt_dvd (modeq_iff_dvd.mp h) h2
#align nat.modeq.eq_of_abs_lt Nat.ModEq.eq_of_abs_lt
+-/
#print Nat.ModEq.eq_of_lt_of_lt /-
theorem eq_of_lt_of_lt (h : a ≡ b [MOD m]) (ha : a < m) (hb : b < m) : a = b :=
@@ -538,6 +541,7 @@ theorem div_mod_eq_mod_mul_div (a b c : ℕ) : a / b % c = a % (b * c) / b :=
#align nat.div_mod_eq_mod_mul_div Nat.div_mod_eq_mod_mul_div
-/
+#print Nat.add_mod_add_ite /-
theorem add_mod_add_ite (a b c : ℕ) :
((a + b) % c + if c ≤ a % c + b % c then c else 0) = a % c + b % c :=
have : (a + b) % c = (a % c + b % c) % c := ((mod_modEq _ _).add <| mod_modEq _ _).symm
@@ -557,6 +561,7 @@ theorem add_mod_add_ite (a b c : ℕ) :
mod_add_div, le_antisymm (le_of_lt_succ h2) h0, mul_one, add_comm]
· rw [Nat.mod_eq_of_lt (lt_of_not_ge h), add_zero]
#align nat.add_mod_add_ite Nat.add_mod_add_ite
+-/
#print Nat.add_mod_of_add_mod_lt /-
theorem add_mod_of_add_mod_lt {a b c : ℕ} (hc : a % c + b % c < c) : (a + b) % c = a % c + b % c :=
@@ -570,6 +575,7 @@ theorem add_mod_add_of_le_add_mod {a b c : ℕ} (hc : c ≤ a % c + b % c) :
#align nat.add_mod_add_of_le_add_mod Nat.add_mod_add_of_le_add_mod
-/
+#print Nat.add_div /-
theorem add_div {a b c : ℕ} (hc0 : 0 < c) :
(a + b) / c = a / c + b / c + if c ≤ a % c + b % c then 1 else 0 :=
by
@@ -583,6 +589,7 @@ theorem add_div {a b c : ℕ} (hc0 : 0 < c) :
conv_lhs => rw [← add_mod_add_ite]
simp; ac_rfl
#align nat.add_div Nat.add_div
+-/
#print Nat.add_div_eq_of_add_mod_lt /-
theorem add_div_eq_of_add_mod_lt {a b c : ℕ} (hc : a % c + b % c < c) :
mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0
@@ -510,7 +510,6 @@ theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n])
1 ≡ a * b [MOD a.gcd n] := Nat.ModEq.of_mul_right g (hh.subst h).symm
_ ≡ 0 * b [MOD a.gcd n] := ((nat.modeq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).mul_right b)
_ = 0 := by rw [MulZeroClass.zero_mul]
-
#align nat.coprime_of_mul_modeq_one Nat.coprime_of_mul_modEq_one
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -36,7 +36,8 @@ namespace Nat
#print Nat.ModEq /-
/-- Modular equality. `n.modeq a b`, or `a ≡ b [MOD n]`, means that `a - b` is a multiple of `n`. -/
def ModEq (n a b : ℕ) :=
- a % n = b % n deriving Decidable
+ a % n = b % n
+deriving Decidable
#align nat.modeq Nat.ModEq
-/
@@ -195,7 +196,7 @@ protected theorem add_right (c : ℕ) (h : a ≡ b [MOD n]) : a + c ≡ b + c [M
protected theorem add_left_cancel (h₁ : a ≡ b [MOD n]) (h₂ : a + c ≡ b + d [MOD n]) :
c ≡ d [MOD n] := by
simp only [modeq_iff_dvd, Int.ofNat_add] at *
- rw [add_sub_add_comm] at h₂
+ rw [add_sub_add_comm] at h₂
convert _root_.dvd_sub h₂ h₁ using 1
rw [add_sub_cancel']
#align nat.modeq.add_left_cancel Nat.ModEq.add_left_cancel
@@ -209,7 +210,7 @@ protected theorem add_left_cancel' (c : ℕ) (h : c + a ≡ c + b [MOD n]) : a
#print Nat.ModEq.add_right_cancel /-
protected theorem add_right_cancel (h₁ : c ≡ d [MOD n]) (h₂ : a + c ≡ b + d [MOD n]) :
- a ≡ b [MOD n] := by rw [add_comm a, add_comm b] at h₂; exact h₁.add_left_cancel h₂
+ a ≡ b [MOD n] := by rw [add_comm a, add_comm b] at h₂ ; exact h₁.add_left_cancel h₂
#align nat.modeq.add_right_cancel Nat.ModEq.add_right_cancel
-/
@@ -407,8 +408,8 @@ theorem cancel_right_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : a * c
theorem cancel_left_of_coprime (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) : a ≡ b [MOD m] :=
by
rcases m.eq_zero_or_pos with (rfl | hm)
- · simp only [gcd_zero_left] at hmc
- simp only [gcd_zero_left, hmc, one_mul, modeq_zero_iff] at h
+ · simp only [gcd_zero_left] at hmc
+ simp only [gcd_zero_left, hmc, one_mul, modeq_zero_iff] at h
subst h
simpa [hmc] using h.cancel_left_div_gcd hm
#align nat.modeq.cancel_left_of_coprime Nat.ModEq.cancel_left_of_coprime
@@ -426,9 +427,9 @@ end Modeq
#print Nat.chineseRemainder' /-
/-- The natural number less than `lcm n m` congruent to `a` mod `n` and `b` mod `m` -/
def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
- if hn : n = 0 then ⟨a, by rw [hn, gcd_zero_left] at h; constructor; rfl; exact h⟩
+ if hn : n = 0 then ⟨a, by rw [hn, gcd_zero_left] at h ; constructor; rfl; exact h⟩
else
- if hm : m = 0 then ⟨b, by rw [hm, gcd_zero_right] at h; constructor; exact h.symm; rfl⟩
+ if hm : m = 0 then ⟨b, by rw [hm, gcd_zero_right] at h ; constructor; exact h.symm; rfl⟩
else
⟨let (c, d) := xgcd n m
Int.toNat ((n * c * b + m * d * a) / gcd n m % lcm n m),
@@ -446,14 +447,14 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
constructor <;> rw [Int.mod_def, ← sub_add] <;>
refine' dvd_add _ (dvd_mul_of_dvd_left _ _) <;>
try norm_cast
- · rw [← sub_eq_iff_eq_add'] at this
+ · rw [← sub_eq_iff_eq_add'] at this
rw [← this, sub_mul, ← add_sub_assoc, add_comm, add_sub_assoc, ← mul_sub,
Int.add_ediv_of_dvd_left, Int.mul_ediv_cancel_left _ hnonzero,
Int.mul_ediv_assoc _ h.dvd, ← sub_sub, sub_self, zero_sub, dvd_neg, mul_assoc]
exact dvd_mul_right _ _
norm_cast; exact dvd_mul_right _ _
· exact dvd_lcm_left n m
- · rw [← sub_eq_iff_eq_add] at this
+ · rw [← sub_eq_iff_eq_add] at this
rw [← this, sub_mul, sub_add, ← mul_sub, Int.sub_ediv_of_dvd,
Int.mul_ediv_cancel_left _ hnonzero, Int.mul_ediv_assoc _ h.dvd, ← sub_add, sub_self,
zero_add, mul_assoc]
@@ -494,7 +495,7 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : coprime m n) :
⟨fun h =>
by
rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
- Int.coe_nat_dvd] at h
+ Int.coe_nat_dvd] at h
rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd]
exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2, fun h => ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -102,29 +102,11 @@ theorem Dvd.dvd.zero_modEq_nat (h : n ∣ a) : 0 ≡ a [MOD n] :=
#align has_dvd.dvd.zero_modeq_nat Dvd.dvd.zero_modEq_nat
-/
-/- warning: nat.modeq_iff_dvd -> Nat.modEq_iff_dvd is a dubious translation:
-lean 3 declaration is
- forall {n : Nat} {a : Nat} {b : Nat}, Iff (Nat.ModEq n a b) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a)))
-but is expected to have type
- forall {n : Nat} {a : Nat} {b : Nat}, Iff (Nat.ModEq n a b) (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a)))
-Case conversion may be inaccurate. Consider using '#align nat.modeq_iff_dvd Nat.modEq_iff_dvdₓ'. -/
theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
rw [modeq, eq_comm, ← Int.coe_nat_inj', Int.coe_nat_mod, Int.coe_nat_mod,
Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.dvd_iff_emod_eq_zero]
#align nat.modeq_iff_dvd Nat.modEq_iff_dvd
-/- warning: nat.modeq.dvd -> Nat.ModEq.dvd is a dubious translation:
-lean 3 declaration is
- forall {n : Nat} {a : Nat} {b : Nat}, (Nat.ModEq n a b) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a)))
-but is expected to have type
- forall {n : Nat} {a : Nat} {b : Nat}, (Nat.ModEq n a b) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a)))
-Case conversion may be inaccurate. Consider using '#align nat.modeq.dvd Nat.ModEq.dvdₓ'. -/
-/- warning: nat.modeq_of_dvd -> Nat.modEq_of_dvd is a dubious translation:
-lean 3 declaration is
- forall {n : Nat} {a : Nat} {b : Nat}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a))) -> (Nat.ModEq n a b)
-but is expected to have type
- forall {n : Nat} {a : Nat} {b : Nat}, (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a))) -> (Nat.ModEq n a b)
-Case conversion may be inaccurate. Consider using '#align nat.modeq_of_dvd Nat.modEq_of_dvdₓ'. -/
alias modeq_iff_dvd ↔ modeq.dvd modeq_of_dvd
#align nat.modeq.dvd Nat.ModEq.dvd
#align nat.modeq_of_dvd Nat.modEq_of_dvd
@@ -363,12 +345,6 @@ theorem gcd_eq (h : a ≡ b [MOD m]) : gcd a m = gcd b m :=
#align nat.modeq.gcd_eq Nat.ModEq.gcd_eq
-/
-/- warning: nat.modeq.eq_of_abs_lt -> Nat.ModEq.eq_of_abs_lt is a dubious translation:
-lean 3 declaration is
- forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.hasLt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.hasNeg (SemilatticeSup.toHasSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (LinearOrder.toLattice.{0} Int Int.linearOrder)))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a))) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) m)) -> (Eq.{1} Nat a b)
-but is expected to have type
- forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.instLTInt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.instNegInt (SemilatticeSup.toSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (DistribLattice.toLattice.{0} Int (instDistribLattice.{0} Int Int.instLinearOrderInt))))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a))) (Nat.cast.{0} Int instNatCastInt m)) -> (Eq.{1} Nat a b)
-Case conversion may be inaccurate. Consider using '#align nat.modeq.eq_of_abs_lt Nat.ModEq.eq_of_abs_ltₓ'. -/
theorem eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b - a : ℤ)| < m) : a = b :=
by
apply Int.ofNat.inj
@@ -562,12 +538,6 @@ theorem div_mod_eq_mod_mul_div (a b c : ℕ) : a / b % c = a % (b * c) / b :=
#align nat.div_mod_eq_mod_mul_div Nat.div_mod_eq_mod_mul_div
-/
-/- warning: nat.add_mod_add_ite -> Nat.add_mod_add_ite is a dubious translation:
-lean 3 declaration is
- forall (a : Nat) (b : Nat) (c : Nat), Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) a b) c) (ite.{1} Nat (LE.le.{0} Nat Nat.hasLe c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) b c))) (Nat.decidableLe c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) b c))) c (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))))) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) b c))
-but is expected to have type
- forall (a : Nat) (b : Nat) (c : Nat), Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) a b) c) (ite.{1} Nat (LE.le.{0} Nat instLENat c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) b c))) (Nat.decLe c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) b c))) c (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)))) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) b c))
-Case conversion may be inaccurate. Consider using '#align nat.add_mod_add_ite Nat.add_mod_add_iteₓ'. -/
theorem add_mod_add_ite (a b c : ℕ) :
((a + b) % c + if c ≤ a % c + b % c then c else 0) = a % c + b % c :=
have : (a + b) % c = (a % c + b % c) % c := ((mod_modEq _ _).add <| mod_modEq _ _).symm
@@ -600,12 +570,6 @@ theorem add_mod_add_of_le_add_mod {a b c : ℕ} (hc : c ≤ a % c + b % c) :
#align nat.add_mod_add_of_le_add_mod Nat.add_mod_add_of_le_add_mod
-/
-/- warning: nat.add_div -> Nat.add_div is a dubious translation:
-lean 3 declaration is
- forall {a : Nat} {b : Nat} {c : Nat}, (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) c) -> (Eq.{1} Nat (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.hasDiv) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) a b) c) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.hasDiv) a c) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.hasDiv) b c)) (ite.{1} Nat (LE.le.{0} Nat Nat.hasLe c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) b c))) (Nat.decidableLe c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.hasMod) b c))) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))) (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))))))
-but is expected to have type
- forall {a : Nat} {b : Nat} {c : Nat}, (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) c) -> (Eq.{1} Nat (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.instDivNat) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) a b) c) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.instDivNat) a c) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.instDivNat) b c)) (ite.{1} Nat (LE.le.{0} Nat instLENat c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) b c))) (Nat.decLe c (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) a c) (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) b c))) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)))))
-Case conversion may be inaccurate. Consider using '#align nat.add_div Nat.add_divₓ'. -/
theorem add_div {a b c : ℕ} (hc0 : 0 < c) :
(a + b) / c = a / c + b / c + if c ≤ a % c + b % c then 1 else 0 :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -227,9 +227,7 @@ protected theorem add_left_cancel' (c : ℕ) (h : c + a ≡ c + b [MOD n]) : a
#print Nat.ModEq.add_right_cancel /-
protected theorem add_right_cancel (h₁ : c ≡ d [MOD n]) (h₂ : a + c ≡ b + d [MOD n]) :
- a ≡ b [MOD n] := by
- rw [add_comm a, add_comm b] at h₂
- exact h₁.add_left_cancel h₂
+ a ≡ b [MOD n] := by rw [add_comm a, add_comm b] at h₂; exact h₁.add_left_cancel h₂
#align nat.modeq.add_right_cancel Nat.ModEq.add_right_cancel
-/
@@ -277,9 +275,7 @@ protected theorem mul_right_cancel_iff' {a b c m : ℕ} (hc : c ≠ 0) :
/-- Cancel left multiplication in the modulus.
For cancelling left multiplication on both sides of the `≡`, see `nat.modeq.mul_left_cancel'`. -/
-theorem of_mul_left (m : ℕ) (h : a ≡ b [MOD m * n]) : a ≡ b [MOD n] :=
- by
- rw [modeq_iff_dvd] at *
+theorem of_mul_left (m : ℕ) (h : a ≡ b [MOD m * n]) : a ≡ b [MOD n] := by rw [modeq_iff_dvd] at *;
exact (dvd_mul_left (n : ℤ) (m : ℤ)).trans h
#align nat.modeq.of_mul_left Nat.ModEq.of_mul_left
-/
@@ -412,9 +408,7 @@ theorem cancel_left_div_gcd (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) : a ≡ b
#print Nat.ModEq.cancel_right_div_gcd /-
theorem cancel_right_div_gcd (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m / gcd m c] :=
- by
- apply cancel_left_div_gcd hm
- simpa [mul_comm] using h
+ by apply cancel_left_div_gcd hm; simpa [mul_comm] using h
#align nat.modeq.cancel_right_div_gcd Nat.ModEq.cancel_right_div_gcd
-/
@@ -481,8 +475,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
Int.add_ediv_of_dvd_left, Int.mul_ediv_cancel_left _ hnonzero,
Int.mul_ediv_assoc _ h.dvd, ← sub_sub, sub_self, zero_sub, dvd_neg, mul_assoc]
exact dvd_mul_right _ _
- norm_cast
- exact dvd_mul_right _ _
+ norm_cast; exact dvd_mul_right _ _
· exact dvd_lcm_left n m
· rw [← sub_eq_iff_eq_add] at this
rw [← this, sub_mul, sub_add, ← mul_sub, Int.sub_ediv_of_dvd,
@@ -624,8 +617,7 @@ theorem add_div {a b c : ℕ} (hc0 : 0 < c) :
by simpa only [mul_add, add_comm, add_left_comm, add_assoc]
rw [mod_add_div, mod_add_div, mod_add_div, mul_ite, add_assoc, add_assoc]
conv_lhs => rw [← add_mod_add_ite]
- simp
- ac_rfl
+ simp; ac_rfl
#align nat.add_div Nat.add_div
#print Nat.add_div_eq_of_add_mod_lt /-
mathlib commit https://github.com/leanprover-community/mathlib/commit/06a655b5fcfbda03502f9158bbf6c0f1400886f9
@@ -293,9 +293,11 @@ theorem of_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] :=
#align nat.modeq.of_mul_right Nat.ModEq.of_mul_right
-/
+#print Nat.ModEq.of_div /-
theorem of_div (h : a / c ≡ b / c [MOD m / c]) (ha : c ∣ a) (ha : c ∣ b) (ha : c ∣ m) :
a ≡ b [MOD m] := by convert h.mul_left' c <;> rwa [Nat.mul_div_cancel']
#align nat.modeq.of_div Nat.ModEq.of_div
+-/
end Modeq
mathlib commit https://github.com/leanprover-community/mathlib/commit/3cacc945118c8c637d89950af01da78307f59325
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
! This file was ported from Lean 3 source module data.nat.modeq
-! leanprover-community/mathlib commit c0dbeca1a7a7f4959cdf6b2817629bafbf1547a0
+! leanprover-community/mathlib commit 47a1a73351de8dd6c8d3d32b569c8e434b03ca47
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -293,6 +293,10 @@ theorem of_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] :=
#align nat.modeq.of_mul_right Nat.ModEq.of_mul_right
-/
+theorem of_div (h : a / c ≡ b / c [MOD m / c]) (ha : c ∣ a) (ha : c ∣ b) (ha : c ∣ m) :
+ a ≡ b [MOD m] := by convert h.mul_left' c <;> rwa [Nat.mul_div_cancel']
+#align nat.modeq.of_div Nat.ModEq.of_div
+
end Modeq
#print Nat.modEq_sub /-
mathlib commit https://github.com/leanprover-community/mathlib/commit/da3fc4a33ff6bc75f077f691dc94c217b8d41559
@@ -106,7 +106,7 @@ theorem Dvd.dvd.zero_modEq_nat (h : n ∣ a) : 0 ≡ a [MOD n] :=
lean 3 declaration is
forall {n : Nat} {a : Nat} {b : Nat}, Iff (Nat.ModEq n a b) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a)))
but is expected to have type
- forall {n : Nat} {a : Nat} {b : Nat}, Iff (Nat.ModEq n a b) (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt a)))
+ forall {n : Nat} {a : Nat} {b : Nat}, Iff (Nat.ModEq n a b) (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a)))
Case conversion may be inaccurate. Consider using '#align nat.modeq_iff_dvd Nat.modEq_iff_dvdₓ'. -/
theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
rw [modeq, eq_comm, ← Int.coe_nat_inj', Int.coe_nat_mod, Int.coe_nat_mod,
@@ -117,13 +117,13 @@ theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
lean 3 declaration is
forall {n : Nat} {a : Nat} {b : Nat}, (Nat.ModEq n a b) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a)))
but is expected to have type
- forall {n : Nat} {a : Nat} {b : Nat}, (Nat.ModEq n a b) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt a)))
+ forall {n : Nat} {a : Nat} {b : Nat}, (Nat.ModEq n a b) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a)))
Case conversion may be inaccurate. Consider using '#align nat.modeq.dvd Nat.ModEq.dvdₓ'. -/
/- warning: nat.modeq_of_dvd -> Nat.modEq_of_dvd is a dubious translation:
lean 3 declaration is
forall {n : Nat} {a : Nat} {b : Nat}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a))) -> (Nat.ModEq n a b)
but is expected to have type
- forall {n : Nat} {a : Nat} {b : Nat}, (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt a))) -> (Nat.ModEq n a b)
+ forall {n : Nat} {a : Nat} {b : Nat}, (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt n) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a))) -> (Nat.ModEq n a b)
Case conversion may be inaccurate. Consider using '#align nat.modeq_of_dvd Nat.modEq_of_dvdₓ'. -/
alias modeq_iff_dvd ↔ modeq.dvd modeq_of_dvd
#align nat.modeq.dvd Nat.ModEq.dvd
@@ -365,7 +365,7 @@ theorem gcd_eq (h : a ≡ b [MOD m]) : gcd a m = gcd b m :=
lean 3 declaration is
forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.hasLt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.hasNeg (SemilatticeSup.toHasSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (LinearOrder.toLattice.{0} Int Int.linearOrder)))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a))) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) m)) -> (Eq.{1} Nat a b)
but is expected to have type
- forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.instLTInt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.instNegInt (SemilatticeSup.toSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (DistribLattice.toLattice.{0} Int (instDistribLattice.{0} Int Int.instLinearOrderInt))))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt a))) (Nat.cast.{0} Int Int.instNatCastInt m)) -> (Eq.{1} Nat a b)
+ forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.instLTInt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.instNegInt (SemilatticeSup.toSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (DistribLattice.toLattice.{0} Int (instDistribLattice.{0} Int Int.instLinearOrderInt))))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int instNatCastInt b) (Nat.cast.{0} Int instNatCastInt a))) (Nat.cast.{0} Int instNatCastInt m)) -> (Eq.{1} Nat a b)
Case conversion may be inaccurate. Consider using '#align nat.modeq.eq_of_abs_lt Nat.ModEq.eq_of_abs_ltₓ'. -/
theorem eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b - a : ℤ)| < m) : a = b :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212
@@ -533,7 +533,7 @@ theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n])
calc
1 ≡ a * b [MOD a.gcd n] := Nat.ModEq.of_mul_right g (hh.subst h).symm
_ ≡ 0 * b [MOD a.gcd n] := ((nat.modeq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).mul_right b)
- _ = 0 := by rw [zero_mul]
+ _ = 0 := by rw [MulZeroClass.zero_mul]
#align nat.coprime_of_mul_modeq_one Nat.coprime_of_mul_modEq_one
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442
@@ -532,7 +532,7 @@ theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n])
rw [Nat.coprime_iff_gcd_eq_one, ← Nat.dvd_one, ← Nat.modEq_zero_iff_dvd]
calc
1 ≡ a * b [MOD a.gcd n] := Nat.ModEq.of_mul_right g (hh.subst h).symm
- _ ≡ 0 * b [MOD a.gcd n] := (nat.modeq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).mul_right b
+ _ ≡ 0 * b [MOD a.gcd n] := ((nat.modeq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).mul_right b)
_ = 0 := by rw [zero_mul]
#align nat.coprime_of_mul_modeq_one Nat.coprime_of_mul_modEq_one
mathlib commit https://github.com/leanprover-community/mathlib/commit/9da1b3534b65d9661eb8f42443598a92bbb49211
@@ -365,7 +365,7 @@ theorem gcd_eq (h : a ≡ b [MOD m]) : gcd a m = gcd b m :=
lean 3 declaration is
forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.hasLt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.hasNeg (SemilatticeSup.toHasSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (LinearOrder.toLattice.{0} Int Int.linearOrder)))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.hasSub) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) b) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) a))) ((fun (a : Type) (b : Type) [self : HasLiftT.{1, 1} a b] => self.0) Nat Int (HasLiftT.mk.{1, 1} Nat Int (CoeTCₓ.coe.{1, 1} Nat Int (coeBase.{1, 1} Nat Int Int.hasCoe))) m)) -> (Eq.{1} Nat a b)
but is expected to have type
- forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.instLTInt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.instNegInt (SemilatticeSup.toHasSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (DistribLattice.toLattice.{0} Int (instDistribLattice.{0} Int Int.instLinearOrderInt))))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt a))) (Nat.cast.{0} Int Int.instNatCastInt m)) -> (Eq.{1} Nat a b)
+ forall {m : Nat} {a : Nat} {b : Nat}, (Nat.ModEq m a b) -> (LT.lt.{0} Int Int.instLTInt (Abs.abs.{0} Int (Neg.toHasAbs.{0} Int Int.instNegInt (SemilatticeSup.toSup.{0} Int (Lattice.toSemilatticeSup.{0} Int (DistribLattice.toLattice.{0} Int (instDistribLattice.{0} Int Int.instLinearOrderInt))))) (HSub.hSub.{0, 0, 0} Int Int Int (instHSub.{0} Int Int.instSubInt) (Nat.cast.{0} Int Int.instNatCastInt b) (Nat.cast.{0} Int Int.instNatCastInt a))) (Nat.cast.{0} Int Int.instNatCastInt m)) -> (Eq.{1} Nat a b)
Case conversion may be inaccurate. Consider using '#align nat.modeq.eq_of_abs_lt Nat.ModEq.eq_of_abs_ltₓ'. -/
theorem eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b - a : ℤ)| < m) : a = b :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -286,13 +286,13 @@ lemma cancel_left_div_gcd (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) : a ≡ b
have hcd := gcd_dvd_right m c
rw [modEq_iff_dvd]
refine' @Int.dvd_of_dvd_mul_right_of_gcd_one (m / d) (c / d) (b - a) _ _
- show (m / d : ℤ) ∣ c / d * (b - a)
- · rw [mul_comm, ← Int.mul_ediv_assoc (b - a) (Int.natCast_dvd_natCast.mpr hcd), mul_comm]
+ · show (m / d : ℤ) ∣ c / d * (b - a)
+ rw [mul_comm, ← Int.mul_ediv_assoc (b - a) (Int.natCast_dvd_natCast.mpr hcd), mul_comm]
apply Int.ediv_dvd_ediv (Int.natCast_dvd_natCast.mpr hmd)
rw [mul_sub]
exact modEq_iff_dvd.mp h
- show Int.gcd (m / d) (c / d) = 1
- · simp only [← Int.natCast_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
+ · show Int.gcd (m / d) (c / d) = 1
+ simp only [← Int.natCast_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
Nat.div_self (gcd_pos_of_pos_left c hm)]
#align nat.modeq.cancel_left_div_gcd Nat.ModEq.cancel_left_div_gcd
@@ -331,9 +331,15 @@ end ModEq
/-- The natural number less than `lcm n m` congruent to `a` mod `n` and `b` mod `m` -/
def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
- if hn : n = 0 then ⟨a, by rw [hn, gcd_zero_left] at h; constructor; rfl; exact h⟩
+ if hn : n = 0 then ⟨a, by
+ rw [hn, gcd_zero_left] at h; constructor
+ · rfl
+ · exact h⟩
else
- if hm : m = 0 then ⟨b, by rw [hm, gcd_zero_right] at h; constructor; exact h.symm; rfl⟩
+ if hm : m = 0 then ⟨b, by
+ rw [hm, gcd_zero_right] at h; constructor
+ · exact h.symm
+ · rfl⟩
else
⟨let (c, d) := xgcd n m; Int.toNat ((n * c * b + m * d * a) / gcd n m % lcm n m), by
rw [xgcd_val]
@@ -353,7 +359,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
rw [← this, sub_mul, ← add_sub_assoc, add_comm, add_sub_assoc, ← mul_sub,
Int.add_ediv_of_dvd_left, Int.mul_ediv_cancel_left _ hnonzero,
Int.mul_ediv_assoc _ h.dvd, ← sub_sub, sub_self, zero_sub, dvd_neg, mul_assoc]
- exact dvd_mul_right _ _
+ · exact dvd_mul_right _ _
norm_cast
exact dvd_mul_right _ _
· exact dvd_lcm_left n m
@@ -361,8 +367,8 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
rw [← this, sub_mul, sub_add, ← mul_sub, Int.sub_ediv_of_dvd,
Int.mul_ediv_cancel_left _ hnonzero, Int.mul_ediv_assoc _ h.dvd, ← sub_add, sub_self,
zero_add, mul_assoc]
- exact dvd_mul_right _ _
- exact hcoedvd _
+ · exact dvd_mul_right _ _
+ · exact hcoedvd _
· exact dvd_lcm_right n m⟩
#align nat.chinese_remainder' Nat.chineseRemainder'
@@ -375,7 +375,7 @@ theorem chineseRemainder'_lt_lcm (h : a ≡ b [MOD gcd n m]) (hn : n ≠ 0) (hm
↑(chineseRemainder' h) < lcm n m := by
dsimp only [chineseRemainder']
rw [dif_neg hn, dif_neg hm, Subtype.coe_mk, xgcd_val, ← Int.toNat_natCast (lcm n m)]
- have lcm_pos := Int.coe_nat_pos.mpr (Nat.pos_of_ne_zero (lcm_ne_zero hn hm))
+ have lcm_pos := Int.natCast_pos.mpr (Nat.pos_of_ne_zero (lcm_ne_zero hn hm))
exact (Int.toNat_lt_toNat lcm_pos).mpr (Int.emod_lt_of_pos _ lcm_pos)
#align nat.chinese_remainder'_lt_lcm Nat.chineseRemainder'_lt_lcm
@@ -3,11 +3,10 @@ Copyright (c) 2017 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-/
+import Mathlib.Data.Int.Cast.Lemmas
import Mathlib.Data.Int.GCD
import Mathlib.Data.Int.Order.Lemmas
-import Mathlib.Logic.Basic
-import Mathlib.Tactic.NormNum
-import Mathlib.Tactic.GCongr.Core
+import Mathlib.Tactic.NormNum.Basic
#align_import data.nat.modeq from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
@@ -27,6 +26,7 @@ and proves basic properties about it such as the Chinese Remainder Theorem
ModEq, congruence, mod, MOD, modulo
-/
+assert_not_exists Function.support
namespace Nat
coe_nat
to natCast
(#11637)
Reduce the diff of #11499
All in the Int
namespace:
ofNat_eq_cast
→ ofNat_eq_natCast
cast_eq_cast_iff_Nat
→ natCast_inj
natCast_eq_ofNat
→ ofNat_eq_natCast
coe_nat_sub
→ natCast_sub
coe_nat_nonneg
→ natCast_nonneg
sign_coe_add_one
→ sign_natCast_add_one
nat_succ_eq_int_succ
→ natCast_succ
succ_neg_nat_succ
→ succ_neg_natCast_succ
coe_pred_of_pos
→ natCast_pred_of_pos
coe_nat_div
→ natCast_div
coe_nat_ediv
→ natCast_ediv
sign_coe_nat_of_nonzero
→ sign_natCast_of_ne_zero
toNat_coe_nat
→ toNat_natCast
toNat_coe_nat_add_one
→ toNat_natCast_add_one
coe_nat_dvd
→ natCast_dvd_natCast
coe_nat_dvd_left
→ natCast_dvd
coe_nat_dvd_right
→ dvd_natCast
le_coe_nat_sub
→ le_natCast_sub
succ_coe_nat_pos
→ succ_natCast_pos
coe_nat_modEq_iff
→ natCast_modEq_iff
coe_natAbs
→ natCast_natAbs
coe_nat_eq_zero
→ natCast_eq_zero
coe_nat_ne_zero
→ natCast_ne_zero
coe_nat_ne_zero_iff_pos
→ natCast_ne_zero_iff_pos
abs_coe_nat
→ abs_natCast
coe_nat_nonpos_iff
→ natCast_nonpos_iff
Also rename Nat.coe_nat_dvd
to Nat.cast_dvd_cast
@@ -87,7 +87,7 @@ theorem _root_.Dvd.dvd.zero_modEq_nat (h : n ∣ a) : 0 ≡ a [MOD n] :=
#align has_dvd.dvd.zero_modeq_nat Dvd.dvd.zero_modEq_nat
theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
- rw [ModEq, eq_comm, ← Int.coe_nat_inj', Int.coe_nat_mod, Int.coe_nat_mod,
+ rw [ModEq, eq_comm, ← Int.natCast_inj, Int.natCast_mod, Int.natCast_mod,
Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.dvd_iff_emod_eq_zero]
#align nat.modeq_iff_dvd Nat.modEq_iff_dvd
@@ -97,7 +97,7 @@ alias ⟨ModEq.dvd, modEq_of_dvd⟩ := modEq_iff_dvd
/-- A variant of `modEq_iff_dvd` with `Nat` divisibility -/
theorem modEq_iff_dvd' (h : a ≤ b) : a ≡ b [MOD n] ↔ n ∣ b - a := by
- rw [modEq_iff_dvd, ← Int.coe_nat_dvd, Int.ofNat_sub h]
+ rw [modEq_iff_dvd, ← Int.natCast_dvd_natCast, Int.ofNat_sub h]
#align nat.modeq_iff_dvd' Nat.modEq_iff_dvd'
theorem mod_modEq (a n) : a % n ≡ a [MOD n] :=
@@ -275,8 +275,8 @@ lemma eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b : ℤ) - a| < m) : a = b := b
lemma eq_of_lt_of_lt (h : a ≡ b [MOD m]) (ha : a < m) (hb : b < m) : a = b :=
h.eq_of_abs_lt <| abs_sub_lt_iff.2
- ⟨(sub_le_self _ <| Int.coe_nat_nonneg _).trans_lt <| Int.ofNat_lt.2 hb,
- (sub_le_self _ <| Int.coe_nat_nonneg _).trans_lt <| Int.ofNat_lt.2 ha⟩
+ ⟨(sub_le_self _ <| Int.natCast_nonneg _).trans_lt <| Int.ofNat_lt.2 hb,
+ (sub_le_self _ <| Int.natCast_nonneg _).trans_lt <| Int.ofNat_lt.2 ha⟩
#align nat.modeq.eq_of_lt_of_lt Nat.ModEq.eq_of_lt_of_lt
/-- To cancel a common factor `c` from a `ModEq` we must divide the modulus `m` by `gcd m c` -/
@@ -287,12 +287,12 @@ lemma cancel_left_div_gcd (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) : a ≡ b
rw [modEq_iff_dvd]
refine' @Int.dvd_of_dvd_mul_right_of_gcd_one (m / d) (c / d) (b - a) _ _
show (m / d : ℤ) ∣ c / d * (b - a)
- · rw [mul_comm, ← Int.mul_ediv_assoc (b - a) (Int.coe_nat_dvd.mpr hcd), mul_comm]
- apply Int.ediv_dvd_ediv (Int.coe_nat_dvd.mpr hmd)
+ · rw [mul_comm, ← Int.mul_ediv_assoc (b - a) (Int.natCast_dvd_natCast.mpr hcd), mul_comm]
+ apply Int.ediv_dvd_ediv (Int.natCast_dvd_natCast.mpr hmd)
rw [mul_sub]
exact modEq_iff_dvd.mp h
show Int.gcd (m / d) (c / d) = 1
- · simp only [← Int.coe_nat_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
+ · simp only [← Int.natCast_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
Nat.div_self (gcd_pos_of_pos_left c hm)]
#align nat.modeq.cancel_left_div_gcd Nat.ModEq.cancel_left_div_gcd
@@ -339,7 +339,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
rw [xgcd_val]
dsimp
rw [modEq_iff_dvd, modEq_iff_dvd,
- Int.toNat_of_nonneg (Int.emod_nonneg _ (Int.coe_nat_ne_zero.2 (lcm_ne_zero hn hm)))]
+ Int.toNat_of_nonneg (Int.emod_nonneg _ (Int.natCast_ne_zero.2 (lcm_ne_zero hn hm)))]
have hnonzero : (gcd n m : ℤ) ≠ 0 := by
norm_cast
rw [Nat.gcd_eq_zero_iff, not_and]
@@ -374,7 +374,7 @@ def chineseRemainder (co : n.Coprime m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧
theorem chineseRemainder'_lt_lcm (h : a ≡ b [MOD gcd n m]) (hn : n ≠ 0) (hm : m ≠ 0) :
↑(chineseRemainder' h) < lcm n m := by
dsimp only [chineseRemainder']
- rw [dif_neg hn, dif_neg hm, Subtype.coe_mk, xgcd_val, ← Int.toNat_coe_nat (lcm n m)]
+ rw [dif_neg hn, dif_neg hm, Subtype.coe_mk, xgcd_val, ← Int.toNat_natCast (lcm n m)]
have lcm_pos := Int.coe_nat_pos.mpr (Nat.pos_of_ne_zero (lcm_ne_zero hn hm))
exact (Int.toNat_lt_toNat lcm_pos).mpr (Int.emod_lt_of_pos _ lcm_pos)
#align nat.chinese_remainder'_lt_lcm Nat.chineseRemainder'_lt_lcm
@@ -396,9 +396,9 @@ theorem chineseRemainder_modEq_unique (co : n.Coprime m) {a b z}
theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.Coprime n) :
a ≡ b [MOD m] ∧ a ≡ b [MOD n] ↔ a ≡ b [MOD m * n] :=
⟨fun h => by
- rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
- Int.coe_nat_dvd] at h
- rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd]
+ rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.natCast_dvd_natCast,
+ ← Int.dvd_natAbs, Int.natCast_dvd_natCast] at h
+ rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.natCast_dvd_natCast]
exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2,
fun h => ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
mul
-div
cancellation lemmas (#11530)
Lemma names around cancellation of multiplication and division are a mess.
This PR renames a handful of them according to the following table (each big row contains the multiplicative statement, then the three rows contain the GroupWithZero
lemma name, the Group
lemma, the AddGroup
lemma name).
| Statement | New name | Old name | |
@@ -163,7 +163,7 @@ protected theorem add_left_cancel (h₁ : a ≡ b [MOD n]) (h₂ : a + c ≡ b +
simp only [modEq_iff_dvd, Int.ofNat_add] at *
rw [add_sub_add_comm] at h₂
convert _root_.dvd_sub h₂ h₁ using 1
- rw [add_sub_cancel']
+ rw [add_sub_cancel_left]
#align nat.modeq.add_left_cancel Nat.ModEq.add_left_cancel
protected theorem add_left_cancel' (c : ℕ) (h : c + a ≡ c + b [MOD n]) : a ≡ b [MOD n] :=
@@ -385,7 +385,7 @@ theorem chineseRemainder_lt_mul (co : n.Coprime m) (a b : ℕ) (hn : n ≠ 0) (h
#align nat.chinese_remainder_lt_mul Nat.chineseRemainder_lt_mul
theorem mod_lcm (hn : a ≡ b [MOD n]) (hm : a ≡ b [MOD m]) : a ≡ b [MOD lcm n m] :=
- (Nat.modEq_iff_dvd).mpr <| Int.lcm_dvd (Nat.modEq_iff_dvd.mp hn) (Nat.modEq_iff_dvd.mp hm)
+ Nat.modEq_iff_dvd.mpr <| Int.lcm_dvd (Nat.modEq_iff_dvd.mp hn) (Nat.modEq_iff_dvd.mp hm)
theorem chineseRemainder_modEq_unique (co : n.Coprime m) {a b z}
(hzan : z ≡ a [MOD n]) (hzbm : z ≡ b [MOD m]) : z ≡ chineseRemainder co a b [MOD n*m] := by
@@ -399,8 +399,8 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.Coprime n) :
rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
Int.coe_nat_dvd] at h
rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd]
- exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2, fun h =>
- ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
+ exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2,
+ fun h => ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.Coprime n := by
This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0
branch as we update to intermediate nightlies.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>
@@ -138,7 +138,7 @@ protected theorem pow (m : ℕ) (h : a ≡ b [MOD n]) : a ^ m ≡ b ^ m [MOD n]
induction m with
| zero => rfl
| succ d hd =>
- rw[pow_succ, pow_succ]
+ rw [Nat.pow_succ, Nat.pow_succ]
exact hd.mul h
#align nat.modeq.pow Nat.ModEq.pow
@@ -412,14 +412,7 @@ theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n])
_ = 0 := by rw [zero_mul]
#align nat.coprime_of_mul_modeq_one Nat.coprime_of_mul_modEq_one
-@[simp 1100]
-theorem mod_mul_right_mod (a b c : ℕ) : a % (b * c) % b = a % b :=
- (mod_modEq _ _).of_mul_right _
#align nat.mod_mul_right_mod Nat.mod_mul_right_mod
-
-@[simp 1100]
-theorem mod_mul_left_mod (a b c : ℕ) : a % (b * c) % c = a % c :=
- (mod_modEq _ _).of_mul_left _
#align nat.mod_mul_left_mod Nat.mod_mul_left_mod
theorem div_mod_eq_mod_mul_div (a b c : ℕ) : a / b % c = a % (b * c) / b :=
This file proves Gödel's Beta Function Lemma, used to prove the First Incompleteness Theorem. This code is a step towards eventually including a proof of Gödel's First Incompleteness Theorem and other key results from the repository https://github.com/iehality/lean4-logic.
Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: jeh <hodellurt@gmail.com> Co-authored-by: Palalansoukî <palalansouki@gmail.com> Co-authored-by: palalansouki <palalansouki@gmail.com>
@@ -384,6 +384,15 @@ theorem chineseRemainder_lt_mul (co : n.Coprime m) (a b : ℕ) (hn : n ≠ 0) (h
lt_of_lt_of_le (chineseRemainder'_lt_lcm _ hn hm) (le_of_eq co.lcm_eq_mul)
#align nat.chinese_remainder_lt_mul Nat.chineseRemainder_lt_mul
+theorem mod_lcm (hn : a ≡ b [MOD n]) (hm : a ≡ b [MOD m]) : a ≡ b [MOD lcm n m] :=
+ (Nat.modEq_iff_dvd).mpr <| Int.lcm_dvd (Nat.modEq_iff_dvd.mp hn) (Nat.modEq_iff_dvd.mp hm)
+
+theorem chineseRemainder_modEq_unique (co : n.Coprime m) {a b z}
+ (hzan : z ≡ a [MOD n]) (hzbm : z ≡ b [MOD m]) : z ≡ chineseRemainder co a b [MOD n*m] := by
+ simpa [Nat.Coprime.lcm_eq_mul co] using
+ mod_lcm (hzan.trans ((chineseRemainder co a b).prop.1).symm)
+ (hzbm.trans ((chineseRemainder co a b).prop.2).symm)
+
theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.Coprime n) :
a ≡ b [MOD m] ∧ a ≡ b [MOD n] ↔ a ≡ b [MOD m * n] :=
⟨fun h => by
@@ -532,4 +541,5 @@ theorem odd_mod_four_iff {n : ℕ} : n % 2 = 1 ↔ n % 4 = 1 ∨ n % 4 = 3 :=
fun h => Or.elim h odd_of_mod_four_eq_one odd_of_mod_four_eq_three⟩
#align nat.odd_mod_four_iff Nat.odd_mod_four_iff
-end Nat
+lemma mod_eq_of_modEq {a b n} (h : a ≡ b [MOD n]) (hb : b < n) : a % n = b :=
+ Eq.trans h (mod_eq_of_lt hb)
@@ -5,6 +5,7 @@ Authors: Mario Carneiro
-/
import Mathlib.Data.Int.GCD
import Mathlib.Data.Int.Order.Lemmas
+import Mathlib.Logic.Basic
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.GCongr.Core
$
with <|
(#9319)
See Zulip thread for the discussion.
@@ -105,7 +105,8 @@ theorem mod_modEq (a n) : a % n ≡ a [MOD n] :=
namespace ModEq
-lemma of_dvd (d : m ∣ n) (h : a ≡ b [MOD n]) : a ≡ b [MOD m] := modEq_of_dvd $ d.natCast.trans h.dvd
+lemma of_dvd (d : m ∣ n) (h : a ≡ b [MOD n]) : a ≡ b [MOD m] :=
+ modEq_of_dvd <| d.natCast.trans h.dvd
#align nat.modeq.of_dvd Nat.ModEq.of_dvd
protected theorem mul_left' (c : ℕ) (h : a ≡ b [MOD n]) : c * a ≡ c * b [MOD c * n] := by
@@ -224,10 +225,10 @@ theorem of_div (h : a / c ≡ b / c [MOD m / c]) (ha : c ∣ a) (ha : c ∣ b) (
end ModEq
-lemma modEq_sub (h : b ≤ a) : a ≡ b [MOD a - b] := (modEq_of_dvd $ by rw [Int.ofNat_sub h]).symm
+lemma modEq_sub (h : b ≤ a) : a ≡ b [MOD a - b] := (modEq_of_dvd <| by rw [Int.ofNat_sub h]).symm
#align nat.modeq_sub Nat.modEq_sub
-lemma modEq_one : a ≡ b [MOD 1] := modEq_of_dvd $ one_dvd _
+lemma modEq_one : a ≡ b [MOD 1] := modEq_of_dvd <| one_dvd _
#align nat.modeq_one Nat.modEq_one
@[simp] lemma modEq_zero_iff : a ≡ b [MOD 0] ↔ a = b := by rw [ModEq, mod_zero, mod_zero]
@@ -272,9 +273,9 @@ lemma eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b : ℤ) - a| < m) : a = b := b
#align nat.modeq.eq_of_abs_lt Nat.ModEq.eq_of_abs_lt
lemma eq_of_lt_of_lt (h : a ≡ b [MOD m]) (ha : a < m) (hb : b < m) : a = b :=
- h.eq_of_abs_lt $ abs_sub_lt_iff.2
- ⟨(sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 hb,
- (sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 ha⟩
+ h.eq_of_abs_lt <| abs_sub_lt_iff.2
+ ⟨(sub_le_self _ <| Int.coe_nat_nonneg _).trans_lt <| Int.ofNat_lt.2 hb,
+ (sub_le_self _ <| Int.coe_nat_nonneg _).trans_lt <| Int.ofNat_lt.2 ha⟩
#align nat.modeq.eq_of_lt_of_lt Nat.ModEq.eq_of_lt_of_lt
/-- To cancel a common factor `c` from a `ModEq` we must divide the modulus `m` by `gcd m c` -/
@@ -302,12 +303,12 @@ lemma cancel_right_div_gcd (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) : a ≡ b
lemma cancel_left_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : c * a ≡ d * b [MOD m]) :
a ≡ b [MOD m / gcd m c] :=
- (h.trans $ hcd.symm.mul_right b).cancel_left_div_gcd hm
+ (h.trans <| hcd.symm.mul_right b).cancel_left_div_gcd hm
#align nat.modeq.cancel_left_div_gcd' Nat.ModEq.cancel_left_div_gcd'
lemma cancel_right_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : a * c ≡ b * d [MOD m]) :
a ≡ b [MOD m / gcd m c] :=
- (h.trans $ hcd.symm.mul_left b).cancel_right_div_gcd hm
+ (h.trans <| hcd.symm.mul_left b).cancel_right_div_gcd hm
#align nat.modeq.cancel_right_div_gcd' Nat.ModEq.cancel_right_div_gcd'
/-- A common factor that's coprime with the modulus can be cancelled from a `ModEq` -/
@@ -322,7 +323,7 @@ lemma cancel_left_of_coprime (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) :
/-- A common factor that's coprime with the modulus can be cancelled from a `ModEq` -/
lemma cancel_right_of_coprime (hmc : gcd m c = 1) (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m] :=
- cancel_left_of_coprime hmc $ by simpa [mul_comm] using h
+ cancel_left_of_coprime hmc <| by simpa [mul_comm] using h
#align nat.modeq.cancel_right_of_coprime Nat.ModEq.cancel_right_of_coprime
end ModEq
This is the supremum of
along with some minor fixes from failures on nightly-testing as Mathlib master
is merged into it.
Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.
I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0
branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.
In particular this includes adjustments for the Lean PRs
We can get rid of all the
local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)
macros across Mathlib (and in any projects that want to write natural number powers of reals).
Changes the default behaviour of simp
to (config := {decide := false})
. This makes simp
(and consequentially norm_num
) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp
or norm_num
to decide
or rfl
, or adding (config := {decide := true})
.
This changed the behaviour of simp
so that simp [f]
will only unfold "fully applied" occurrences of f
. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true })
. We may in future add a syntax for this, e.g. simp [!f]
; please provide feedback! In the meantime, we have made the following changes:
(config := { unfoldPartialApp := true })
in some places, to recover the old behaviour@[eqns]
to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp
and Function.flip
.This change in Lean may require further changes down the line (e.g. adding the !f
syntax, and/or upstreaming the special treatment for Function.comp
and Function.flip
, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>
@@ -526,7 +526,7 @@ theorem odd_of_mod_four_eq_three {n : ℕ} : n % 4 = 3 → n % 2 = 1 := by
theorem odd_mod_four_iff {n : ℕ} : n % 2 = 1 ↔ n % 4 = 1 ∨ n % 4 = 3 :=
have help : ∀ m : ℕ, m < 4 → m % 2 = 1 → m = 1 ∨ m = 3 := by decide
⟨fun hn =>
- help (n % 4) (mod_lt n (by norm_num)) <| (mod_mod_of_dvd n (by norm_num : 2 ∣ 4)).trans hn,
+ help (n % 4) (mod_lt n (by norm_num)) <| (mod_mod_of_dvd n (by decide : 2 ∣ 4)).trans hn,
fun h => Or.elim h odd_of_mod_four_eq_one odd_of_mod_four_eq_three⟩
#align nat.odd_mod_four_iff Nat.odd_mod_four_iff
@@ -458,7 +458,7 @@ theorem add_div {a b c : ℕ} (hc0 : 0 < c) :
by simpa only [mul_add, add_comm, add_left_comm, add_assoc]
rw [mod_add_div, mod_add_div, mod_add_div, mul_ite, add_assoc, add_assoc]
conv_lhs => rw [← add_mod_add_ite]
- simp
+ simp only [mul_one, mul_zero]
ac_rfl
#align nat.add_div Nat.add_div
@@ -302,12 +302,12 @@ lemma cancel_right_div_gcd (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) : a ≡ b
lemma cancel_left_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : c * a ≡ d * b [MOD m]) :
a ≡ b [MOD m / gcd m c] :=
-(h.trans $ hcd.symm.mul_right b).cancel_left_div_gcd hm
+ (h.trans $ hcd.symm.mul_right b).cancel_left_div_gcd hm
#align nat.modeq.cancel_left_div_gcd' Nat.ModEq.cancel_left_div_gcd'
lemma cancel_right_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : a * c ≡ b * d [MOD m]) :
a ≡ b [MOD m / gcd m c] :=
-(h.trans $ hcd.symm.mul_left b).cancel_right_div_gcd hm
+ (h.trans $ hcd.symm.mul_left b).cancel_right_div_gcd hm
#align nat.modeq.cancel_right_div_gcd' Nat.ModEq.cancel_right_div_gcd'
/-- A common factor that's coprime with the modulus can be cancelled from a `ModEq` -/
@@ -301,12 +301,12 @@ lemma cancel_right_div_gcd (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) : a ≡ b
#align nat.modeq.cancel_right_div_gcd Nat.ModEq.cancel_right_div_gcd
lemma cancel_left_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : c * a ≡ d * b [MOD m]) :
- a ≡ b [MOD m / gcd m c] :=
+ a ≡ b [MOD m / gcd m c] :=
(h.trans $ hcd.symm.mul_right b).cancel_left_div_gcd hm
#align nat.modeq.cancel_left_div_gcd' Nat.ModEq.cancel_left_div_gcd'
lemma cancel_right_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : a * c ≡ b * d [MOD m]) :
- a ≡ b [MOD m / gcd m c] :=
+ a ≡ b [MOD m / gcd m c] :=
(h.trans $ hcd.symm.mul_left b).cancel_right_div_gcd hm
#align nat.modeq.cancel_right_div_gcd' Nat.ModEq.cancel_right_div_gcd'
@@ -365,7 +365,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
#align nat.chinese_remainder' Nat.chineseRemainder'
/-- The natural number less than `n*m` congruent to `a` mod `n` and `b` mod `m` -/
-def chineseRemainder (co : n.coprime m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
+def chineseRemainder (co : n.Coprime m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
chineseRemainder' (by convert @modEq_one a b)
#align nat.chinese_remainder Nat.chineseRemainder
@@ -377,12 +377,12 @@ theorem chineseRemainder'_lt_lcm (h : a ≡ b [MOD gcd n m]) (hn : n ≠ 0) (hm
exact (Int.toNat_lt_toNat lcm_pos).mpr (Int.emod_lt_of_pos _ lcm_pos)
#align nat.chinese_remainder'_lt_lcm Nat.chineseRemainder'_lt_lcm
-theorem chineseRemainder_lt_mul (co : n.coprime m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
+theorem chineseRemainder_lt_mul (co : n.Coprime m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
↑(chineseRemainder co a b) < n * m :=
lt_of_lt_of_le (chineseRemainder'_lt_lcm _ hn hm) (le_of_eq co.lcm_eq_mul)
#align nat.chinese_remainder_lt_mul Nat.chineseRemainder_lt_mul
-theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.coprime n) :
+theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.Coprime n) :
a ≡ b [MOD m] ∧ a ≡ b [MOD n] ↔ a ≡ b [MOD m * n] :=
⟨fun h => by
rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
@@ -392,7 +392,7 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.coprime n) :
⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
-theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.coprime n := by
+theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.Coprime n := by
obtain ⟨g, hh⟩ := Nat.gcd_dvd_right a n
rw [Nat.coprime_iff_gcd_eq_one, ← Nat.dvd_one, ← Nat.modEq_zero_iff_dvd]
calc
@@ -365,7 +365,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
#align nat.chinese_remainder' Nat.chineseRemainder'
/-- The natural number less than `n*m` congruent to `a` mod `n` and `b` mod `m` -/
-def chineseRemainder (co : n.Coprime m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
+def chineseRemainder (co : n.coprime m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
chineseRemainder' (by convert @modEq_one a b)
#align nat.chinese_remainder Nat.chineseRemainder
@@ -377,12 +377,12 @@ theorem chineseRemainder'_lt_lcm (h : a ≡ b [MOD gcd n m]) (hn : n ≠ 0) (hm
exact (Int.toNat_lt_toNat lcm_pos).mpr (Int.emod_lt_of_pos _ lcm_pos)
#align nat.chinese_remainder'_lt_lcm Nat.chineseRemainder'_lt_lcm
-theorem chineseRemainder_lt_mul (co : n.Coprime m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
+theorem chineseRemainder_lt_mul (co : n.coprime m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
↑(chineseRemainder co a b) < n * m :=
lt_of_lt_of_le (chineseRemainder'_lt_lcm _ hn hm) (le_of_eq co.lcm_eq_mul)
#align nat.chinese_remainder_lt_mul Nat.chineseRemainder_lt_mul
-theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.Coprime n) :
+theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.coprime n) :
a ≡ b [MOD m] ∧ a ≡ b [MOD n] ↔ a ≡ b [MOD m * n] :=
⟨fun h => by
rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
@@ -392,7 +392,7 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.Coprime n) :
⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
-theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.Coprime n := by
+theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.coprime n := by
obtain ⟨g, hh⟩ := Nat.gcd_dvd_right a n
rw [Nat.coprime_iff_gcd_eq_one, ← Nat.dvd_one, ← Nat.modEq_zero_iff_dvd]
calc
Some changes have already been review and delegated in #6910 and #7148.
The diff that needs looking at is https://github.com/leanprover-community/mathlib4/pull/7174/commits/64d6d07ee18163627c8f517eb31455411921c5ac
The std bump PR was insta-merged already!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -365,7 +365,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
#align nat.chinese_remainder' Nat.chineseRemainder'
/-- The natural number less than `n*m` congruent to `a` mod `n` and `b` mod `m` -/
-def chineseRemainder (co : n.coprime m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
+def chineseRemainder (co : n.Coprime m) (a b : ℕ) : { k // k ≡ a [MOD n] ∧ k ≡ b [MOD m] } :=
chineseRemainder' (by convert @modEq_one a b)
#align nat.chinese_remainder Nat.chineseRemainder
@@ -377,12 +377,12 @@ theorem chineseRemainder'_lt_lcm (h : a ≡ b [MOD gcd n m]) (hn : n ≠ 0) (hm
exact (Int.toNat_lt_toNat lcm_pos).mpr (Int.emod_lt_of_pos _ lcm_pos)
#align nat.chinese_remainder'_lt_lcm Nat.chineseRemainder'_lt_lcm
-theorem chineseRemainder_lt_mul (co : n.coprime m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
+theorem chineseRemainder_lt_mul (co : n.Coprime m) (a b : ℕ) (hn : n ≠ 0) (hm : m ≠ 0) :
↑(chineseRemainder co a b) < n * m :=
lt_of_lt_of_le (chineseRemainder'_lt_lcm _ hn hm) (le_of_eq co.lcm_eq_mul)
#align nat.chinese_remainder_lt_mul Nat.chineseRemainder_lt_mul
-theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.coprime n) :
+theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.Coprime n) :
a ≡ b [MOD m] ∧ a ≡ b [MOD n] ↔ a ≡ b [MOD m * n] :=
⟨fun h => by
rw [Nat.modEq_iff_dvd, Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd, ← Int.dvd_natAbs,
@@ -392,7 +392,7 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.coprime n) :
⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
-theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.coprime n := by
+theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.Coprime n := by
obtain ⟨g, hh⟩ := Nat.gcd_dvd_right a n
rw [Nat.coprime_iff_gcd_eq_one, ← Nat.dvd_one, ← Nat.modEq_zero_iff_dvd]
calc
@@ -90,7 +90,7 @@ theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.dvd_iff_emod_eq_zero]
#align nat.modeq_iff_dvd Nat.modEq_iff_dvd
-alias modEq_iff_dvd ↔ ModEq.dvd modEq_of_dvd
+alias ⟨ModEq.dvd, modEq_of_dvd⟩ := modEq_iff_dvd
#align nat.modeq.dvd Nat.ModEq.dvd
#align nat.modeq_of_dvd Nat.modEq_of_dvd
@@ -2,17 +2,14 @@
Copyright (c) 2017 Mario Carneiro. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.nat.modeq
-! leanprover-community/mathlib commit 47a1a73351de8dd6c8d3d32b569c8e434b03ca47
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Data.Int.GCD
import Mathlib.Data.Int.Order.Lemmas
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.GCongr.Core
+#align_import data.nat.modeq from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
+
/-!
# Congruences modulo a natural number
This PR is the result of running
find . -type f -name "*.lean" -exec sed -i -E 's/^( +)\. /\1· /' {} \;
find . -type f -name "*.lean" -exec sed -i -E 'N;s/^( +·)\n +(.*)$/\1 \2/;P;D' {} \;
which firstly replaces .
focusing dots with ·
and secondly removes isolated instances of such dots, unifying them with the following line. A new rule is placed in the style linter to verify this.
@@ -293,8 +293,7 @@ lemma cancel_left_div_gcd (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) : a ≡ b
rw [mul_sub]
exact modEq_iff_dvd.mp h
show Int.gcd (m / d) (c / d) = 1
- ·
- simp only [← Int.coe_nat_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
+ · simp only [← Int.coe_nat_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
Nat.div_self (gcd_pos_of_pos_left c hm)]
#align nat.modeq.cancel_left_div_gcd Nat.ModEq.cancel_left_div_gcd
@@ -11,6 +11,7 @@ Authors: Mario Carneiro
import Mathlib.Data.Int.GCD
import Mathlib.Data.Int.Order.Lemmas
import Mathlib.Tactic.NormNum
+import Mathlib.Tactic.GCongr.Core
/-!
# Congruences modulo a natural number
@@ -114,6 +115,7 @@ protected theorem mul_left' (c : ℕ) (h : a ≡ b [MOD n]) : c * a ≡ c * b [M
unfold ModEq at *; rw [mul_mod_mul_left, mul_mod_mul_left, h]
#align nat.modeq.mul_left' Nat.ModEq.mul_left'
+@[gcongr]
protected theorem mul_left (c : ℕ) (h : a ≡ b [MOD n]) : c * a ≡ c * b [MOD n] :=
(h.mul_left' _).of_dvd (dvd_mul_left _ _)
#align nat.modeq.mul_left Nat.ModEq.mul_left
@@ -122,14 +124,17 @@ protected theorem mul_right' (c : ℕ) (h : a ≡ b [MOD n]) : a * c ≡ b * c [
rw [mul_comm a, mul_comm b, mul_comm n]; exact h.mul_left' c
#align nat.modeq.mul_right' Nat.ModEq.mul_right'
+@[gcongr]
protected theorem mul_right (c : ℕ) (h : a ≡ b [MOD n]) : a * c ≡ b * c [MOD n] := by
rw [mul_comm a, mul_comm b]; exact h.mul_left c
#align nat.modeq.mul_right Nat.ModEq.mul_right
+@[gcongr]
protected theorem mul (h₁ : a ≡ b [MOD n]) (h₂ : c ≡ d [MOD n]) : a * c ≡ b * d [MOD n] :=
(h₂.mul_left _).trans (h₁.mul_right _)
#align nat.modeq.mul Nat.ModEq.mul
+@[gcongr]
protected theorem pow (m : ℕ) (h : a ≡ b [MOD n]) : a ^ m ≡ b ^ m [MOD n] := by
induction m with
| zero => rfl
@@ -138,15 +143,18 @@ protected theorem pow (m : ℕ) (h : a ≡ b [MOD n]) : a ^ m ≡ b ^ m [MOD n]
exact hd.mul h
#align nat.modeq.pow Nat.ModEq.pow
+@[gcongr]
protected theorem add (h₁ : a ≡ b [MOD n]) (h₂ : c ≡ d [MOD n]) : a + c ≡ b + d [MOD n] := by
rw [modEq_iff_dvd, Int.ofNat_add, Int.ofNat_add, add_sub_add_comm]
exact dvd_add h₁.dvd h₂.dvd
#align nat.modeq.add Nat.ModEq.add
+@[gcongr]
protected theorem add_left (c : ℕ) (h : a ≡ b [MOD n]) : c + a ≡ c + b [MOD n] :=
ModEq.rfl.add h
#align nat.modeq.add_left Nat.ModEq.add_left
+@[gcongr]
protected theorem add_right (c : ℕ) (h : a ≡ b [MOD n]) : a + c ≡ b + c [MOD n] :=
h.add ModEq.rfl
#align nat.modeq.add_right Nat.ModEq.add_right
@@ -267,9 +267,9 @@ lemma eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b : ℤ) - a| < m) : a = b := b
#align nat.modeq.eq_of_abs_lt Nat.ModEq.eq_of_abs_lt
lemma eq_of_lt_of_lt (h : a ≡ b [MOD m]) (ha : a < m) (hb : b < m) : a = b :=
-h.eq_of_abs_lt $ abs_sub_lt_iff.2
- ⟨(sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 hb,
- (sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 ha⟩
+ h.eq_of_abs_lt $ abs_sub_lt_iff.2
+ ⟨(sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 hb,
+ (sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 ha⟩
#align nat.modeq.eq_of_lt_of_lt Nat.ModEq.eq_of_lt_of_lt
/-- To cancel a common factor `c` from a `ModEq` we must divide the modulus `m` by `gcd m c` -/
@@ -318,7 +318,7 @@ lemma cancel_left_of_coprime (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) :
/-- A common factor that's coprime with the modulus can be cancelled from a `ModEq` -/
lemma cancel_right_of_coprime (hmc : gcd m c = 1) (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m] :=
-cancel_left_of_coprime hmc $ by simpa [mul_comm] using h
+ cancel_left_of_coprime hmc $ by simpa [mul_comm] using h
#align nat.modeq.cancel_right_of_coprime Nat.ModEq.cancel_right_of_coprime
end ModEq
fix-comments.py
on all files.@@ -96,7 +96,7 @@ alias modEq_iff_dvd ↔ ModEq.dvd modEq_of_dvd
#align nat.modeq.dvd Nat.ModEq.dvd
#align nat.modeq_of_dvd Nat.modEq_of_dvd
-/-- A variant of `modEq_iff_dvd` with `nat` divisibility -/
+/-- A variant of `modEq_iff_dvd` with `Nat` divisibility -/
theorem modEq_iff_dvd' (h : a ≤ b) : a ≡ b [MOD n] ↔ n ∣ b - a := by
rw [modEq_iff_dvd, ← Int.coe_nat_dvd, Int.ofNat_sub h]
#align nat.modeq_iff_dvd' Nat.modEq_iff_dvd'
Nat.gcd
, Nat.lcm
, Int.gcd
, Int.lcm
, and IsCoprime
(#3923)
This completes the porting of these norm_num extensions while adding a new extension for IsCoprime
over Int
. It also adds the norm_num extension testing file from mathlib3. Closes #3246.
Co-authored-by: Mario Carneiro <di.gama@gmail.com>
@@ -10,6 +10,7 @@ Authors: Mario Carneiro
-/
import Mathlib.Data.Int.GCD
import Mathlib.Data.Int.Order.Lemmas
+import Mathlib.Tactic.NormNum
/-!
# Congruences modulo a natural number
by
s! (#3825)
This PR puts, with one exception, every single remaining by
that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh
. The exception is when the by
begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.
Essentially this is s/\n *by$/ by/g
, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated by
s".
@@ -328,9 +328,7 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
else
if hm : m = 0 then ⟨b, by rw [hm, gcd_zero_right] at h; constructor; exact h.symm; rfl⟩
else
- ⟨let (c, d) := xgcd n m
- Int.toNat ((n * c * b + m * d * a) / gcd n m % lcm n m),
- by
+ ⟨let (c, d) := xgcd n m; Int.toNat ((n * c * b + m * d * a) / gcd n m % lcm n m), by
rw [xgcd_val]
dsimp
rw [modEq_iff_dvd, modEq_iff_dvd,
@@ -341,7 +339,6 @@ def chineseRemainder' (h : a ≡ b [MOD gcd n m]) : { k // k ≡ a [MOD n] ∧ k
exact fun _ => hm
have hcoedvd : ∀ t, (gcd n m : ℤ) ∣ t * (b - a) := fun t => h.dvd.mul_left _
have := gcd_eq_gcd_ab n m
-
constructor <;> rw [Int.emod_def, ← sub_add] <;>
refine' dvd_add _ (dvd_mul_of_dvd_left _ _) <;>
try norm_cast
This PR fixes two things:
align
statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align
). This is often seen in the mathport output after ending calc
blocks.#align
statements. (This was needed for a script I wrote for #3630.)@@ -397,7 +397,6 @@ theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n])
1 ≡ a * b [MOD a.gcd n] := (hh ▸ h).symm.of_mul_right g
_ ≡ 0 * b [MOD a.gcd n] := (Nat.modEq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).mul_right b
_ = 0 := by rw [zero_mul]
-
#align nat.coprime_of_mul_modeq_one Nat.coprime_of_mul_modEq_one
@[simp 1100]
a/c ≡ b/c mod m/c → a ≡ b mod m
(#3259)
https://github.com/leanprover-community/mathlib/pull/18119, https://github.com/leanprover-community/mathlib/pull/18666.
algebra.ring.divisibility
@f1a2caaf51ef593799107fe9a8d5e411599f3996
..47a1a73351de8dd6c8d3d32b569c8e434b03ca47
data.nat.order.lemmas
@2258b40dacd2942571c8ce136215350c702dc78f
..47a1a73351de8dd6c8d3d32b569c8e434b03ca47
data.int.gcd
@d4f69d96f3532729da8ebb763f4bc26fcf640f06
..47a1a73351de8dd6c8d3d32b569c8e434b03ca47
data.nat.modeq
@2ed7e4aec72395b6a7c3ac4ac7873a7a43ead17c
..47a1a73351de8dd6c8d3d32b569c8e434b03ca47
data.int.modeq
@2ed7e4aec72395b6a7c3ac4ac7873a7a43ead17c
..47a1a73351de8dd6c8d3d32b569c8e434b03ca47
algebra.char_p.basic
@ceb887ddf3344dab425292e497fa2af91498437c
..47a1a73351de8dd6c8d3d32b569c8e434b03ca47
data.zmod.basic
@297619ec79dedf23525458b6bf5bf35c736fd2b8
..47a1a73351de8dd6c8d3d32b569c8e434b03ca47
Co-authored-by: Parcly Taxel <reddeloostw@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
! This file was ported from Lean 3 source module data.nat.modeq
-! leanprover-community/mathlib commit 2ed7e4aec72395b6a7c3ac4ac7873a7a43ead17c
+! leanprover-community/mathlib commit 47a1a73351de8dd6c8d3d32b569c8e434b03ca47
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -212,6 +212,10 @@ For cancelling right multiplication on both sides of the `≡`, see `nat.modeq.m
lemma of_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] := mul_comm m n ▸ of_mul_left _
#align nat.modeq.of_mul_right Nat.ModEq.of_mul_right
+theorem of_div (h : a / c ≡ b / c [MOD m / c]) (ha : c ∣ a) (ha : c ∣ b) (ha : c ∣ m) :
+ a ≡ b [MOD m] := by convert h.mul_left' c <;> rwa [Nat.mul_div_cancel']
+#align nat.modeq.of_div Nat.ModEq.of_div
+
end ModEq
lemma modEq_sub (h : b ≤ a) : a ≡ b [MOD a - b] := (modEq_of_dvd $ by rw [Int.ofNat_sub h]).symm
ModEq
lemma names (#1384)
Match https://github.com/leanprover-community/mathlib/pull/17902
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Mario Carneiro
! This file was ported from Lean 3 source module data.nat.modeq
-! leanprover-community/mathlib commit 09597669f02422ed388036273d8848119699c22f
+! leanprover-community/mathlib commit 2ed7e4aec72395b6a7c3ac4ac7873a7a43ead17c
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -91,12 +91,8 @@ theorem modEq_iff_dvd : a ≡ b [MOD n] ↔ (n : ℤ) ∣ b - a := by
Int.emod_eq_emod_iff_emod_sub_eq_zero, Int.dvd_iff_emod_eq_zero]
#align nat.modeq_iff_dvd Nat.modEq_iff_dvd
-protected theorem ModEq.dvd : a ≡ b [MOD n] → (n : ℤ) ∣ b - a :=
- modEq_iff_dvd.1
+alias modEq_iff_dvd ↔ ModEq.dvd modEq_of_dvd
#align nat.modeq.dvd Nat.ModEq.dvd
-
-theorem modEq_of_dvd : (n : ℤ) ∣ b - a → a ≡ b [MOD n] :=
- modEq_iff_dvd.2
#align nat.modeq_of_dvd Nat.modEq_of_dvd
/-- A variant of `modEq_iff_dvd` with `nat` divisibility -/
@@ -110,16 +106,15 @@ theorem mod_modEq (a n) : a % n ≡ a [MOD n] :=
namespace ModEq
-protected theorem modEq_of_dvd (d : m ∣ n) (h : a ≡ b [MOD n]) : a ≡ b [MOD m] :=
- modEq_of_dvd ((Int.coe_nat_dvd.2 d).trans h.dvd)
-#align nat.modeq.modeq_of_dvd Nat.ModEq.modEq_of_dvd
+lemma of_dvd (d : m ∣ n) (h : a ≡ b [MOD n]) : a ≡ b [MOD m] := modEq_of_dvd $ d.natCast.trans h.dvd
+#align nat.modeq.of_dvd Nat.ModEq.of_dvd
protected theorem mul_left' (c : ℕ) (h : a ≡ b [MOD n]) : c * a ≡ c * b [MOD c * n] := by
unfold ModEq at *; rw [mul_mod_mul_left, mul_mod_mul_left, h]
#align nat.modeq.mul_left' Nat.ModEq.mul_left'
protected theorem mul_left (c : ℕ) (h : a ≡ b [MOD n]) : c * a ≡ c * b [MOD n] :=
- (h.mul_left' _).modEq_of_dvd (dvd_mul_left _ _)
+ (h.mul_left' _).of_dvd (dvd_mul_left _ _)
#align nat.modeq.mul_left Nat.ModEq.mul_left
protected theorem mul_right' (c : ℕ) (h : a ≡ b [MOD n]) : a * c ≡ b * c [MOD n * c] := by
@@ -137,7 +132,7 @@ protected theorem mul (h₁ : a ≡ b [MOD n]) (h₂ : c ≡ d [MOD n]) : a * c
protected theorem pow (m : ℕ) (h : a ≡ b [MOD n]) : a ^ m ≡ b ^ m [MOD n] := by
induction m with
| zero => rfl
- | succ d hd =>
+ | succ d hd =>
rw[pow_succ, pow_succ]
exact hd.mul h
#align nat.modeq.pow Nat.ModEq.pow
@@ -177,6 +172,9 @@ protected theorem add_right_cancel' (c : ℕ) (h : a + c ≡ b + c [MOD n]) : a
ModEq.rfl.add_right_cancel h
#align nat.modeq.add_right_cancel' Nat.ModEq.add_right_cancel'
+/-- Cancel left multiplication on both sides of the `≡` and in the modulus.
+
+For cancelling left multiplication in the modulus, see `Nat.ModEq.of_mul_left`. -/
protected theorem mul_left_cancel' {a b c m : ℕ} (hc : c ≠ 0) :
c * a ≡ c * b [MOD c * m] → a ≡ b [MOD m] := by
simp [modEq_iff_dvd, ← mul_sub, mul_dvd_mul_iff_left (by simp [hc] : (c : ℤ) ≠ 0)]
@@ -187,6 +185,9 @@ protected theorem mul_left_cancel_iff' {a b c m : ℕ} (hc : c ≠ 0) :
⟨ModEq.mul_left_cancel' hc, ModEq.mul_left' _⟩
#align nat.modeq.mul_left_cancel_iff' Nat.ModEq.mul_left_cancel_iff'
+/-- Cancel right multiplication on both sides of the `≡` and in the modulus.
+
+For cancelling right multiplication in the modulus, see `Nat.ModEq.of_mul_right`. -/
protected theorem mul_right_cancel' {a b c m : ℕ} (hc : c ≠ 0) :
a * c ≡ b * c [MOD m * c] → a ≡ b [MOD m] := by
simp [modEq_iff_dvd, ← sub_mul, mul_dvd_mul_iff_right (by simp [hc] : (c : ℤ) ≠ 0)]
@@ -197,36 +198,35 @@ protected theorem mul_right_cancel_iff' {a b c m : ℕ} (hc : c ≠ 0) :
⟨ModEq.mul_right_cancel' hc, ModEq.mul_right' _⟩
#align nat.modeq.mul_right_cancel_iff' Nat.ModEq.mul_right_cancel_iff'
-theorem of_modEq_mul_left (m : ℕ) (h : a ≡ b [MOD m * n]) : a ≡ b [MOD n] := by
+/-- Cancel left multiplication in the modulus.
+
+For cancelling left multiplication on both sides of the `≡`, see `nat.modeq.mul_left_cancel'`. -/
+lemma of_mul_left (m : ℕ) (h : a ≡ b [MOD m * n]) : a ≡ b [MOD n] := by
rw [modEq_iff_dvd] at *
exact (dvd_mul_left (n : ℤ) (m : ℤ)).trans h
-#align nat.modeq.of_ModEq_mul_left Nat.ModEq.of_modEq_mul_left
+#align nat.modeq.of_mul_left Nat.ModEq.of_mul_left
-theorem of_modEq_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] :=
- mul_comm m n ▸ of_modEq_mul_left _
-#align nat.modeq.of_ModEq_mul_right Nat.ModEq.of_modEq_mul_right
+/-- Cancel right multiplication in the modulus.
-end ModEq
+For cancelling right multiplication on both sides of the `≡`, see `nat.modeq.mul_right_cancel'`. -/
+lemma of_mul_right (m : ℕ) : a ≡ b [MOD n * m] → a ≡ b [MOD n] := mul_comm m n ▸ of_mul_left _
+#align nat.modeq.of_mul_right Nat.ModEq.of_mul_right
-theorem modEq_one : a ≡ b [MOD 1] :=
- modEq_of_dvd (one_dvd _)
-#align nat.modeq_one Nat.modEq_one
+end ModEq
-theorem modEq_sub (h : b ≤ a) : a ≡ b [MOD a - b] :=
- (modEq_of_dvd <| by rw [Int.ofNat_sub h]).symm
+lemma modEq_sub (h : b ≤ a) : a ≡ b [MOD a - b] := (modEq_of_dvd $ by rw [Int.ofNat_sub h]).symm
#align nat.modeq_sub Nat.modEq_sub
-@[simp]
-theorem modEq_zero_iff {a b : ℕ} : a ≡ b [MOD 0] ↔ a = b := by
- rw [Nat.ModEq, Nat.mod_zero, Nat.mod_zero]
+lemma modEq_one : a ≡ b [MOD 1] := modEq_of_dvd $ one_dvd _
+#align nat.modeq_one Nat.modEq_one
+
+@[simp] lemma modEq_zero_iff : a ≡ b [MOD 0] ↔ a = b := by rw [ModEq, mod_zero, mod_zero]
#align nat.modeq_zero_iff Nat.modEq_zero_iff
-@[simp]
-theorem add_modEq_left {a n : ℕ} : n + a ≡ a [MOD n] := by rw [Nat.ModEq, Nat.add_mod_left]
+@[simp] lemma add_modEq_left : n + a ≡ a [MOD n] := by rw [ModEq, add_mod_left]
#align nat.add_modeq_left Nat.add_modEq_left
-@[simp]
-theorem add_modEq_right {a n : ℕ} : a + n ≡ a [MOD n] := by rw [Nat.ModEq, Nat.add_mod_right]
+@[simp] lemma add_modEq_right : a + n ≡ a [MOD n] := by rw [ModEq, add_mod_right]
#align nat.add_modeq_right Nat.add_modEq_right
namespace ModEq
@@ -241,30 +241,34 @@ theorem add_le_of_lt (h1 : a ≡ b [MOD m]) (h2 : a < b) : a + m ≤ b :=
le_of_lt_add (add_modEq_right.trans h1) (add_lt_add_right h2 m)
#align nat.modeq.add_le_of_lt Nat.ModEq.add_le_of_lt
-theorem dvd_iff_of_modEq_of_dvd {a b d m : ℕ} (h : a ≡ b [MOD m]) (hdm : d ∣ m) :
- d ∣ a ↔ d ∣ b := by
+theorem dvd_iff (h : a ≡ b [MOD m]) (hdm : d ∣ m) : d ∣ a ↔ d ∣ b := by
simp only [← modEq_zero_iff_dvd]
- replace h := h.modEq_of_dvd hdm
+ replace h := h.of_dvd hdm
exact ⟨h.symm.trans, h.trans⟩
-#align nat.modeq.dvd_iff_of_modeq_of_dvd Nat.ModEq.dvd_iff_of_modEq_of_dvd
+#align nat.modeq.dvd_iff Nat.ModEq.dvd_iff
-theorem gcd_eq_of_modEq {a b m : ℕ} (h : a ≡ b [MOD m]) : gcd a m = gcd b m := by
+theorem gcd_eq (h : a ≡ b [MOD m]) : gcd a m = gcd b m := by
have h1 := gcd_dvd_right a m
have h2 := gcd_dvd_right b m
exact
- dvd_antisymm (dvd_gcd ((dvd_iff_of_modEq_of_dvd h h1).mp (gcd_dvd_left a m)) h1)
- (dvd_gcd ((dvd_iff_of_modEq_of_dvd h h2).mpr (gcd_dvd_left b m)) h2)
-#align nat.modeq.gcd_eq_of_modeq Nat.ModEq.gcd_eq_of_modEq
+ dvd_antisymm (dvd_gcd ((h.dvd_iff h1).mp (gcd_dvd_left a m)) h1)
+ (dvd_gcd ((h.dvd_iff h2).mpr (gcd_dvd_left b m)) h2)
+#align nat.modeq.gcd_eq Nat.ModEq.gcd_eq
-theorem eq_of_modEq_of_abs_lt {a b m : ℕ} (h : a ≡ b [MOD m]) (h2 : |(b : ℤ) - a| < m) : a = b := by
+lemma eq_of_abs_lt (h : a ≡ b [MOD m]) (h2 : |(b : ℤ) - a| < m) : a = b := by
apply Int.ofNat.inj
rw [eq_comm, ← sub_eq_zero]
- exact Int.eq_zero_of_abs_lt_dvd (modEq_iff_dvd.mp h) h2
-#align nat.modeq.eq_of_modeq_of_abs_lt Nat.ModEq.eq_of_modEq_of_abs_lt
+ exact Int.eq_zero_of_abs_lt_dvd h.dvd h2
+#align nat.modeq.eq_of_abs_lt Nat.ModEq.eq_of_abs_lt
+
+lemma eq_of_lt_of_lt (h : a ≡ b [MOD m]) (ha : a < m) (hb : b < m) : a = b :=
+h.eq_of_abs_lt $ abs_sub_lt_iff.2
+ ⟨(sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 hb,
+ (sub_le_self _ $ Int.coe_nat_nonneg _).trans_lt $ Int.ofNat_lt.2 ha⟩
+#align nat.modeq.eq_of_lt_of_lt Nat.ModEq.eq_of_lt_of_lt
/-- To cancel a common factor `c` from a `ModEq` we must divide the modulus `m` by `gcd m c` -/
-theorem modEq_cancel_left_div_gcd {a b c m : ℕ} (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) :
- a ≡ b [MOD m / gcd m c] := by
+lemma cancel_left_div_gcd (hm : 0 < m) (h : c * a ≡ c * b [MOD m]) : a ≡ b [MOD m / gcd m c] := by
let d := gcd m c
have hmd := gcd_dvd_left m c
have hcd := gcd_dvd_right m c
@@ -279,42 +283,38 @@ theorem modEq_cancel_left_div_gcd {a b c m : ℕ} (hm : 0 < m) (h : c * a ≡ c
·
simp only [← Int.coe_nat_div, Int.coe_nat_gcd (m / d) (c / d), gcd_div hmd hcd,
Nat.div_self (gcd_pos_of_pos_left c hm)]
-#align nat.modeq.modeq_cancel_left_div_gcd Nat.ModEq.modEq_cancel_left_div_gcd
+#align nat.modeq.cancel_left_div_gcd Nat.ModEq.cancel_left_div_gcd
-theorem modEq_cancel_right_div_gcd {a b c m : ℕ} (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) :
- a ≡ b [MOD m / gcd m c] := by
- apply modEq_cancel_left_div_gcd hm
+/-- To cancel a common factor `c` from a `ModEq` we must divide the modulus `m` by `gcd m c` -/
+lemma cancel_right_div_gcd (hm : 0 < m) (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m / gcd m c] := by
+ apply cancel_left_div_gcd hm
simpa [mul_comm] using h
-#align nat.modeq.modeq_cancel_right_div_gcd Nat.ModEq.modEq_cancel_right_div_gcd
+#align nat.modeq.cancel_right_div_gcd Nat.ModEq.cancel_right_div_gcd
-theorem modEq_cancel_left_div_gcd' {a b c d m : ℕ} (hm : 0 < m) (hcd : c ≡ d [MOD m])
- (h : c * a ≡ d * b [MOD m]) : a ≡ b [MOD m / gcd m c] :=
- modEq_cancel_left_div_gcd hm (h.trans (ModEq.mul_right b hcd).symm)
-#align nat.modeq.modeq_cancel_left_div_gcd' Nat.ModEq.modEq_cancel_left_div_gcd'
+lemma cancel_left_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : c * a ≡ d * b [MOD m]) :
+ a ≡ b [MOD m / gcd m c] :=
+(h.trans $ hcd.symm.mul_right b).cancel_left_div_gcd hm
+#align nat.modeq.cancel_left_div_gcd' Nat.ModEq.cancel_left_div_gcd'
-theorem modEq_cancel_right_div_gcd' {a b c d m : ℕ} (hm : 0 < m) (hcd : c ≡ d [MOD m])
- (h : a * c ≡ b * d [MOD m]) : a ≡ b [MOD m / gcd m c] := by
- apply modEq_cancel_left_div_gcd' hm hcd
- simpa [mul_comm] using h
-#align nat.modeq.modeq_cancel_right_div_gcd' Nat.ModEq.modEq_cancel_right_div_gcd'
+lemma cancel_right_div_gcd' (hm : 0 < m) (hcd : c ≡ d [MOD m]) (h : a * c ≡ b * d [MOD m]) :
+ a ≡ b [MOD m / gcd m c] :=
+(h.trans $ hcd.symm.mul_left b).cancel_right_div_gcd hm
+#align nat.modeq.cancel_right_div_gcd' Nat.ModEq.cancel_right_div_gcd'
/-- A common factor that's coprime with the modulus can be cancelled from a `ModEq` -/
-theorem modEq_cancel_left_of_coprime {a b c m : ℕ} (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) :
- a ≡ b [MOD m] := by
+lemma cancel_left_of_coprime (hmc : gcd m c = 1) (h : c * a ≡ c * b [MOD m]) : a ≡ b [MOD m] := by
rcases m.eq_zero_or_pos with (rfl | hm)
· simp only [gcd_zero_left] at hmc
simp only [gcd_zero_left, hmc, one_mul, modEq_zero_iff] at h
subst h
rfl
- simpa [hmc] using modEq_cancel_left_div_gcd hm h
-#align nat.modeq.modeq_cancel_left_of_coprime Nat.ModEq.modEq_cancel_left_of_coprime
+ simpa [hmc] using h.cancel_left_div_gcd hm
+#align nat.modeq.cancel_left_of_coprime Nat.ModEq.cancel_left_of_coprime
/-- A common factor that's coprime with the modulus can be cancelled from a `ModEq` -/
-theorem modEq_cancel_right_of_coprime {a b c m : ℕ} (hmc : gcd m c = 1)
- (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m] := by
- apply modEq_cancel_left_of_coprime hmc
- simpa [mul_comm] using h
-#align nat.modeq.modeq_cancel_right_of_coprime Nat.ModEq.modEq_cancel_right_of_coprime
+lemma cancel_right_of_coprime (hmc : gcd m c = 1) (h : a * c ≡ b * c [MOD m]) : a ≡ b [MOD m] :=
+cancel_left_of_coprime hmc $ by simpa [mul_comm] using h
+#align nat.modeq.cancel_right_of_coprime Nat.ModEq.cancel_right_of_coprime
end ModEq
@@ -383,27 +383,27 @@ theorem modEq_and_modEq_iff_modEq_mul {a b m n : ℕ} (hmn : m.coprime n) :
Int.coe_nat_dvd] at h
rw [Nat.modEq_iff_dvd, ← Int.dvd_natAbs, Int.coe_nat_dvd]
exact hmn.mul_dvd_of_dvd_of_dvd h.1 h.2, fun h =>
- ⟨h.of_modEq_mul_right _, h.of_modEq_mul_left _⟩⟩
+ ⟨h.of_mul_right _, h.of_mul_left _⟩⟩
#align nat.modeq_and_modeq_iff_modeq_mul Nat.modEq_and_modEq_iff_modEq_mul
theorem coprime_of_mul_modEq_one (b : ℕ) {a n : ℕ} (h : a * b ≡ 1 [MOD n]) : a.coprime n := by
obtain ⟨g, hh⟩ := Nat.gcd_dvd_right a n
rw [Nat.coprime_iff_gcd_eq_one, ← Nat.dvd_one, ← Nat.modEq_zero_iff_dvd]
calc
- 1 ≡ a * b [MOD a.gcd n] := Nat.ModEq.of_modEq_mul_right g (hh ▸ h).symm
+ 1 ≡ a * b [MOD a.gcd n] := (hh ▸ h).symm.of_mul_right g
_ ≡ 0 * b [MOD a.gcd n] := (Nat.modEq_zero_iff_dvd.mpr (Nat.gcd_dvd_left _ _)).mul_right b
_ = 0 := by rw [zero_mul]
-
+
#align nat.coprime_of_mul_modeq_one Nat.coprime_of_mul_modEq_one
@[simp 1100]
theorem mod_mul_right_mod (a b c : ℕ) : a % (b * c) % b = a % b :=
- (mod_modEq _ _).of_modEq_mul_right _
+ (mod_modEq _ _).of_mul_right _
#align nat.mod_mul_right_mod Nat.mod_mul_right_mod
@[simp 1100]
theorem mod_mul_left_mod (a b c : ℕ) : a % (b * c) % c = a % c :=
- (mod_modEq _ _).of_modEq_mul_left _
+ (mod_modEq _ _).of_mul_left _
#align nat.mod_mul_left_mod Nat.mod_mul_left_mod
theorem div_mod_eq_mod_mul_div (a b c : ℕ) : a / b % c = a % (b * c) / b :=
@@ -509,12 +509,12 @@ theorem odd_mul_odd_div_two {m n : ℕ} (hm1 : m % 2 = 1) (hn1 : n % 2 = 1) :
#align nat.odd_mul_odd_div_two Nat.odd_mul_odd_div_two
theorem odd_of_mod_four_eq_one {n : ℕ} : n % 4 = 1 → n % 2 = 1 := by
- simpa [ModEq, show 2 * 2 = 4 by norm_num] using @ModEq.of_modEq_mul_left 2 n 1 2
+ simpa [ModEq, show 2 * 2 = 4 by norm_num] using @ModEq.of_mul_left 2 n 1 2
#align nat.odd_of_mod_four_eq_one Nat.odd_of_mod_four_eq_one
theorem odd_of_mod_four_eq_three {n : ℕ} : n % 4 = 3 → n % 2 = 1 := by
simpa [ModEq, show 2 * 2 = 4 by norm_num, show 3 % 4 = 3 by norm_num] using
- @ModEq.of_modEq_mul_left 2 n 3 2
+ @ModEq.of_mul_left 2 n 3 2
#align nat.odd_of_mod_four_eq_three Nat.odd_of_mod_four_eq_three
/-- A natural number is odd iff it has residue `1` or `3` mod `4`-/
All dependencies are ported!