data.int.gcd
⟷
Mathlib.Data.Int.GCD
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)@@ -214,11 +214,11 @@ by { rw [int.gcd, int.gcd, nat_abs_mul, nat_abs_mul], apply nat.gcd_mul_left }
theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * nat_abs j :=
by { rw [int.gcd, int.gcd, nat_abs_mul, nat_abs_mul], apply nat.gcd_mul_right }
-theorem gcd_pos_of_non_zero_left {i : ℤ} (j : ℤ) (i_non_zero : i ≠ 0) : 0 < gcd i j :=
-nat.gcd_pos_of_pos_left (nat_abs j) (nat_abs_pos_of_ne_zero i_non_zero)
+theorem gcd_pos_of_ne_zero_left {i : ℤ} (j : ℤ) (hi : i ≠ 0) : 0 < gcd i j :=
+nat.gcd_pos_of_pos_left _ $ nat_abs_pos_of_ne_zero hi
-theorem gcd_pos_of_non_zero_right (i : ℤ) {j : ℤ} (j_non_zero : j ≠ 0) : 0 < gcd i j :=
-nat.gcd_pos_of_pos_right (nat_abs i) (nat_abs_pos_of_ne_zero j_non_zero)
+theorem gcd_pos_of_ne_zero_right (i : ℤ) {j : ℤ} (hj : j ≠ 0) : 0 < gcd i j :=
+nat.gcd_pos_of_pos_right _ $ nat_abs_pos_of_ne_zero hj
theorem gcd_eq_zero_iff {i j : ℤ} : gcd i j = 0 ↔ i = 0 ∧ j = 0 :=
begin
@@ -339,7 +339,7 @@ theorem gcd_least_linear {a b : ℤ} (ha : a ≠ 0) :
begin
simp_rw ←gcd_dvd_iff,
split,
- { simpa [and_true, dvd_refl, set.mem_set_of_eq] using gcd_pos_of_non_zero_left b ha },
+ { simpa [and_true, dvd_refl, set.mem_set_of_eq] using gcd_pos_of_ne_zero_left b ha },
{ simp only [lower_bounds, and_imp, set.mem_set_of_eq],
exact λ n hn_pos hn, nat.le_of_dvd hn_pos hn },
end
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(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) 2018 Guy Leroy. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
-/
-import Data.Nat.Gcd.Basic
+import Data.Nat.GCD.Basic
import Tactic.NormNum
#align_import data.int.gcd from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
@@ -172,9 +172,9 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
have hk' := int.coe_nat_ne_zero.mpr (ne_of_gt (lt_of_le_of_lt (zero_le (gcd n k)) hk))
have key := congr_arg (fun m => Int.natMod m k) (gcd_eq_gcd_ab n k)
simp_rw [Int.natMod] at key
- rw [Int.add_mul_emod_self_left, ← Int.coe_nat_mod, Int.toNat_coe_nat, mod_eq_of_lt hk] at key
+ rw [Int.add_mul_emod_self_left, ← Int.natCast_mod, Int.toNat_natCast, mod_eq_of_lt hk] at key
refine' ⟨(n.gcd_a k % k).toNat, Eq.trans (Int.ofNat.inj _) key.symm⟩
- rw [Int.coe_nat_mod, Int.ofNat_mul, Int.toNat_of_nonneg (Int.emod_nonneg _ hk'),
+ rw [Int.natCast_mod, Int.ofNat_mul, Int.toNat_of_nonneg (Int.emod_nonneg _ hk'),
Int.toNat_of_nonneg (Int.emod_nonneg _ hk'), Int.mul_emod, Int.emod_emod, ← Int.mul_emod]
#align nat.exists_mul_mod_eq_gcd Nat.exists_mul_emod_eq_gcd
-/
@@ -277,19 +277,20 @@ protected theorem coe_nat_lcm (m n : ℕ) : Int.lcm ↑m ↑n = Nat.lcm m n :=
#print Int.gcd_dvd_left /-
theorem gcd_dvd_left (i j : ℤ) : (gcd i j : ℤ) ∣ i :=
- dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_left _ _
+ dvd_natAbs.mp <| natCast_dvd_natCast.mpr <| Nat.gcd_dvd_left _ _
#align int.gcd_dvd_left Int.gcd_dvd_left
-/
#print Int.gcd_dvd_right /-
theorem gcd_dvd_right (i j : ℤ) : (gcd i j : ℤ) ∣ j :=
- dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_right _ _
+ dvd_natAbs.mp <| natCast_dvd_natCast.mpr <| Nat.gcd_dvd_right _ _
#align int.gcd_dvd_right Int.gcd_dvd_right
-/
#print Int.dvd_gcd /-
theorem dvd_gcd {i j k : ℤ} (h1 : k ∣ i) (h2 : k ∣ j) : k ∣ gcd i j :=
- natAbs_dvd.1 <| coe_nat_dvd.2 <| Nat.dvd_gcd (natAbs_dvd_natAbs.2 h1) (natAbs_dvd_natAbs.2 h2)
+ natAbs_dvd.1 <|
+ natCast_dvd_natCast.2 <| Nat.dvd_gcd (natAbs_dvd_natAbs.2 h1) (natAbs_dvd_natAbs.2 h2)
#align int.dvd_gcd Int.dvd_gcd
-/
@@ -369,13 +370,13 @@ theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * natAbs j :
#print Int.gcd_pos_of_ne_zero_left /-
theorem gcd_pos_of_ne_zero_left {i : ℤ} (j : ℤ) (hi : i ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_left _ <| natAbs_pos_of_ne_zero hi
+ Nat.gcd_pos_of_pos_left _ <| natAbs_pos hi
#align int.gcd_pos_of_ne_zero_left Int.gcd_pos_of_ne_zero_left
-/
#print Int.gcd_pos_of_ne_zero_right /-
theorem gcd_pos_of_ne_zero_right (i : ℤ) {j : ℤ} (hj : j ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_right _ <| natAbs_pos_of_ne_zero hj
+ Nat.gcd_pos_of_pos_right _ <| natAbs_pos hj
#align int.gcd_pos_of_ne_zero_right Int.gcd_pos_of_ne_zero_right
-/
@@ -417,13 +418,13 @@ theorem gcd_div_gcd_div_gcd {i j : ℤ} (H : 0 < gcd i j) : gcd (i / gcd i j) (j
#print Int.gcd_dvd_gcd_of_dvd_left /-
theorem gcd_dvd_gcd_of_dvd_left {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd i j ∣ gcd k j :=
- Int.coe_nat_dvd.1 <| dvd_gcd ((gcd_dvd_left i j).trans H) (gcd_dvd_right i j)
+ Int.natCast_dvd_natCast.1 <| dvd_gcd ((gcd_dvd_left i j).trans H) (gcd_dvd_right i j)
#align int.gcd_dvd_gcd_of_dvd_left Int.gcd_dvd_gcd_of_dvd_left
-/
#print Int.gcd_dvd_gcd_of_dvd_right /-
theorem gcd_dvd_gcd_of_dvd_right {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd j i ∣ gcd j k :=
- Int.coe_nat_dvd.1 <| dvd_gcd (gcd_dvd_left j i) ((gcd_dvd_right j i).trans H)
+ Int.natCast_dvd_natCast.1 <| dvd_gcd (gcd_dvd_left j i) ((gcd_dvd_right j i).trans H)
#align int.gcd_dvd_gcd_of_dvd_right Int.gcd_dvd_gcd_of_dvd_right
-/
@@ -506,7 +507,7 @@ theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑
rw [← Nat.mul_div_cancel' h, Int.ofNat_mul, gcd_eq_gcd_ab, add_mul, mul_assoc, mul_assoc]
refine' ⟨_, _, rfl⟩
· rintro ⟨x, y, h⟩
- rw [← Int.coe_nat_dvd, h]
+ rw [← Int.natCast_dvd_natCast, h]
exact
dvd_add (dvd_mul_of_dvd_left (gcd_dvd_left a b) _) (dvd_mul_of_dvd_left (gcd_dvd_right a b) y)
#align int.gcd_dvd_iff Int.gcd_dvd_iff
@@ -630,7 +631,7 @@ theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
cases m; · simp only [hn, Nat.gcd_zero_left]
lift x to Mˣ using isUnit_ofPowEqOne hm m.succ_ne_zero
simp only [← Units.val_pow_eq_pow_val] at *
- rw [← Units.val_one, ← zpow_coe_nat, ← Units.ext_iff] at *
+ rw [← Units.val_one, ← zpow_natCast, ← Units.ext_iff] at *
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
-/
@@ -660,8 +661,8 @@ namespace NormNum
theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂ : (d : ℤ) ∣ y)
(h₃ : x * a + y * b = d) : Int.gcd x y = d :=
by
- refine' Nat.dvd_antisymm _ (Int.coe_nat_dvd.1 (Int.dvd_gcd h₁ h₂))
- rw [← Int.coe_nat_dvd, ← h₃]
+ refine' Nat.dvd_antisymm _ (Int.natCast_dvd_natCast.1 (Int.dvd_gcd h₁ h₂))
+ rw [← Int.natCast_dvd_natCast, ← h₃]
apply dvd_add
· exact (Int.gcd_dvd_left _ _).hMul_right _
· exact (Int.gcd_dvd_right _ _).hMul_right _
@@ -686,7 +687,8 @@ theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d *
by
rw [← Int.coe_nat_gcd];
apply
- @int_gcd_helper' _ _ _ a (-b) (Int.coe_nat_dvd.2 ⟨_, hu.symm⟩) (Int.coe_nat_dvd.2 ⟨_, hv.symm⟩)
+ @int_gcd_helper' _ _ _ a (-b) (Int.natCast_dvd_natCast.2 ⟨_, hu.symm⟩)
+ (Int.natCast_dvd_natCast.2 ⟨_, hv.symm⟩)
rw [mul_neg, ← sub_eq_add_neg, sub_eq_iff_eq_add']
norm_cast; rw [hx, hy, h]
#align tactic.norm_num.nat_gcd_helper_2 Tactic.NormNum.nat_gcd_helper_2
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -160,7 +160,7 @@ theorem xgcdAux_P {r r'} :
-/
theorem gcd_eq_gcd_ab : (gcd x y : ℤ) = x * gcdA x y + y * gcdB x y := by
have := @xgcd_aux_P x y x y 1 0 0 1 (by simp [P]) (by simp [P]) <;>
- rwa [xgcd_aux_val, xgcd_val] at this
+ rwa [xgcd_aux_val, xgcd_val] at this
#align nat.gcd_eq_gcd_ab Nat.gcd_eq_gcd_ab
-/
@@ -171,8 +171,8 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
by
have hk' := int.coe_nat_ne_zero.mpr (ne_of_gt (lt_of_le_of_lt (zero_le (gcd n k)) hk))
have key := congr_arg (fun m => Int.natMod m k) (gcd_eq_gcd_ab n k)
- simp_rw [Int.natMod] at key
- rw [Int.add_mul_emod_self_left, ← Int.coe_nat_mod, Int.toNat_coe_nat, mod_eq_of_lt hk] at key
+ simp_rw [Int.natMod] at key
+ rw [Int.add_mul_emod_self_left, ← Int.coe_nat_mod, Int.toNat_coe_nat, mod_eq_of_lt hk] at key
refine' ⟨(n.gcd_a k % k).toNat, Eq.trans (Int.ofNat.inj _) key.symm⟩
rw [Int.coe_nat_mod, Int.ofNat_mul, Int.toNat_of_nonneg (Int.emod_nonneg _ hk'),
Int.toNat_of_nonneg (Int.emod_nonneg _ hk'), Int.mul_emod, Int.emod_emod, ← Int.mul_emod]
@@ -246,13 +246,13 @@ theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natA
#print Int.dvd_of_mul_dvd_mul_left /-
theorem dvd_of_mul_dvd_mul_left {i j k : ℤ} (k_non_zero : k ≠ 0) (H : k * i ∣ k * j) : i ∣ j :=
- Dvd.elim H fun l H1 => by rw [mul_assoc] at H1 <;> exact ⟨_, mul_left_cancel₀ k_non_zero H1⟩
+ Dvd.elim H fun l H1 => by rw [mul_assoc] at H1 <;> exact ⟨_, mul_left_cancel₀ k_non_zero H1⟩
#align int.dvd_of_mul_dvd_mul_left Int.dvd_of_mul_dvd_mul_left
-/
#print Int.dvd_of_mul_dvd_mul_right /-
theorem dvd_of_mul_dvd_mul_right {i j k : ℤ} (k_non_zero : k ≠ 0) (H : i * k ∣ j * k) : i ∣ j := by
- rw [mul_comm i k, mul_comm j k] at H <;> exact dvd_of_mul_dvd_mul_left k_non_zero H
+ rw [mul_comm i k, mul_comm j k] at H <;> exact dvd_of_mul_dvd_mul_left k_non_zero H
#align int.dvd_of_mul_dvd_mul_right Int.dvd_of_mul_dvd_mul_right
-/
@@ -527,7 +527,7 @@ Compare with `is_coprime.dvd_of_dvd_mul_left` and
theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a c = 1) : a ∣ b :=
by
have := gcd_eq_gcd_ab a c
- simp only [hab, Int.ofNat_zero, Int.ofNat_succ, zero_add] at this
+ simp only [hab, Int.ofNat_zero, Int.ofNat_succ, zero_add] at this
have : b * a * gcd_a a c + b * c * gcd_b a c = b := by simp [mul_assoc, ← mul_add, ← this]
rw [← this]
exact dvd_add (dvd_mul_of_dvd_left (dvd_mul_left a b) _) (dvd_mul_of_dvd_left habc _)
@@ -539,7 +539,7 @@ theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab :
Compare with `is_coprime.dvd_of_dvd_mul_right` and
`unique_factorization_monoid.dvd_of_dvd_mul_right_of_no_prime_factors` -/
theorem dvd_of_dvd_mul_right_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a b = 1) :
- a ∣ c := by rw [mul_comm] at habc ; exact dvd_of_dvd_mul_left_of_gcd_one habc hab
+ a ∣ c := by rw [mul_comm] at habc; exact dvd_of_dvd_mul_left_of_gcd_one habc hab
#align int.dvd_of_dvd_mul_right_of_gcd_one Int.dvd_of_dvd_mul_right_of_gcd_one
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -630,7 +630,7 @@ theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
cases m; · simp only [hn, Nat.gcd_zero_left]
lift x to Mˣ using isUnit_ofPowEqOne hm m.succ_ne_zero
simp only [← Units.val_pow_eq_pow_val] at *
- rw [← Units.val_one, ← zpow_ofNat, ← Units.ext_iff] at *
+ rw [← Units.val_one, ← zpow_coe_nat, ← Units.ext_iff] at *
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -329,30 +329,30 @@ theorem gcd_zero_right (i : ℤ) : gcd i 0 = natAbs i := by simp [gcd]
#align int.gcd_zero_right Int.gcd_zero_right
-/
-#print Int.gcd_one_left /-
+#print Int.one_gcd /-
@[simp]
-theorem gcd_one_left (i : ℤ) : gcd 1 i = 1 :=
+theorem one_gcd (i : ℤ) : gcd 1 i = 1 :=
Nat.gcd_one_left _
-#align int.gcd_one_left Int.gcd_one_left
+#align int.gcd_one_left Int.one_gcd
-/
-#print Int.gcd_one_right /-
+#print Int.gcd_one /-
@[simp]
-theorem gcd_one_right (i : ℤ) : gcd i 1 = 1 :=
+theorem gcd_one (i : ℤ) : gcd i 1 = 1 :=
Nat.gcd_one_right _
-#align int.gcd_one_right Int.gcd_one_right
+#align int.gcd_one_right Int.gcd_one
-/
-#print Int.gcd_neg_right /-
+#print Int.gcd_neg /-
@[simp]
-theorem gcd_neg_right {x y : ℤ} : gcd x (-y) = gcd x y := by rw [Int.gcd, Int.gcd, nat_abs_neg]
-#align int.gcd_neg_right Int.gcd_neg_right
+theorem gcd_neg {x y : ℤ} : gcd x (-y) = gcd x y := by rw [Int.gcd, Int.gcd, nat_abs_neg]
+#align int.gcd_neg_right Int.gcd_neg
-/
-#print Int.gcd_neg_left /-
+#print Int.neg_gcd /-
@[simp]
-theorem gcd_neg_left {x y : ℤ} : gcd (-x) y = gcd x y := by rw [Int.gcd, Int.gcd, nat_abs_neg]
-#align int.gcd_neg_left Int.gcd_neg_left
+theorem neg_gcd {x y : ℤ} : gcd (-x) y = gcd x y := by rw [Int.gcd, Int.gcd, nat_abs_neg]
+#align int.gcd_neg_left Int.neg_gcd
-/
#print Int.gcd_mul_left /-
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,8 +3,8 @@ Copyright (c) 2018 Guy Leroy. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
-/
-import Mathbin.Data.Nat.Gcd.Basic
-import Mathbin.Tactic.NormNum
+import Data.Nat.Gcd.Basic
+import Tactic.NormNum
#align_import data.int.gcd from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -180,7 +180,7 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
-/
#print Nat.exists_mul_emod_eq_one_of_coprime /-
-theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : coprime n k) (hk : 1 < k) :
+theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : Coprime n k) (hk : 1 < k) :
∃ m, n * m % k = 1 :=
Exists.cases_on (exists_mul_emod_eq_gcd (lt_of_le_of_lt (le_of_eq hkn) hk)) fun m hm =>
⟨m, hm.trans hkn⟩
@@ -706,26 +706,26 @@ theorem nat_lcm_helper (x y d m n : ℕ) (hd : Nat.gcd x y = d) (d0 : 0 < d) (xy
#align tactic.norm_num.nat_lcm_helper Tactic.NormNum.nat_lcm_helper
-/
-theorem nat_coprime_helper_zero_left (x : ℕ) (h : 1 < x) : ¬Nat.coprime 0 x :=
+theorem nat_coprime_helper_zero_left (x : ℕ) (h : 1 < x) : ¬Nat.Coprime 0 x :=
mt (Nat.coprime_zero_left _).1 <| ne_of_gt h
#align tactic.norm_num.nat_coprime_helper_zero_left Tactic.NormNum.nat_coprime_helper_zero_left
-theorem nat_coprime_helper_zero_right (x : ℕ) (h : 1 < x) : ¬Nat.coprime x 0 :=
+theorem nat_coprime_helper_zero_right (x : ℕ) (h : 1 < x) : ¬Nat.Coprime x 0 :=
mt (Nat.coprime_zero_right _).1 <| ne_of_gt h
#align tactic.norm_num.nat_coprime_helper_zero_right Tactic.NormNum.nat_coprime_helper_zero_right
theorem nat_coprime_helper_1 (x y a b tx ty : ℕ) (hx : x * a = tx) (hy : y * b = ty)
- (h : tx + 1 = ty) : Nat.coprime x y :=
+ (h : tx + 1 = ty) : Nat.Coprime x y :=
nat_gcd_helper_1 _ _ _ _ _ _ _ _ _ (one_mul _) (one_mul _) hx hy h
#align tactic.norm_num.nat_coprime_helper_1 Tactic.NormNum.nat_coprime_helper_1
theorem nat_coprime_helper_2 (x y a b tx ty : ℕ) (hx : x * a = tx) (hy : y * b = ty)
- (h : ty + 1 = tx) : Nat.coprime x y :=
+ (h : ty + 1 = tx) : Nat.Coprime x y :=
nat_gcd_helper_2 _ _ _ _ _ _ _ _ _ (one_mul _) (one_mul _) hx hy h
#align tactic.norm_num.nat_coprime_helper_2 Tactic.NormNum.nat_coprime_helper_2
theorem nat_not_coprime_helper (d x y u v : ℕ) (hu : d * u = x) (hv : d * v = y) (h : 1 < d) :
- ¬Nat.coprime x y :=
+ ¬Nat.Coprime x y :=
Nat.not_coprime_of_dvd_of_dvd h ⟨_, hu.symm⟩ ⟨_, hv.symm⟩
#align tactic.norm_num.nat_not_coprime_helper Tactic.NormNum.nat_not_coprime_helper
@@ -900,7 +900,7 @@ unsafe def eval_gcd : expr → tactic (expr × expr)
| q(Nat.lcm $(ex) $(ey)) => do
let c ← mk_instance_cache q(ℕ)
Prod.snd <$> prove_lcm_nat c ex ey
- | q(Nat.coprime $(ex) $(ey)) => do
+ | q(Nat.Coprime $(ex) $(ey)) => do
let c ← mk_instance_cache q(ℕ)
prove_coprime_nat c ex ey >>= Sum.elim true_intro false_intro ∘ Prod.snd
| q(Int.gcd $(ex) $(ey)) => do
mathlib commit https://github.com/leanprover-community/mathlib/commit/32a7e535287f9c73f2e4d2aef306a39190f0b504
@@ -663,8 +663,8 @@ theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂
refine' Nat.dvd_antisymm _ (Int.coe_nat_dvd.1 (Int.dvd_gcd h₁ h₂))
rw [← Int.coe_nat_dvd, ← h₃]
apply dvd_add
- · exact (Int.gcd_dvd_left _ _).mul_right _
- · exact (Int.gcd_dvd_right _ _).mul_right _
+ · exact (Int.gcd_dvd_left _ _).hMul_right _
+ · exact (Int.gcd_dvd_right _ _).hMul_right _
#align tactic.norm_num.int_gcd_helper' Tactic.NormNum.int_gcd_helper'
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,15 +2,12 @@
Copyright (c) 2018 Guy Leroy. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.int.gcd
-! 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.Nat.Gcd.Basic
import Mathbin.Tactic.NormNum
+#align_import data.int.gcd from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
+
/-!
# Extended GCD and divisibility over ℤ
mathlib commit https://github.com/leanprover-community/mathlib/commit/bf2428c9486c407ca38b5b3fb10b87dad0bc99fa
@@ -55,11 +55,11 @@ theorem xgcd_zero_left {s t r' s' t'} : xgcdAux 0 s t r' s' t' = (r', s', t') :=
#align nat.xgcd_zero_left Nat.xgcd_zero_left
-/
-#print Nat.xgcd_aux_rec /-
-theorem xgcd_aux_rec {r s t r' s' t'} (h : 0 < r) :
+#print Nat.xgcdAux_rec /-
+theorem xgcdAux_rec {r s t r' s' t'} (h : 0 < r) :
xgcdAux r s t r' s' t' = xgcdAux (r' % r) (s' - r' / r * s) (t' - r' / r * t) r s t := by
cases r <;> [exact absurd h (lt_irrefl _); · simp only [xgcd_aux]; rfl]
-#align nat.xgcd_aux_rec Nat.xgcd_aux_rec
+#align nat.xgcd_aux_rec Nat.xgcdAux_rec
-/
#print Nat.xgcd /-
@@ -118,18 +118,18 @@ theorem gcdB_zero_right {s : ℕ} (h : s ≠ 0) : gcdB s 0 = 0 :=
#align nat.gcd_b_zero_right Nat.gcdB_zero_right
-/
-#print Nat.xgcd_aux_fst /-
+#print Nat.xgcdAux_fst /-
@[simp]
-theorem xgcd_aux_fst (x y) : ∀ s t s' t', (xgcdAux x s t y s' t').1 = gcd x y :=
+theorem xgcdAux_fst (x y) : ∀ s t s' t', (xgcdAux x s t y s' t').1 = gcd x y :=
gcd.induction x y (by simp) fun x y h IH s t s' t' => by
simp [xgcd_aux_rec, h, IH] <;> rw [← gcd_rec]
-#align nat.xgcd_aux_fst Nat.xgcd_aux_fst
+#align nat.xgcd_aux_fst Nat.xgcdAux_fst
-/
-#print Nat.xgcd_aux_val /-
-theorem xgcd_aux_val (x y) : xgcdAux x 1 0 y 0 1 = (gcd x y, xgcd x y) := by
+#print Nat.xgcdAux_val /-
+theorem xgcdAux_val (x y) : xgcdAux x 1 0 y 0 1 = (gcd x y, xgcd x y) := by
rw [xgcd, ← xgcd_aux_fst x y 1 0 0 1] <;> cases xgcd_aux x 1 0 y 0 1 <;> rfl
-#align nat.xgcd_aux_val Nat.xgcd_aux_val
+#align nat.xgcd_aux_val Nat.xgcdAux_val
-/
#print Nat.xgcd_val /-
@@ -145,8 +145,8 @@ parameter (x y : ℕ)
private def P : ℕ × ℤ × ℤ → Prop
| (r, s, t) => (r : ℤ) = x * s + y * t
-#print Nat.xgcd_aux_P /-
-theorem xgcd_aux_P {r r'} :
+#print Nat.xgcdAux_P /-
+theorem xgcdAux_P {r r'} :
∀ {s t s' t'}, P (r, s, t) → P (r', s', t') → P (xgcdAux r s t r' s' t') :=
gcd.induction r r' (by simp) fun a b h IH s t s' t' p p' =>
by
@@ -154,7 +154,7 @@ theorem xgcd_aux_P {r r'} :
rw [Int.mod_def]; generalize (b / a : ℤ) = k
rw [p, p']
simp [mul_add, mul_comm, mul_left_comm, add_comm, add_left_comm, sub_eq_neg_add, mul_assoc]
-#align nat.xgcd_aux_P Nat.xgcd_aux_P
+#align nat.xgcd_aux_P Nat.xgcdAux_P
-/
#print Nat.gcd_eq_gcd_ab /-
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -233,6 +233,7 @@ theorem gcd_eq_gcd_ab : ∀ x y : ℤ, (gcd x y : ℤ) = x * gcdA x y + y * gcdB
#align int.gcd_eq_gcd_ab Int.gcd_eq_gcd_ab
-/
+#print Int.natAbs_ediv /-
theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natAbs b :=
by
cases Nat.eq_zero_or_pos (nat_abs b)
@@ -244,14 +245,19 @@ theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natA
_ = nat_abs (a / b * b) / nat_abs b := by rw [nat_abs_mul (a / b) b]
_ = nat_abs a / nat_abs b := by rw [Int.ediv_mul_cancel H]
#align int.nat_abs_div Int.natAbs_ediv
+-/
+#print Int.dvd_of_mul_dvd_mul_left /-
theorem dvd_of_mul_dvd_mul_left {i j k : ℤ} (k_non_zero : k ≠ 0) (H : k * i ∣ k * j) : i ∣ j :=
Dvd.elim H fun l H1 => by rw [mul_assoc] at H1 <;> exact ⟨_, mul_left_cancel₀ k_non_zero H1⟩
#align int.dvd_of_mul_dvd_mul_left Int.dvd_of_mul_dvd_mul_left
+-/
+#print Int.dvd_of_mul_dvd_mul_right /-
theorem dvd_of_mul_dvd_mul_right {i j k : ℤ} (k_non_zero : k ≠ 0) (H : i * k ∣ j * k) : i ∣ j := by
rw [mul_comm i k, mul_comm j k] at H <;> exact dvd_of_mul_dvd_mul_left k_non_zero H
#align int.dvd_of_mul_dvd_mul_right Int.dvd_of_mul_dvd_mul_right
+-/
#print Int.lcm /-
/-- ℤ specific version of least common multiple. -/
@@ -272,17 +278,23 @@ protected theorem coe_nat_lcm (m n : ℕ) : Int.lcm ↑m ↑n = Nat.lcm m n :=
#align int.coe_nat_lcm Int.coe_nat_lcm
-/
+#print Int.gcd_dvd_left /-
theorem gcd_dvd_left (i j : ℤ) : (gcd i j : ℤ) ∣ i :=
dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_left _ _
#align int.gcd_dvd_left Int.gcd_dvd_left
+-/
+#print Int.gcd_dvd_right /-
theorem gcd_dvd_right (i j : ℤ) : (gcd i j : ℤ) ∣ j :=
dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_right _ _
#align int.gcd_dvd_right Int.gcd_dvd_right
+-/
+#print Int.dvd_gcd /-
theorem dvd_gcd {i j k : ℤ} (h1 : k ∣ i) (h2 : k ∣ j) : k ∣ gcd i j :=
natAbs_dvd.1 <| coe_nat_dvd.2 <| Nat.dvd_gcd (natAbs_dvd_natAbs.2 h1) (natAbs_dvd_natAbs.2 h2)
#align int.dvd_gcd Int.dvd_gcd
+-/
#print Int.gcd_mul_lcm /-
theorem gcd_mul_lcm (i j : ℤ) : gcd i j * lcm i j = natAbs (i * j) := by
@@ -390,11 +402,13 @@ theorem gcd_pos_iff {i j : ℤ} : 0 < gcd i j ↔ i ≠ 0 ∨ j ≠ 0 :=
#align int.gcd_pos_iff Int.gcd_pos_iff
-/
+#print Int.gcd_div /-
theorem gcd_div {i j k : ℤ} (H1 : k ∣ i) (H2 : k ∣ j) : gcd (i / k) (j / k) = gcd i j / natAbs k :=
by
rw [gcd, nat_abs_div i k H1, nat_abs_div j k H2] <;>
exact Nat.gcd_div (nat_abs_dvd_iff_dvd.mpr H1) (nat_abs_dvd_iff_dvd.mpr H2)
#align int.gcd_div Int.gcd_div
+-/
#print Int.gcd_div_gcd_div_gcd /-
theorem gcd_div_gcd_div_gcd {i j : ℤ} (H : 0 < gcd i j) : gcd (i / gcd i j) (j / gcd i j) = 1 :=
@@ -404,13 +418,17 @@ theorem gcd_div_gcd_div_gcd {i j : ℤ} (H : 0 < gcd i j) : gcd (i / gcd i j) (j
#align int.gcd_div_gcd_div_gcd Int.gcd_div_gcd_div_gcd
-/
+#print Int.gcd_dvd_gcd_of_dvd_left /-
theorem gcd_dvd_gcd_of_dvd_left {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd i j ∣ gcd k j :=
Int.coe_nat_dvd.1 <| dvd_gcd ((gcd_dvd_left i j).trans H) (gcd_dvd_right i j)
#align int.gcd_dvd_gcd_of_dvd_left Int.gcd_dvd_gcd_of_dvd_left
+-/
+#print Int.gcd_dvd_gcd_of_dvd_right /-
theorem gcd_dvd_gcd_of_dvd_right {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd j i ∣ gcd j k :=
Int.coe_nat_dvd.1 <| dvd_gcd (gcd_dvd_left j i) ((gcd_dvd_right j i).trans H)
#align int.gcd_dvd_gcd_of_dvd_right Int.gcd_dvd_gcd_of_dvd_right
+-/
#print Int.gcd_dvd_gcd_mul_left /-
theorem gcd_dvd_gcd_mul_left (i j k : ℤ) : gcd i j ∣ gcd (k * i) j :=
@@ -436,13 +454,17 @@ theorem gcd_dvd_gcd_mul_right_right (i j k : ℤ) : gcd i j ∣ gcd i (j * k) :=
#align int.gcd_dvd_gcd_mul_right_right Int.gcd_dvd_gcd_mul_right_right
-/
+#print Int.gcd_eq_left /-
theorem gcd_eq_left {i j : ℤ} (H : i ∣ j) : gcd i j = natAbs i :=
Nat.dvd_antisymm (by unfold gcd <;> exact Nat.gcd_dvd_left _ _)
(by unfold gcd <;> exact Nat.dvd_gcd dvd_rfl (nat_abs_dvd_iff_dvd.mpr H))
#align int.gcd_eq_left Int.gcd_eq_left
+-/
+#print Int.gcd_eq_right /-
theorem gcd_eq_right {i j : ℤ} (H : j ∣ i) : gcd i j = natAbs j := by rw [gcd_comm, gcd_eq_left H]
#align int.gcd_eq_right Int.gcd_eq_right
+-/
#print Int.ne_zero_of_gcd /-
theorem ne_zero_of_gcd {x y : ℤ} (hc : gcd x y ≠ 0) : x ≠ 0 ∨ y ≠ 0 :=
@@ -468,6 +490,7 @@ theorem exists_gcd_one' {m n : ℤ} (H : 0 < gcd m n) :
#align int.exists_gcd_one' Int.exists_gcd_one'
-/
+#print Int.pow_dvd_pow_iff /-
theorem pow_dvd_pow_iff {m n : ℤ} {k : ℕ} (k0 : 0 < k) : m ^ k ∣ n ^ k ↔ m ∣ n :=
by
refine' ⟨fun h => _, fun h => pow_dvd_pow_of_dvd h _⟩
@@ -476,6 +499,7 @@ theorem pow_dvd_pow_iff {m n : ℤ} {k : ℕ} (k0 : 0 < k) : m ^ k ∣ n ^ k ↔
rw [← Int.natAbs_pow, ← Int.natAbs_pow]
exact int.nat_abs_dvd_iff_dvd.mpr h
#align int.pow_dvd_pow_iff Int.pow_dvd_pow_iff
+-/
#print Int.gcd_dvd_iff /-
theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑n = a * x + b * y :=
@@ -491,12 +515,15 @@ theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑
#align int.gcd_dvd_iff Int.gcd_dvd_iff
-/
+#print Int.gcd_greatest /-
theorem gcd_greatest {a b d : ℤ} (hd_pos : 0 ≤ d) (hda : d ∣ a) (hdb : d ∣ b)
(hd : ∀ e : ℤ, e ∣ a → e ∣ b → e ∣ d) : d = gcd a b :=
dvd_antisymm hd_pos (ofNat_zero_le (gcd a b)) (dvd_gcd hda hdb)
(hd _ (gcd_dvd_left a b) (gcd_dvd_right a b))
#align int.gcd_greatest Int.gcd_greatest
+-/
+#print Int.dvd_of_dvd_mul_left_of_gcd_one /-
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a c = 1` then `a ∣ b`.
Compare with `is_coprime.dvd_of_dvd_mul_left` and
`unique_factorization_monoid.dvd_of_dvd_mul_left_of_no_prime_factors` -/
@@ -508,13 +535,16 @@ theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab :
rw [← this]
exact dvd_add (dvd_mul_of_dvd_left (dvd_mul_left a b) _) (dvd_mul_of_dvd_left habc _)
#align int.dvd_of_dvd_mul_left_of_gcd_one Int.dvd_of_dvd_mul_left_of_gcd_one
+-/
+#print Int.dvd_of_dvd_mul_right_of_gcd_one /-
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a b = 1` then `a ∣ c`.
Compare with `is_coprime.dvd_of_dvd_mul_right` and
`unique_factorization_monoid.dvd_of_dvd_mul_right_of_no_prime_factors` -/
theorem dvd_of_dvd_mul_right_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a b = 1) :
a ∣ c := by rw [mul_comm] at habc ; exact dvd_of_dvd_mul_left_of_gcd_one habc hab
#align int.dvd_of_dvd_mul_right_of_gcd_one Int.dvd_of_dvd_mul_right_of_gcd_one
+-/
#print Int.gcd_least_linear /-
/-- For nonzero integers `a` and `b`, `gcd a b` is the smallest positive natural number that can be
@@ -574,23 +604,30 @@ theorem lcm_self (i : ℤ) : lcm i i = natAbs i := by rw [Int.lcm]; apply Nat.lc
#align int.lcm_self Int.lcm_self
-/
+#print Int.dvd_lcm_left /-
theorem dvd_lcm_left (i j : ℤ) : i ∣ lcm i j := by rw [Int.lcm]; apply coe_nat_dvd_right.mpr;
apply Nat.dvd_lcm_left
#align int.dvd_lcm_left Int.dvd_lcm_left
+-/
+#print Int.dvd_lcm_right /-
theorem dvd_lcm_right (i j : ℤ) : j ∣ lcm i j := by rw [Int.lcm]; apply coe_nat_dvd_right.mpr;
apply Nat.dvd_lcm_right
#align int.dvd_lcm_right Int.dvd_lcm_right
+-/
+#print Int.lcm_dvd /-
theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k :=
by
rw [Int.lcm]
intro hi hj
exact coe_nat_dvd_left.mpr (Nat.lcm_dvd (nat_abs_dvd_iff_dvd.mpr hi) (nat_abs_dvd_iff_dvd.mpr hj))
#align int.lcm_dvd Int.lcm_dvd
+-/
end Int
+#print pow_gcd_eq_one /-
theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m = 1) (hn : x ^ n = 1) :
x ^ m.gcd n = 1 := by
cases m; · simp only [hn, Nat.gcd_zero_left]
@@ -599,7 +636,9 @@ theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
rw [← Units.val_one, ← zpow_ofNat, ← Units.ext_iff] at *
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
+-/
+#print gcd_nsmul_eq_zero /-
theorem gcd_nsmul_eq_zero {M : Type _} [AddMonoid M] (x : M) {m n : ℕ} (hm : m • x = 0)
(hn : n • x = 0) : m.gcd n • x = 0 :=
by
@@ -607,6 +646,7 @@ theorem gcd_nsmul_eq_zero {M : Type _} [AddMonoid M] (x : M) {m n : ℕ} (hm : m
rw [ofAdd_nsmul, ofAdd_zero, pow_gcd_eq_one] <;>
rwa [← ofAdd_nsmul, ← ofAdd_zero, Equiv.apply_eq_iff_eq]
#align gcd_nsmul_eq_zero gcd_nsmul_eq_zero
+-/
attribute [to_additive gcd_nsmul_eq_zero] pow_gcd_eq_one
@@ -619,6 +659,7 @@ namespace Tactic
namespace NormNum
+#print Tactic.NormNum.int_gcd_helper' /-
theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂ : (d : ℤ) ∣ y)
(h₃ : x * a + y * b = d) : Int.gcd x y = d :=
by
@@ -628,15 +669,21 @@ theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂
· exact (Int.gcd_dvd_left _ _).mul_right _
· exact (Int.gcd_dvd_right _ _).mul_right _
#align tactic.norm_num.int_gcd_helper' Tactic.NormNum.int_gcd_helper'
+-/
+#print Tactic.NormNum.nat_gcd_helper_dvd_left /-
theorem nat_gcd_helper_dvd_left (x y a : ℕ) (h : x * a = y) : Nat.gcd x y = x :=
Nat.gcd_eq_left ⟨a, h.symm⟩
#align tactic.norm_num.nat_gcd_helper_dvd_left Tactic.NormNum.nat_gcd_helper_dvd_left
+-/
+#print Tactic.NormNum.nat_gcd_helper_dvd_right /-
theorem nat_gcd_helper_dvd_right (x y a : ℕ) (h : y * a = x) : Nat.gcd x y = y :=
Nat.gcd_eq_right ⟨a, h.symm⟩
#align tactic.norm_num.nat_gcd_helper_dvd_right Tactic.NormNum.nat_gcd_helper_dvd_right
+-/
+#print Tactic.NormNum.nat_gcd_helper_2 /-
theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
(hx : x * a = tx) (hy : y * b = ty) (h : ty + d = tx) : Nat.gcd x y = d :=
by
@@ -646,16 +693,21 @@ theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d *
rw [mul_neg, ← sub_eq_add_neg, sub_eq_iff_eq_add']
norm_cast; rw [hx, hy, h]
#align tactic.norm_num.nat_gcd_helper_2 Tactic.NormNum.nat_gcd_helper_2
+-/
+#print Tactic.NormNum.nat_gcd_helper_1 /-
theorem nat_gcd_helper_1 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
(hx : x * a = tx) (hy : y * b = ty) (h : tx + d = ty) : Nat.gcd x y = d :=
(Nat.gcd_comm _ _).trans <| nat_gcd_helper_2 _ _ _ _ _ _ _ _ _ hv hu hy hx h
#align tactic.norm_num.nat_gcd_helper_1 Tactic.NormNum.nat_gcd_helper_1
+-/
+#print Tactic.NormNum.nat_lcm_helper /-
theorem nat_lcm_helper (x y d m n : ℕ) (hd : Nat.gcd x y = d) (d0 : 0 < d) (xy : x * y = n)
(dm : d * m = n) : Nat.lcm x y = m :=
mul_right_injective₀ d0.ne' <| by rw [dm, ← xy, ← hd, Nat.gcd_mul_lcm]
#align tactic.norm_num.nat_lcm_helper Tactic.NormNum.nat_lcm_helper
+-/
theorem nat_coprime_helper_zero_left (x : ℕ) (h : 1 < x) : ¬Nat.coprime 0 x :=
mt (Nat.coprime_zero_left _).1 <| ne_of_gt h
@@ -680,9 +732,11 @@ theorem nat_not_coprime_helper (d x y u v : ℕ) (hu : d * u = x) (hv : d * v =
Nat.not_coprime_of_dvd_of_dvd h ⟨_, hu.symm⟩ ⟨_, hv.symm⟩
#align tactic.norm_num.nat_not_coprime_helper Tactic.NormNum.nat_not_coprime_helper
+#print Tactic.NormNum.int_gcd_helper /-
theorem int_gcd_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
(h : Nat.gcd nx ny = d) : Int.gcd x y = d := by rwa [← hx, ← hy, Int.coe_nat_gcd]
#align tactic.norm_num.int_gcd_helper Tactic.NormNum.int_gcd_helper
+-/
theorem int_gcd_helper_neg_left (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : Int.gcd (-x) y = d := by
rw [Int.gcd] at h ⊢ <;> rwa [Int.natAbs_neg]
@@ -692,9 +746,11 @@ theorem int_gcd_helper_neg_right (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : I
rw [Int.gcd] at h ⊢ <;> rwa [Int.natAbs_neg]
#align tactic.norm_num.int_gcd_helper_neg_right Tactic.NormNum.int_gcd_helper_neg_right
+#print Tactic.NormNum.int_lcm_helper /-
theorem int_lcm_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
(h : Nat.lcm nx ny = d) : Int.lcm x y = d := by rwa [← hx, ← hy, Int.coe_nat_lcm]
#align tactic.norm_num.int_lcm_helper Tactic.NormNum.int_lcm_helper
+-/
theorem int_lcm_helper_neg_left (x y : ℤ) (d : ℕ) (h : Int.lcm x y = d) : Int.lcm (-x) y = d := by
rw [Int.lcm] at h ⊢ <;> rwa [Int.natAbs_neg]
mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0
@@ -243,7 +243,6 @@ theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natA
_ = nat_abs (a / b) * nat_abs b / nat_abs b := by rw [Nat.mul_div_assoc _ dvd_rfl]
_ = nat_abs (a / b * b) / nat_abs b := by rw [nat_abs_mul (a / b) b]
_ = nat_abs a / nat_abs b := by rw [Int.ediv_mul_cancel H]
-
#align int.nat_abs_div Int.natAbs_ediv
theorem dvd_of_mul_dvd_mul_left {i j k : ℤ} (k_non_zero : k ≠ 0) (H : k * i ∣ k * j) : i ∣ j :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -521,7 +521,7 @@ theorem dvd_of_dvd_mul_right_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab
/-- For nonzero integers `a` and `b`, `gcd a b` is the smallest positive natural number that can be
written in the form `a * x + b * y` for some pair of integers `x` and `y` -/
theorem gcd_least_linear {a b : ℤ} (ha : a ≠ 0) :
- IsLeast { n : ℕ | 0 < n ∧ ∃ x y : ℤ, ↑n = a * x + b * y } (a.gcd b) :=
+ IsLeast {n : ℕ | 0 < n ∧ ∃ x y : ℤ, ↑n = a * x + b * y} (a.gcd b) :=
by
simp_rw [← gcd_dvd_iff]
constructor
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -58,7 +58,7 @@ theorem xgcd_zero_left {s t r' s' t'} : xgcdAux 0 s t r' s' t' = (r', s', t') :=
#print Nat.xgcd_aux_rec /-
theorem xgcd_aux_rec {r s t r' s' t'} (h : 0 < r) :
xgcdAux r s t r' s' t' = xgcdAux (r' % r) (s' - r' / r * s) (t' - r' / r * t) r s t := by
- cases r <;> [exact absurd h (lt_irrefl _);· simp only [xgcd_aux]; rfl]
+ cases r <;> [exact absurd h (lt_irrefl _); · simp only [xgcd_aux]; rfl]
#align nat.xgcd_aux_rec Nat.xgcd_aux_rec
-/
@@ -163,7 +163,7 @@ theorem xgcd_aux_P {r r'} :
-/
theorem gcd_eq_gcd_ab : (gcd x y : ℤ) = x * gcdA x y + y * gcdB x y := by
have := @xgcd_aux_P x y x y 1 0 0 1 (by simp [P]) (by simp [P]) <;>
- rwa [xgcd_aux_val, xgcd_val] at this
+ rwa [xgcd_aux_val, xgcd_val] at this
#align nat.gcd_eq_gcd_ab Nat.gcd_eq_gcd_ab
-/
@@ -174,8 +174,8 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
by
have hk' := int.coe_nat_ne_zero.mpr (ne_of_gt (lt_of_le_of_lt (zero_le (gcd n k)) hk))
have key := congr_arg (fun m => Int.natMod m k) (gcd_eq_gcd_ab n k)
- simp_rw [Int.natMod] at key
- rw [Int.add_mul_emod_self_left, ← Int.coe_nat_mod, Int.toNat_coe_nat, mod_eq_of_lt hk] at key
+ simp_rw [Int.natMod] at key
+ rw [Int.add_mul_emod_self_left, ← Int.coe_nat_mod, Int.toNat_coe_nat, mod_eq_of_lt hk] at key
refine' ⟨(n.gcd_a k % k).toNat, Eq.trans (Int.ofNat.inj _) key.symm⟩
rw [Int.coe_nat_mod, Int.ofNat_mul, Int.toNat_of_nonneg (Int.emod_nonneg _ hk'),
Int.toNat_of_nonneg (Int.emod_nonneg _ hk'), Int.mul_emod, Int.emod_emod, ← Int.mul_emod]
@@ -247,11 +247,11 @@ theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natA
#align int.nat_abs_div Int.natAbs_ediv
theorem dvd_of_mul_dvd_mul_left {i j k : ℤ} (k_non_zero : k ≠ 0) (H : k * i ∣ k * j) : i ∣ j :=
- Dvd.elim H fun l H1 => by rw [mul_assoc] at H1 <;> exact ⟨_, mul_left_cancel₀ k_non_zero H1⟩
+ Dvd.elim H fun l H1 => by rw [mul_assoc] at H1 <;> exact ⟨_, mul_left_cancel₀ k_non_zero H1⟩
#align int.dvd_of_mul_dvd_mul_left Int.dvd_of_mul_dvd_mul_left
theorem dvd_of_mul_dvd_mul_right {i j k : ℤ} (k_non_zero : k ≠ 0) (H : i * k ∣ j * k) : i ∣ j := by
- rw [mul_comm i k, mul_comm j k] at H <;> exact dvd_of_mul_dvd_mul_left k_non_zero H
+ rw [mul_comm i k, mul_comm j k] at H <;> exact dvd_of_mul_dvd_mul_left k_non_zero H
#align int.dvd_of_mul_dvd_mul_right Int.dvd_of_mul_dvd_mul_right
#print Int.lcm /-
@@ -463,7 +463,7 @@ theorem exists_gcd_one {m n : ℤ} (H : 0 < gcd m n) :
#print Int.exists_gcd_one' /-
theorem exists_gcd_one' {m n : ℤ} (H : 0 < gcd m n) :
- ∃ (g : ℕ)(m' n' : ℤ), 0 < g ∧ gcd m' n' = 1 ∧ m = m' * g ∧ n = n' * g :=
+ ∃ (g : ℕ) (m' n' : ℤ), 0 < g ∧ gcd m' n' = 1 ∧ m = m' * g ∧ n = n' * g :=
let ⟨m', n', h⟩ := exists_gcd_one H
⟨_, m', n', H, h⟩
#align int.exists_gcd_one' Int.exists_gcd_one'
@@ -504,7 +504,7 @@ Compare with `is_coprime.dvd_of_dvd_mul_left` and
theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a c = 1) : a ∣ b :=
by
have := gcd_eq_gcd_ab a c
- simp only [hab, Int.ofNat_zero, Int.ofNat_succ, zero_add] at this
+ simp only [hab, Int.ofNat_zero, Int.ofNat_succ, zero_add] at this
have : b * a * gcd_a a c + b * c * gcd_b a c = b := by simp [mul_assoc, ← mul_add, ← this]
rw [← this]
exact dvd_add (dvd_mul_of_dvd_left (dvd_mul_left a b) _) (dvd_mul_of_dvd_left habc _)
@@ -514,7 +514,7 @@ theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab :
Compare with `is_coprime.dvd_of_dvd_mul_right` and
`unique_factorization_monoid.dvd_of_dvd_mul_right_of_no_prime_factors` -/
theorem dvd_of_dvd_mul_right_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a b = 1) :
- a ∣ c := by rw [mul_comm] at habc; exact dvd_of_dvd_mul_left_of_gcd_one habc hab
+ a ∣ c := by rw [mul_comm] at habc ; exact dvd_of_dvd_mul_left_of_gcd_one habc hab
#align int.dvd_of_dvd_mul_right_of_gcd_one Int.dvd_of_dvd_mul_right_of_gcd_one
#print Int.gcd_least_linear /-
@@ -686,11 +686,11 @@ theorem int_gcd_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (
#align tactic.norm_num.int_gcd_helper Tactic.NormNum.int_gcd_helper
theorem int_gcd_helper_neg_left (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : Int.gcd (-x) y = d := by
- rw [Int.gcd] at h⊢ <;> rwa [Int.natAbs_neg]
+ rw [Int.gcd] at h ⊢ <;> rwa [Int.natAbs_neg]
#align tactic.norm_num.int_gcd_helper_neg_left Tactic.NormNum.int_gcd_helper_neg_left
theorem int_gcd_helper_neg_right (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : Int.gcd x (-y) = d := by
- rw [Int.gcd] at h⊢ <;> rwa [Int.natAbs_neg]
+ rw [Int.gcd] at h ⊢ <;> rwa [Int.natAbs_neg]
#align tactic.norm_num.int_gcd_helper_neg_right Tactic.NormNum.int_gcd_helper_neg_right
theorem int_lcm_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
@@ -698,11 +698,11 @@ theorem int_lcm_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (
#align tactic.norm_num.int_lcm_helper Tactic.NormNum.int_lcm_helper
theorem int_lcm_helper_neg_left (x y : ℤ) (d : ℕ) (h : Int.lcm x y = d) : Int.lcm (-x) y = d := by
- rw [Int.lcm] at h⊢ <;> rwa [Int.natAbs_neg]
+ rw [Int.lcm] at h ⊢ <;> rwa [Int.natAbs_neg]
#align tactic.norm_num.int_lcm_helper_neg_left Tactic.NormNum.int_lcm_helper_neg_left
theorem int_lcm_helper_neg_right (x y : ℤ) (d : ℕ) (h : Int.lcm x y = d) : Int.lcm x (-y) = d := by
- rw [Int.lcm] at h⊢ <;> rwa [Int.natAbs_neg]
+ rw [Int.lcm] at h ⊢ <;> rwa [Int.natAbs_neg]
#align tactic.norm_num.int_lcm_helper_neg_right Tactic.NormNum.int_lcm_helper_neg_right
/-- Evaluates the `nat.gcd` function. -/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -233,12 +233,6 @@ theorem gcd_eq_gcd_ab : ∀ x y : ℤ, (gcd x y : ℤ) = x * gcdA x y + y * gcdB
#align int.gcd_eq_gcd_ab Int.gcd_eq_gcd_ab
-/
-/- warning: int.nat_abs_div -> Int.natAbs_ediv is a dubious translation:
-lean 3 declaration is
- forall (a : Int) (b : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) b a) -> (Eq.{1} Nat (Int.natAbs (HDiv.hDiv.{0, 0, 0} Int Int Int (instHDiv.{0} Int Int.hasDiv) a b)) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.hasDiv) (Int.natAbs a) (Int.natAbs b)))
-but is expected to have type
- forall (a : Int) (b : Int), (Dvd.dvd.{0} Int Int.instDvdInt b a) -> (Eq.{1} Nat (Int.natAbs (HDiv.hDiv.{0, 0, 0} Int Int Int (instHDiv.{0} Int Int.instDivInt_1) a b)) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.instDivNat) (Int.natAbs a) (Int.natAbs b)))
-Case conversion may be inaccurate. Consider using '#align int.nat_abs_div Int.natAbs_edivₓ'. -/
theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natAbs b :=
by
cases Nat.eq_zero_or_pos (nat_abs b)
@@ -252,22 +246,10 @@ theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natA
#align int.nat_abs_div Int.natAbs_ediv
-/- warning: int.dvd_of_mul_dvd_mul_left -> Int.dvd_of_mul_dvd_mul_left is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {j : Int} {k : Int}, (Ne.{1} Int k (OfNat.ofNat.{0} Int 0 (OfNat.mk.{0} Int 0 (Zero.zero.{0} Int Int.hasZero)))) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) k i) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) k j)) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i j)
-but is expected to have type
- forall {i : Int} {j : Int} {k : Int}, (Ne.{1} Int k (OfNat.ofNat.{0} Int 0 (instOfNatInt 0))) -> (Dvd.dvd.{0} Int Int.instDvdInt (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) k i) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) k j)) -> (Dvd.dvd.{0} Int Int.instDvdInt i j)
-Case conversion may be inaccurate. Consider using '#align int.dvd_of_mul_dvd_mul_left Int.dvd_of_mul_dvd_mul_leftₓ'. -/
theorem dvd_of_mul_dvd_mul_left {i j k : ℤ} (k_non_zero : k ≠ 0) (H : k * i ∣ k * j) : i ∣ j :=
Dvd.elim H fun l H1 => by rw [mul_assoc] at H1 <;> exact ⟨_, mul_left_cancel₀ k_non_zero H1⟩
#align int.dvd_of_mul_dvd_mul_left Int.dvd_of_mul_dvd_mul_left
-/- warning: int.dvd_of_mul_dvd_mul_right -> Int.dvd_of_mul_dvd_mul_right is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {j : Int} {k : Int}, (Ne.{1} Int k (OfNat.ofNat.{0} Int 0 (OfNat.mk.{0} Int 0 (Zero.zero.{0} Int Int.hasZero)))) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) i k) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) j k)) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i j)
-but is expected to have type
- forall {i : Int} {j : Int} {k : Int}, (Ne.{1} Int k (OfNat.ofNat.{0} Int 0 (instOfNatInt 0))) -> (Dvd.dvd.{0} Int Int.instDvdInt (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) i k) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) j k)) -> (Dvd.dvd.{0} Int Int.instDvdInt i j)
-Case conversion may be inaccurate. Consider using '#align int.dvd_of_mul_dvd_mul_right Int.dvd_of_mul_dvd_mul_rightₓ'. -/
theorem dvd_of_mul_dvd_mul_right {i j k : ℤ} (k_non_zero : k ≠ 0) (H : i * k ∣ j * k) : i ∣ j := by
rw [mul_comm i k, mul_comm j k] at H <;> exact dvd_of_mul_dvd_mul_left k_non_zero H
#align int.dvd_of_mul_dvd_mul_right Int.dvd_of_mul_dvd_mul_right
@@ -291,32 +273,14 @@ protected theorem coe_nat_lcm (m n : ℕ) : Int.lcm ↑m ↑n = Nat.lcm m n :=
#align int.coe_nat_lcm Int.coe_nat_lcm
-/
-/- warning: int.gcd_dvd_left -> Int.gcd_dvd_left is a dubious translation:
-lean 3 declaration is
- forall (i : Int) (j : Int), 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))) (Int.gcd i j)) i
-but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt (Int.gcd i j)) i
-Case conversion may be inaccurate. Consider using '#align int.gcd_dvd_left Int.gcd_dvd_leftₓ'. -/
theorem gcd_dvd_left (i j : ℤ) : (gcd i j : ℤ) ∣ i :=
dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_left _ _
#align int.gcd_dvd_left Int.gcd_dvd_left
-/- warning: int.gcd_dvd_right -> Int.gcd_dvd_right is a dubious translation:
-lean 3 declaration is
- forall (i : Int) (j : Int), 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))) (Int.gcd i j)) j
-but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt (Int.gcd i j)) j
-Case conversion may be inaccurate. Consider using '#align int.gcd_dvd_right Int.gcd_dvd_rightₓ'. -/
theorem gcd_dvd_right (i j : ℤ) : (gcd i j : ℤ) ∣ j :=
dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_right _ _
#align int.gcd_dvd_right Int.gcd_dvd_right
-/- warning: int.dvd_gcd -> Int.dvd_gcd is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {j : Int} {k : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k i) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k j) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k ((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))) (Int.gcd i j)))
-but is expected to have type
- forall {i : Int} {j : Int} {k : Int}, (Dvd.dvd.{0} Int Int.instDvdInt k i) -> (Dvd.dvd.{0} Int Int.instDvdInt k j) -> (Dvd.dvd.{0} Int Int.instDvdInt k (Nat.cast.{0} Int instNatCastInt (Int.gcd i j)))
-Case conversion may be inaccurate. Consider using '#align int.dvd_gcd Int.dvd_gcdₓ'. -/
theorem dvd_gcd {i j k : ℤ} (h1 : k ∣ i) (h2 : k ∣ j) : k ∣ gcd i j :=
natAbs_dvd.1 <| coe_nat_dvd.2 <| Nat.dvd_gcd (natAbs_dvd_natAbs.2 h1) (natAbs_dvd_natAbs.2 h2)
#align int.dvd_gcd Int.dvd_gcd
@@ -427,12 +391,6 @@ theorem gcd_pos_iff {i j : ℤ} : 0 < gcd i j ↔ i ≠ 0 ∨ j ≠ 0 :=
#align int.gcd_pos_iff Int.gcd_pos_iff
-/
-/- warning: int.gcd_div -> Int.gcd_div is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {j : Int} {k : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k i) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k j) -> (Eq.{1} Nat (Int.gcd (HDiv.hDiv.{0, 0, 0} Int Int Int (instHDiv.{0} Int Int.hasDiv) i k) (HDiv.hDiv.{0, 0, 0} Int Int Int (instHDiv.{0} Int Int.hasDiv) j k)) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.hasDiv) (Int.gcd i j) (Int.natAbs k)))
-but is expected to have type
- forall {i : Int} {j : Int} {k : Int}, (Dvd.dvd.{0} Int Int.instDvdInt k i) -> (Dvd.dvd.{0} Int Int.instDvdInt k j) -> (Eq.{1} Nat (Int.gcd (HDiv.hDiv.{0, 0, 0} Int Int Int (instHDiv.{0} Int Int.instDivInt_1) i k) (HDiv.hDiv.{0, 0, 0} Int Int Int (instHDiv.{0} Int Int.instDivInt_1) j k)) (HDiv.hDiv.{0, 0, 0} Nat Nat Nat (instHDiv.{0} Nat Nat.instDivNat) (Int.gcd i j) (Int.natAbs k)))
-Case conversion may be inaccurate. Consider using '#align int.gcd_div Int.gcd_divₓ'. -/
theorem gcd_div {i j k : ℤ} (H1 : k ∣ i) (H2 : k ∣ j) : gcd (i / k) (j / k) = gcd i j / natAbs k :=
by
rw [gcd, nat_abs_div i k H1, nat_abs_div j k H2] <;>
@@ -447,22 +405,10 @@ theorem gcd_div_gcd_div_gcd {i j : ℤ} (H : 0 < gcd i j) : gcd (i / gcd i j) (j
#align int.gcd_div_gcd_div_gcd Int.gcd_div_gcd_div_gcd
-/
-/- warning: int.gcd_dvd_gcd_of_dvd_left -> Int.gcd_dvd_gcd_of_dvd_left is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {k : Int} (j : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i k) -> (Dvd.Dvd.{0} Nat Nat.hasDvd (Int.gcd i j) (Int.gcd k j))
-but is expected to have type
- forall {i : Int} {k : Int} (j : Int), (Dvd.dvd.{0} Int Int.instDvdInt i k) -> (Dvd.dvd.{0} Nat Nat.instDvdNat (Int.gcd i j) (Int.gcd k j))
-Case conversion may be inaccurate. Consider using '#align int.gcd_dvd_gcd_of_dvd_left Int.gcd_dvd_gcd_of_dvd_leftₓ'. -/
theorem gcd_dvd_gcd_of_dvd_left {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd i j ∣ gcd k j :=
Int.coe_nat_dvd.1 <| dvd_gcd ((gcd_dvd_left i j).trans H) (gcd_dvd_right i j)
#align int.gcd_dvd_gcd_of_dvd_left Int.gcd_dvd_gcd_of_dvd_left
-/- warning: int.gcd_dvd_gcd_of_dvd_right -> Int.gcd_dvd_gcd_of_dvd_right is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {k : Int} (j : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i k) -> (Dvd.Dvd.{0} Nat Nat.hasDvd (Int.gcd j i) (Int.gcd j k))
-but is expected to have type
- forall {i : Int} {k : Int} (j : Int), (Dvd.dvd.{0} Int Int.instDvdInt i k) -> (Dvd.dvd.{0} Nat Nat.instDvdNat (Int.gcd j i) (Int.gcd j k))
-Case conversion may be inaccurate. Consider using '#align int.gcd_dvd_gcd_of_dvd_right Int.gcd_dvd_gcd_of_dvd_rightₓ'. -/
theorem gcd_dvd_gcd_of_dvd_right {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd j i ∣ gcd j k :=
Int.coe_nat_dvd.1 <| dvd_gcd (gcd_dvd_left j i) ((gcd_dvd_right j i).trans H)
#align int.gcd_dvd_gcd_of_dvd_right Int.gcd_dvd_gcd_of_dvd_right
@@ -491,23 +437,11 @@ theorem gcd_dvd_gcd_mul_right_right (i j k : ℤ) : gcd i j ∣ gcd i (j * k) :=
#align int.gcd_dvd_gcd_mul_right_right Int.gcd_dvd_gcd_mul_right_right
-/
-/- warning: int.gcd_eq_left -> Int.gcd_eq_left is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {j : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i j) -> (Eq.{1} Nat (Int.gcd i j) (Int.natAbs i))
-but is expected to have type
- forall {i : Int} {j : Int}, (Dvd.dvd.{0} Int Int.instDvdInt i j) -> (Eq.{1} Nat (Int.gcd i j) (Int.natAbs i))
-Case conversion may be inaccurate. Consider using '#align int.gcd_eq_left Int.gcd_eq_leftₓ'. -/
theorem gcd_eq_left {i j : ℤ} (H : i ∣ j) : gcd i j = natAbs i :=
Nat.dvd_antisymm (by unfold gcd <;> exact Nat.gcd_dvd_left _ _)
(by unfold gcd <;> exact Nat.dvd_gcd dvd_rfl (nat_abs_dvd_iff_dvd.mpr H))
#align int.gcd_eq_left Int.gcd_eq_left
-/- warning: int.gcd_eq_right -> Int.gcd_eq_right is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {j : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) j i) -> (Eq.{1} Nat (Int.gcd i j) (Int.natAbs j))
-but is expected to have type
- forall {i : Int} {j : Int}, (Dvd.dvd.{0} Int Int.instDvdInt j i) -> (Eq.{1} Nat (Int.gcd i j) (Int.natAbs j))
-Case conversion may be inaccurate. Consider using '#align int.gcd_eq_right Int.gcd_eq_rightₓ'. -/
theorem gcd_eq_right {i j : ℤ} (H : j ∣ i) : gcd i j = natAbs j := by rw [gcd_comm, gcd_eq_left H]
#align int.gcd_eq_right Int.gcd_eq_right
@@ -535,12 +469,6 @@ theorem exists_gcd_one' {m n : ℤ} (H : 0 < gcd m n) :
#align int.exists_gcd_one' Int.exists_gcd_one'
-/
-/- warning: int.pow_dvd_pow_iff -> Int.pow_dvd_pow_iff is a dubious translation:
-lean 3 declaration is
- forall {m : Int} {n : Int} {k : Nat}, (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) k) -> (Iff (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) (HPow.hPow.{0, 0, 0} Int Nat Int (instHPow.{0, 0} Int Nat (Monoid.Pow.{0} Int Int.monoid)) m k) (HPow.hPow.{0, 0, 0} Int Nat Int (instHPow.{0, 0} Int Nat (Monoid.Pow.{0} Int Int.monoid)) n k)) (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) m n))
-but is expected to have type
- forall {m : Int} {n : Int} {k : Nat}, (LT.lt.{0} Nat instLTNat (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0)) k) -> (Iff (Dvd.dvd.{0} Int Int.instDvdInt (HPow.hPow.{0, 0, 0} Int Nat Int Int.instHPowIntNat m k) (HPow.hPow.{0, 0, 0} Int Nat Int Int.instHPowIntNat n k)) (Dvd.dvd.{0} Int Int.instDvdInt m n))
-Case conversion may be inaccurate. Consider using '#align int.pow_dvd_pow_iff Int.pow_dvd_pow_iffₓ'. -/
theorem pow_dvd_pow_iff {m n : ℤ} {k : ℕ} (k0 : 0 < k) : m ^ k ∣ n ^ k ↔ m ∣ n :=
by
refine' ⟨fun h => _, fun h => pow_dvd_pow_of_dvd h _⟩
@@ -564,24 +492,12 @@ theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑
#align int.gcd_dvd_iff Int.gcd_dvd_iff
-/
-/- warning: int.gcd_greatest -> Int.gcd_greatest is a dubious translation:
-lean 3 declaration is
- forall {a : Int} {b : Int} {d : Int}, (LE.le.{0} Int Int.hasLe (OfNat.ofNat.{0} Int 0 (OfNat.mk.{0} Int 0 (Zero.zero.{0} Int Int.hasZero))) d) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) d a) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) d b) -> (forall (e : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) e a) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) e b) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) e d)) -> (Eq.{1} Int d ((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))) (Int.gcd a b)))
-but is expected to have type
- forall {a : Int} {b : Int} {d : Int}, (LE.le.{0} Int Int.instLEInt (OfNat.ofNat.{0} Int 0 (instOfNatInt 0)) d) -> (Dvd.dvd.{0} Int Int.instDvdInt d a) -> (Dvd.dvd.{0} Int Int.instDvdInt d b) -> (forall (e : Int), (Dvd.dvd.{0} Int Int.instDvdInt e a) -> (Dvd.dvd.{0} Int Int.instDvdInt e b) -> (Dvd.dvd.{0} Int Int.instDvdInt e d)) -> (Eq.{1} Int d (Nat.cast.{0} Int instNatCastInt (Int.gcd a b)))
-Case conversion may be inaccurate. Consider using '#align int.gcd_greatest Int.gcd_greatestₓ'. -/
theorem gcd_greatest {a b d : ℤ} (hd_pos : 0 ≤ d) (hda : d ∣ a) (hdb : d ∣ b)
(hd : ∀ e : ℤ, e ∣ a → e ∣ b → e ∣ d) : d = gcd a b :=
dvd_antisymm hd_pos (ofNat_zero_le (gcd a b)) (dvd_gcd hda hdb)
(hd _ (gcd_dvd_left a b) (gcd_dvd_right a b))
#align int.gcd_greatest Int.gcd_greatest
-/- warning: int.dvd_of_dvd_mul_left_of_gcd_one -> Int.dvd_of_dvd_mul_left_of_gcd_one is a dubious translation:
-lean 3 declaration is
- forall {a : Int} {b : Int} {c : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) a (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) b c)) -> (Eq.{1} Nat (Int.gcd a c) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) a b)
-but is expected to have type
- forall {a : Int} {b : Int} {c : Int}, (Dvd.dvd.{0} Int Int.instDvdInt a (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) b c)) -> (Eq.{1} Nat (Int.gcd a c) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) -> (Dvd.dvd.{0} Int Int.instDvdInt a b)
-Case conversion may be inaccurate. Consider using '#align int.dvd_of_dvd_mul_left_of_gcd_one Int.dvd_of_dvd_mul_left_of_gcd_oneₓ'. -/
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a c = 1` then `a ∣ b`.
Compare with `is_coprime.dvd_of_dvd_mul_left` and
`unique_factorization_monoid.dvd_of_dvd_mul_left_of_no_prime_factors` -/
@@ -594,12 +510,6 @@ theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab :
exact dvd_add (dvd_mul_of_dvd_left (dvd_mul_left a b) _) (dvd_mul_of_dvd_left habc _)
#align int.dvd_of_dvd_mul_left_of_gcd_one Int.dvd_of_dvd_mul_left_of_gcd_one
-/- warning: int.dvd_of_dvd_mul_right_of_gcd_one -> Int.dvd_of_dvd_mul_right_of_gcd_one is a dubious translation:
-lean 3 declaration is
- forall {a : Int} {b : Int} {c : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) a (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) b c)) -> (Eq.{1} Nat (Int.gcd a b) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) a c)
-but is expected to have type
- forall {a : Int} {b : Int} {c : Int}, (Dvd.dvd.{0} Int Int.instDvdInt a (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) b c)) -> (Eq.{1} Nat (Int.gcd a b) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) -> (Dvd.dvd.{0} Int Int.instDvdInt a c)
-Case conversion may be inaccurate. Consider using '#align int.dvd_of_dvd_mul_right_of_gcd_one Int.dvd_of_dvd_mul_right_of_gcd_oneₓ'. -/
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a b = 1` then `a ∣ c`.
Compare with `is_coprime.dvd_of_dvd_mul_right` and
`unique_factorization_monoid.dvd_of_dvd_mul_right_of_no_prime_factors` -/
@@ -665,32 +575,14 @@ theorem lcm_self (i : ℤ) : lcm i i = natAbs i := by rw [Int.lcm]; apply Nat.lc
#align int.lcm_self Int.lcm_self
-/
-/- warning: int.dvd_lcm_left -> Int.dvd_lcm_left is a dubious translation:
-lean 3 declaration is
- forall (i : Int) (j : Int), Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i ((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))) (Int.lcm i j))
-but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt i (Nat.cast.{0} Int instNatCastInt (Int.lcm i j))
-Case conversion may be inaccurate. Consider using '#align int.dvd_lcm_left Int.dvd_lcm_leftₓ'. -/
theorem dvd_lcm_left (i j : ℤ) : i ∣ lcm i j := by rw [Int.lcm]; apply coe_nat_dvd_right.mpr;
apply Nat.dvd_lcm_left
#align int.dvd_lcm_left Int.dvd_lcm_left
-/- warning: int.dvd_lcm_right -> Int.dvd_lcm_right is a dubious translation:
-lean 3 declaration is
- forall (i : Int) (j : Int), Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) j ((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))) (Int.lcm i j))
-but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt j (Nat.cast.{0} Int instNatCastInt (Int.lcm i j))
-Case conversion may be inaccurate. Consider using '#align int.dvd_lcm_right Int.dvd_lcm_rightₓ'. -/
theorem dvd_lcm_right (i j : ℤ) : j ∣ lcm i j := by rw [Int.lcm]; apply coe_nat_dvd_right.mpr;
apply Nat.dvd_lcm_right
#align int.dvd_lcm_right Int.dvd_lcm_right
-/- warning: int.lcm_dvd -> Int.lcm_dvd is a dubious translation:
-lean 3 declaration is
- forall {i : Int} {j : Int} {k : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i k) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) j k) -> (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))) (Int.lcm i j)) k)
-but is expected to have type
- forall {i : Int} {j : Int} {k : Int}, (Dvd.dvd.{0} Int Int.instDvdInt i k) -> (Dvd.dvd.{0} Int Int.instDvdInt j k) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt (Int.lcm i j)) k)
-Case conversion may be inaccurate. Consider using '#align int.lcm_dvd Int.lcm_dvdₓ'. -/
theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k :=
by
rw [Int.lcm]
@@ -700,12 +592,6 @@ theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k :=
end Int
-/- warning: pow_gcd_eq_one -> pow_gcd_eq_one is a dubious translation:
-lean 3 declaration is
- forall {M : Type.{u1}} [_inst_1 : Monoid.{u1} M] (x : M) {m : Nat} {n : Nat}, (Eq.{succ u1} M (HPow.hPow.{u1, 0, u1} M Nat M (instHPow.{u1, 0} M Nat (Monoid.Pow.{u1} M _inst_1)) x m) (OfNat.ofNat.{u1} M 1 (OfNat.mk.{u1} M 1 (One.one.{u1} M (MulOneClass.toHasOne.{u1} M (Monoid.toMulOneClass.{u1} M _inst_1)))))) -> (Eq.{succ u1} M (HPow.hPow.{u1, 0, u1} M Nat M (instHPow.{u1, 0} M Nat (Monoid.Pow.{u1} M _inst_1)) x n) (OfNat.ofNat.{u1} M 1 (OfNat.mk.{u1} M 1 (One.one.{u1} M (MulOneClass.toHasOne.{u1} M (Monoid.toMulOneClass.{u1} M _inst_1)))))) -> (Eq.{succ u1} M (HPow.hPow.{u1, 0, u1} M Nat M (instHPow.{u1, 0} M Nat (Monoid.Pow.{u1} M _inst_1)) x (Nat.gcd m n)) (OfNat.ofNat.{u1} M 1 (OfNat.mk.{u1} M 1 (One.one.{u1} M (MulOneClass.toHasOne.{u1} M (Monoid.toMulOneClass.{u1} M _inst_1))))))
-but is expected to have type
- forall {M : Type.{u1}} [_inst_1 : Monoid.{u1} M] (x : M) {m : Nat} {n : Nat}, (Eq.{succ u1} M (HPow.hPow.{u1, 0, u1} M Nat M (instHPow.{u1, 0} M Nat (Monoid.Pow.{u1} M _inst_1)) x m) (OfNat.ofNat.{u1} M 1 (One.toOfNat1.{u1} M (Monoid.toOne.{u1} M _inst_1)))) -> (Eq.{succ u1} M (HPow.hPow.{u1, 0, u1} M Nat M (instHPow.{u1, 0} M Nat (Monoid.Pow.{u1} M _inst_1)) x n) (OfNat.ofNat.{u1} M 1 (One.toOfNat1.{u1} M (Monoid.toOne.{u1} M _inst_1)))) -> (Eq.{succ u1} M (HPow.hPow.{u1, 0, u1} M Nat M (instHPow.{u1, 0} M Nat (Monoid.Pow.{u1} M _inst_1)) x (Nat.gcd m n)) (OfNat.ofNat.{u1} M 1 (One.toOfNat1.{u1} M (Monoid.toOne.{u1} M _inst_1))))
-Case conversion may be inaccurate. Consider using '#align pow_gcd_eq_one pow_gcd_eq_oneₓ'. -/
theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m = 1) (hn : x ^ n = 1) :
x ^ m.gcd n = 1 := by
cases m; · simp only [hn, Nat.gcd_zero_left]
@@ -715,12 +601,6 @@ theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
-/- warning: gcd_nsmul_eq_zero -> gcd_nsmul_eq_zero is a dubious translation:
-lean 3 declaration is
- forall {M : Type.{u1}} [_inst_1 : AddMonoid.{u1} M] (x : M) {m : Nat} {n : Nat}, (Eq.{succ u1} M (SMul.smul.{0, u1} Nat M (AddMonoid.SMul.{u1} M _inst_1) m x) (OfNat.ofNat.{u1} M 0 (OfNat.mk.{u1} M 0 (Zero.zero.{u1} M (AddZeroClass.toHasZero.{u1} M (AddMonoid.toAddZeroClass.{u1} M _inst_1)))))) -> (Eq.{succ u1} M (SMul.smul.{0, u1} Nat M (AddMonoid.SMul.{u1} M _inst_1) n x) (OfNat.ofNat.{u1} M 0 (OfNat.mk.{u1} M 0 (Zero.zero.{u1} M (AddZeroClass.toHasZero.{u1} M (AddMonoid.toAddZeroClass.{u1} M _inst_1)))))) -> (Eq.{succ u1} M (SMul.smul.{0, u1} Nat M (AddMonoid.SMul.{u1} M _inst_1) (Nat.gcd m n) x) (OfNat.ofNat.{u1} M 0 (OfNat.mk.{u1} M 0 (Zero.zero.{u1} M (AddZeroClass.toHasZero.{u1} M (AddMonoid.toAddZeroClass.{u1} M _inst_1))))))
-but is expected to have type
- forall {M : Type.{u1}} [_inst_1 : AddMonoid.{u1} M] (x : M) {m : Nat} {n : Nat}, (Eq.{succ u1} M (HSMul.hSMul.{0, u1, u1} Nat M M (instHSMul.{0, u1} Nat M (AddMonoid.SMul.{u1} M _inst_1)) m x) (OfNat.ofNat.{u1} M 0 (Zero.toOfNat0.{u1} M (AddMonoid.toZero.{u1} M _inst_1)))) -> (Eq.{succ u1} M (HSMul.hSMul.{0, u1, u1} Nat M M (instHSMul.{0, u1} Nat M (AddMonoid.SMul.{u1} M _inst_1)) n x) (OfNat.ofNat.{u1} M 0 (Zero.toOfNat0.{u1} M (AddMonoid.toZero.{u1} M _inst_1)))) -> (Eq.{succ u1} M (HSMul.hSMul.{0, u1, u1} Nat M M (instHSMul.{0, u1} Nat M (AddMonoid.SMul.{u1} M _inst_1)) (Nat.gcd m n) x) (OfNat.ofNat.{u1} M 0 (Zero.toOfNat0.{u1} M (AddMonoid.toZero.{u1} M _inst_1))))
-Case conversion may be inaccurate. Consider using '#align gcd_nsmul_eq_zero gcd_nsmul_eq_zeroₓ'. -/
theorem gcd_nsmul_eq_zero {M : Type _} [AddMonoid M] (x : M) {m n : ℕ} (hm : m • x = 0)
(hn : n • x = 0) : m.gcd n • x = 0 :=
by
@@ -740,12 +620,6 @@ namespace Tactic
namespace NormNum
-/- warning: tactic.norm_num.int_gcd_helper' -> Tactic.NormNum.int_gcd_helper' is a dubious translation:
-lean 3 declaration is
- forall {d : Nat} {x : Int} {y : Int} {a : Int} {b : Int}, (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))) d) x) -> (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))) d) y) -> (Eq.{1} Int (HAdd.hAdd.{0, 0, 0} Int Int Int (instHAdd.{0} Int Int.hasAdd) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) x a) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) y 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))) d)) -> (Eq.{1} Nat (Int.gcd x y) d)
-but is expected to have type
- forall {d : Nat} {x : Int} {y : Int} (a : Int) (b : Int), (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt d) x) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt d) y) -> (Eq.{1} Int (HAdd.hAdd.{0, 0, 0} Int Int Int (instHAdd.{0} Int Int.instAddInt) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) x a) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) y b)) (Nat.cast.{0} Int instNatCastInt d)) -> (Eq.{1} Nat (Int.gcd x y) d)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.int_gcd_helper' Tactic.NormNum.int_gcd_helper'ₓ'. -/
theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂ : (d : ℤ) ∣ y)
(h₃ : x * a + y * b = d) : Int.gcd x y = d :=
by
@@ -756,32 +630,14 @@ theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂
· exact (Int.gcd_dvd_right _ _).mul_right _
#align tactic.norm_num.int_gcd_helper' Tactic.NormNum.int_gcd_helper'
-/- warning: tactic.norm_num.nat_gcd_helper_dvd_left -> Tactic.NormNum.nat_gcd_helper_dvd_left is a dubious translation:
-lean 3 declaration is
- forall (x : Nat) (y : Nat) (a : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x a) y) -> (Eq.{1} Nat (Nat.gcd x y) x)
-but is expected to have type
- forall (x : Nat) (y : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) y x) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (Nat.gcd x y) x)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_dvd_left Tactic.NormNum.nat_gcd_helper_dvd_leftₓ'. -/
theorem nat_gcd_helper_dvd_left (x y a : ℕ) (h : x * a = y) : Nat.gcd x y = x :=
Nat.gcd_eq_left ⟨a, h.symm⟩
#align tactic.norm_num.nat_gcd_helper_dvd_left Tactic.NormNum.nat_gcd_helper_dvd_left
-/- warning: tactic.norm_num.nat_gcd_helper_dvd_right -> Tactic.NormNum.nat_gcd_helper_dvd_right is a dubious translation:
-lean 3 declaration is
- forall (x : Nat) (y : Nat) (a : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) y a) x) -> (Eq.{1} Nat (Nat.gcd x y) y)
-but is expected to have type
- forall (x : Nat) (y : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) x y) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (Nat.gcd x y) y)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_dvd_right Tactic.NormNum.nat_gcd_helper_dvd_rightₓ'. -/
theorem nat_gcd_helper_dvd_right (x y a : ℕ) (h : y * a = x) : Nat.gcd x y = y :=
Nat.gcd_eq_right ⟨a, h.symm⟩
#align tactic.norm_num.nat_gcd_helper_dvd_right Tactic.NormNum.nat_gcd_helper_dvd_right
-/- warning: tactic.norm_num.nat_gcd_helper_2 -> Tactic.NormNum.nat_gcd_helper_2 is a dubious translation:
-lean 3 declaration is
- forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat) (u : Nat) (v : Nat) (tx : Nat) (ty : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d u) x) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d v) y) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x a) tx) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) y b) ty) -> (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) ty d) tx) -> (Eq.{1} Nat (Nat.gcd x y) d)
-but is expected to have type
- forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) x d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) y d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) x a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) y b) d)) -> (Eq.{1} Nat (Nat.gcd x y) d)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_2 Tactic.NormNum.nat_gcd_helper_2ₓ'. -/
theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
(hx : x * a = tx) (hy : y * b = ty) (h : ty + d = tx) : Nat.gcd x y = d :=
by
@@ -792,23 +648,11 @@ theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d *
norm_cast; rw [hx, hy, h]
#align tactic.norm_num.nat_gcd_helper_2 Tactic.NormNum.nat_gcd_helper_2
-/- warning: tactic.norm_num.nat_gcd_helper_1 -> Tactic.NormNum.nat_gcd_helper_1 is a dubious translation:
-lean 3 declaration is
- forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat) (u : Nat) (v : Nat) (tx : Nat) (ty : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d u) x) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d v) y) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x a) tx) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) y b) ty) -> (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) tx d) ty) -> (Eq.{1} Nat (Nat.gcd x y) d)
-but is expected to have type
- forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) x d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) y d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) y b) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) x a) d)) -> (Eq.{1} Nat (Nat.gcd x y) d)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_1 Tactic.NormNum.nat_gcd_helper_1ₓ'. -/
theorem nat_gcd_helper_1 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
(hx : x * a = tx) (hy : y * b = ty) (h : tx + d = ty) : Nat.gcd x y = d :=
(Nat.gcd_comm _ _).trans <| nat_gcd_helper_2 _ _ _ _ _ _ _ _ _ hv hu hy hx h
#align tactic.norm_num.nat_gcd_helper_1 Tactic.NormNum.nat_gcd_helper_1
-/- warning: tactic.norm_num.nat_lcm_helper -> Tactic.NormNum.nat_lcm_helper is a dubious translation:
-lean 3 declaration is
- forall (x : Nat) (y : Nat) (d : Nat) (m : Nat) (n : Nat), (Eq.{1} Nat (Nat.gcd x y) d) -> (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) d) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x y) n) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d m) n) -> (Eq.{1} Nat (Nat.lcm x y) m)
-but is expected to have type
- forall (x : Nat) (y : Nat) (d : Nat) (m : Nat), (Eq.{1} Nat (Nat.gcd x y) d) -> (Eq.{1} Bool (Nat.beq d (OfNat.ofNat.{0} ([mdata borrowed:1 Nat]) 0 (instOfNatNat 0))) Bool.false) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) x y) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) d m)) -> (Eq.{1} Nat (Nat.lcm x y) m)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_lcm_helper Tactic.NormNum.nat_lcm_helperₓ'. -/
theorem nat_lcm_helper (x y d m n : ℕ) (hd : Nat.gcd x y = d) (d0 : 0 < d) (xy : x * y = n)
(dm : d * m = n) : Nat.lcm x y = m :=
mul_right_injective₀ d0.ne' <| by rw [dm, ← xy, ← hd, Nat.gcd_mul_lcm]
@@ -837,12 +681,6 @@ theorem nat_not_coprime_helper (d x y u v : ℕ) (hu : d * u = x) (hv : d * v =
Nat.not_coprime_of_dvd_of_dvd h ⟨_, hu.symm⟩ ⟨_, hv.symm⟩
#align tactic.norm_num.nat_not_coprime_helper Tactic.NormNum.nat_not_coprime_helper
-/- warning: tactic.norm_num.int_gcd_helper -> Tactic.NormNum.int_gcd_helper is a dubious translation:
-lean 3 declaration is
- forall (x : Int) (y : Int) (nx : Nat) (ny : Nat) (d : Nat), (Eq.{1} Int ((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))) nx) x) -> (Eq.{1} Int ((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))) ny) y) -> (Eq.{1} Nat (Nat.gcd nx ny) d) -> (Eq.{1} Nat (Int.gcd x y) d)
-but is expected to have type
- forall {x : Int} {y : Int} {nx : Nat} {ny : Nat} {d : Nat}, (Eq.{1} Nat (Int.natAbs x) nx) -> (Eq.{1} Nat (Int.natAbs y) ny) -> (Eq.{1} Nat (Nat.gcd nx ny) d) -> (Eq.{1} Nat (Int.gcd x y) d)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.int_gcd_helper Tactic.NormNum.int_gcd_helperₓ'. -/
theorem int_gcd_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
(h : Nat.gcd nx ny = d) : Int.gcd x y = d := by rwa [← hx, ← hy, Int.coe_nat_gcd]
#align tactic.norm_num.int_gcd_helper Tactic.NormNum.int_gcd_helper
@@ -855,12 +693,6 @@ theorem int_gcd_helper_neg_right (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : I
rw [Int.gcd] at h⊢ <;> rwa [Int.natAbs_neg]
#align tactic.norm_num.int_gcd_helper_neg_right Tactic.NormNum.int_gcd_helper_neg_right
-/- warning: tactic.norm_num.int_lcm_helper -> Tactic.NormNum.int_lcm_helper is a dubious translation:
-lean 3 declaration is
- forall (x : Int) (y : Int) (nx : Nat) (ny : Nat) (d : Nat), (Eq.{1} Int ((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))) nx) x) -> (Eq.{1} Int ((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))) ny) y) -> (Eq.{1} Nat (Nat.lcm nx ny) d) -> (Eq.{1} Nat (Int.lcm x y) d)
-but is expected to have type
- forall {x : Int} {y : Int} {nx : Nat} {ny : Nat} {d : Nat}, (Eq.{1} Nat (Int.natAbs x) nx) -> (Eq.{1} Nat (Int.natAbs y) ny) -> (Eq.{1} Nat (Nat.lcm nx ny) d) -> (Eq.{1} Nat (Int.lcm x y) d)
-Case conversion may be inaccurate. Consider using '#align tactic.norm_num.int_lcm_helper Tactic.NormNum.int_lcm_helperₓ'. -/
theorem int_lcm_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
(h : Nat.lcm nx ny = d) : Int.lcm x y = d := by rwa [← hx, ← hy, Int.coe_nat_lcm]
#align tactic.norm_num.int_lcm_helper Tactic.NormNum.int_lcm_helper
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -58,10 +58,7 @@ theorem xgcd_zero_left {s t r' s' t'} : xgcdAux 0 s t r' s' t' = (r', s', t') :=
#print Nat.xgcd_aux_rec /-
theorem xgcd_aux_rec {r s t r' s' t'} (h : 0 < r) :
xgcdAux r s t r' s' t' = xgcdAux (r' % r) (s' - r' / r * s) (t' - r' / r * t) r s t := by
- cases r <;>
- [exact absurd h (lt_irrefl _);·
- simp only [xgcd_aux]
- rfl]
+ cases r <;> [exact absurd h (lt_irrefl _);· simp only [xgcd_aux]; rfl]
#align nat.xgcd_aux_rec Nat.xgcd_aux_rec
-/
@@ -89,19 +86,13 @@ def gcdB (x y : ℕ) : ℤ :=
#print Nat.gcdA_zero_left /-
@[simp]
-theorem gcdA_zero_left {s : ℕ} : gcdA 0 s = 0 :=
- by
- unfold gcd_a
- rw [xgcd, xgcd_zero_left]
+theorem gcdA_zero_left {s : ℕ} : gcdA 0 s = 0 := by unfold gcd_a; rw [xgcd, xgcd_zero_left]
#align nat.gcd_a_zero_left Nat.gcdA_zero_left
-/
#print Nat.gcdB_zero_left /-
@[simp]
-theorem gcdB_zero_left {s : ℕ} : gcdB 0 s = 1 :=
- by
- unfold gcd_b
- rw [xgcd, xgcd_zero_left]
+theorem gcdB_zero_left {s : ℕ} : gcdB 0 s = 1 := by unfold gcd_b; rw [xgcd, xgcd_zero_left]
#align nat.gcd_b_zero_left Nat.gcdB_zero_left
-/
@@ -237,9 +228,7 @@ theorem gcd_eq_gcd_ab : ∀ x y : ℤ, (gcd x y : ℤ) = x * gcdA x y + y * gcdB
| -[m+1], (n : ℕ) =>
show (_ : ℤ) = -(m + 1) * -_ + _ by rw [neg_mul_neg] <;> apply Nat.gcd_eq_gcd_ab
| -[m+1], -[n+1] =>
- show (_ : ℤ) = -(m + 1) * -_ + -(n + 1) * -_
- by
- rw [neg_mul_neg, neg_mul_neg]
+ show (_ : ℤ) = -(m + 1) * -_ + -(n + 1) * -_ by rw [neg_mul_neg, neg_mul_neg];
apply Nat.gcd_eq_gcd_ab
#align int.gcd_eq_gcd_ab Int.gcd_eq_gcd_ab
-/
@@ -253,8 +242,7 @@ Case conversion may be inaccurate. Consider using '#align int.nat_abs_div Int.na
theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natAbs b :=
by
cases Nat.eq_zero_or_pos (nat_abs b)
- · rw [eq_zero_of_nat_abs_eq_zero h]
- simp [Int.div_zero]
+ · rw [eq_zero_of_nat_abs_eq_zero h]; simp [Int.div_zero]
calc
nat_abs (a / b) = nat_abs (a / b) * 1 := by rw [mul_one]
_ = nat_abs (a / b) * (nat_abs b / nat_abs b) := by rw [Nat.div_self h]
@@ -396,18 +384,14 @@ theorem gcd_neg_left {x y : ℤ} : gcd (-x) y = gcd x y := by rw [Int.gcd, Int.g
-/
#print Int.gcd_mul_left /-
-theorem gcd_mul_left (i j k : ℤ) : gcd (i * j) (i * k) = natAbs i * gcd j k :=
- by
- rw [Int.gcd, Int.gcd, nat_abs_mul, nat_abs_mul]
- apply Nat.gcd_mul_left
+theorem gcd_mul_left (i j k : ℤ) : gcd (i * j) (i * k) = natAbs i * gcd j k := by
+ rw [Int.gcd, Int.gcd, nat_abs_mul, nat_abs_mul]; apply Nat.gcd_mul_left
#align int.gcd_mul_left Int.gcd_mul_left
-/
#print Int.gcd_mul_right /-
-theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * natAbs j :=
- by
- rw [Int.gcd, Int.gcd, nat_abs_mul, nat_abs_mul]
- apply Nat.gcd_mul_right
+theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * natAbs j := by
+ rw [Int.gcd, Int.gcd, nat_abs_mul, nat_abs_mul]; apply Nat.gcd_mul_right
#align int.gcd_mul_right Int.gcd_mul_right
-/
@@ -432,8 +416,7 @@ theorem gcd_eq_zero_iff {i j : ℤ} : gcd i j = 0 ↔ i = 0 ∧ j = 0 :=
exact
⟨nat_abs_eq_zero.mp (Nat.eq_zero_of_gcd_eq_zero_left h),
nat_abs_eq_zero.mp (Nat.eq_zero_of_gcd_eq_zero_right h)⟩
- · intro h
- rw [nat_abs_eq_zero.mpr h.left, nat_abs_eq_zero.mpr h.right]
+ · intro h; rw [nat_abs_eq_zero.mpr h.left, nat_abs_eq_zero.mpr h.right]
apply Nat.gcd_zero_left
#align int.gcd_eq_zero_iff Int.gcd_eq_zero_iff
-/
@@ -621,9 +604,7 @@ Case conversion may be inaccurate. Consider using '#align int.dvd_of_dvd_mul_rig
Compare with `is_coprime.dvd_of_dvd_mul_right` and
`unique_factorization_monoid.dvd_of_dvd_mul_right_of_no_prime_factors` -/
theorem dvd_of_dvd_mul_right_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a b = 1) :
- a ∣ c := by
- rw [mul_comm] at habc
- exact dvd_of_dvd_mul_left_of_gcd_one habc hab
+ a ∣ c := by rw [mul_comm] at habc; exact dvd_of_dvd_mul_left_of_gcd_one habc hab
#align int.dvd_of_dvd_mul_right_of_gcd_one Int.dvd_of_dvd_mul_right_of_gcd_one
#print Int.gcd_least_linear /-
@@ -644,63 +625,43 @@ theorem gcd_least_linear {a b : ℤ} (ha : a ≠ 0) :
#print Int.lcm_comm /-
-theorem lcm_comm (i j : ℤ) : lcm i j = lcm j i :=
- by
- rw [Int.lcm, Int.lcm]
- exact Nat.lcm_comm _ _
+theorem lcm_comm (i j : ℤ) : lcm i j = lcm j i := by rw [Int.lcm, Int.lcm]; exact Nat.lcm_comm _ _
#align int.lcm_comm Int.lcm_comm
-/
#print Int.lcm_assoc /-
-theorem lcm_assoc (i j k : ℤ) : lcm (lcm i j) k = lcm i (lcm j k) :=
- by
- rw [Int.lcm, Int.lcm, Int.lcm, Int.lcm, nat_abs_of_nat, nat_abs_of_nat]
- apply Nat.lcm_assoc
+theorem lcm_assoc (i j k : ℤ) : lcm (lcm i j) k = lcm i (lcm j k) := by
+ rw [Int.lcm, Int.lcm, Int.lcm, Int.lcm, nat_abs_of_nat, nat_abs_of_nat]; apply Nat.lcm_assoc
#align int.lcm_assoc Int.lcm_assoc
-/
#print Int.lcm_zero_left /-
@[simp]
-theorem lcm_zero_left (i : ℤ) : lcm 0 i = 0 :=
- by
- rw [Int.lcm]
- apply Nat.lcm_zero_left
+theorem lcm_zero_left (i : ℤ) : lcm 0 i = 0 := by rw [Int.lcm]; apply Nat.lcm_zero_left
#align int.lcm_zero_left Int.lcm_zero_left
-/
#print Int.lcm_zero_right /-
@[simp]
-theorem lcm_zero_right (i : ℤ) : lcm i 0 = 0 :=
- by
- rw [Int.lcm]
- apply Nat.lcm_zero_right
+theorem lcm_zero_right (i : ℤ) : lcm i 0 = 0 := by rw [Int.lcm]; apply Nat.lcm_zero_right
#align int.lcm_zero_right Int.lcm_zero_right
-/
#print Int.lcm_one_left /-
@[simp]
-theorem lcm_one_left (i : ℤ) : lcm 1 i = natAbs i :=
- by
- rw [Int.lcm]
- apply Nat.lcm_one_left
+theorem lcm_one_left (i : ℤ) : lcm 1 i = natAbs i := by rw [Int.lcm]; apply Nat.lcm_one_left
#align int.lcm_one_left Int.lcm_one_left
-/
#print Int.lcm_one_right /-
@[simp]
-theorem lcm_one_right (i : ℤ) : lcm i 1 = natAbs i :=
- by
- rw [Int.lcm]
- apply Nat.lcm_one_right
+theorem lcm_one_right (i : ℤ) : lcm i 1 = natAbs i := by rw [Int.lcm]; apply Nat.lcm_one_right
#align int.lcm_one_right Int.lcm_one_right
-/
#print Int.lcm_self /-
@[simp]
-theorem lcm_self (i : ℤ) : lcm i i = natAbs i :=
- by
- rw [Int.lcm]
- apply Nat.lcm_self
+theorem lcm_self (i : ℤ) : lcm i i = natAbs i := by rw [Int.lcm]; apply Nat.lcm_self
#align int.lcm_self Int.lcm_self
-/
@@ -710,10 +671,7 @@ lean 3 declaration is
but is expected to have type
forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt i (Nat.cast.{0} Int instNatCastInt (Int.lcm i j))
Case conversion may be inaccurate. Consider using '#align int.dvd_lcm_left Int.dvd_lcm_leftₓ'. -/
-theorem dvd_lcm_left (i j : ℤ) : i ∣ lcm i j :=
- by
- rw [Int.lcm]
- apply coe_nat_dvd_right.mpr
+theorem dvd_lcm_left (i j : ℤ) : i ∣ lcm i j := by rw [Int.lcm]; apply coe_nat_dvd_right.mpr;
apply Nat.dvd_lcm_left
#align int.dvd_lcm_left Int.dvd_lcm_left
@@ -723,10 +681,7 @@ lean 3 declaration is
but is expected to have type
forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt j (Nat.cast.{0} Int instNatCastInt (Int.lcm i j))
Case conversion may be inaccurate. Consider using '#align int.dvd_lcm_right Int.dvd_lcm_rightₓ'. -/
-theorem dvd_lcm_right (i j : ℤ) : j ∣ lcm i j :=
- by
- rw [Int.lcm]
- apply coe_nat_dvd_right.mpr
+theorem dvd_lcm_right (i j : ℤ) : j ∣ lcm i j := by rw [Int.lcm]; apply coe_nat_dvd_right.mpr;
apply Nat.dvd_lcm_right
#align int.dvd_lcm_right Int.dvd_lcm_right
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -153,7 +153,6 @@ parameter (x y : ℕ)
private def P : ℕ × ℤ × ℤ → Prop
| (r, s, t) => (r : ℤ) = x * s + y * t
-#align nat.P nat.P
#print Nat.xgcd_aux_P /-
theorem xgcd_aux_P {r r'} :
mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b
@@ -58,8 +58,9 @@ theorem xgcd_zero_left {s t r' s' t'} : xgcdAux 0 s t r' s' t' = (r', s', t') :=
#print Nat.xgcd_aux_rec /-
theorem xgcd_aux_rec {r s t r' s' t'} (h : 0 < r) :
xgcdAux r s t r' s' t' = xgcdAux (r' % r) (s' - r' / r * s) (t' - r' / r * t) r s t := by
- cases r <;> [exact absurd h (lt_irrefl _),
- · simp only [xgcd_aux]
+ cases r <;>
+ [exact absurd h (lt_irrefl _);·
+ simp only [xgcd_aux]
rfl]
#align nat.xgcd_aux_rec Nat.xgcd_aux_rec
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8
@@ -785,6 +785,12 @@ namespace Tactic
namespace NormNum
+/- warning: tactic.norm_num.int_gcd_helper' -> Tactic.NormNum.int_gcd_helper' is a dubious translation:
+lean 3 declaration is
+ forall {d : Nat} {x : Int} {y : Int} {a : Int} {b : Int}, (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))) d) x) -> (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))) d) y) -> (Eq.{1} Int (HAdd.hAdd.{0, 0, 0} Int Int Int (instHAdd.{0} Int Int.hasAdd) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) x a) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.hasMul) y 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))) d)) -> (Eq.{1} Nat (Int.gcd x y) d)
+but is expected to have type
+ forall {d : Nat} {x : Int} {y : Int} (a : Int) (b : Int), (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt d) x) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt d) y) -> (Eq.{1} Int (HAdd.hAdd.{0, 0, 0} Int Int Int (instHAdd.{0} Int Int.instAddInt) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) x a) (HMul.hMul.{0, 0, 0} Int Int Int (instHMul.{0} Int Int.instMulInt) y b)) (Nat.cast.{0} Int instNatCastInt d)) -> (Eq.{1} Nat (Int.gcd x y) d)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.int_gcd_helper' Tactic.NormNum.int_gcd_helper'ₓ'. -/
theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂ : (d : ℤ) ∣ y)
(h₃ : x * a + y * b = d) : Int.gcd x y = d :=
by
@@ -795,14 +801,32 @@ theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂
· exact (Int.gcd_dvd_right _ _).mul_right _
#align tactic.norm_num.int_gcd_helper' Tactic.NormNum.int_gcd_helper'
+/- warning: tactic.norm_num.nat_gcd_helper_dvd_left -> Tactic.NormNum.nat_gcd_helper_dvd_left is a dubious translation:
+lean 3 declaration is
+ forall (x : Nat) (y : Nat) (a : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x a) y) -> (Eq.{1} Nat (Nat.gcd x y) x)
+but is expected to have type
+ forall (x : Nat) (y : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) y x) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (Nat.gcd x y) x)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_dvd_left Tactic.NormNum.nat_gcd_helper_dvd_leftₓ'. -/
theorem nat_gcd_helper_dvd_left (x y a : ℕ) (h : x * a = y) : Nat.gcd x y = x :=
Nat.gcd_eq_left ⟨a, h.symm⟩
#align tactic.norm_num.nat_gcd_helper_dvd_left Tactic.NormNum.nat_gcd_helper_dvd_left
+/- warning: tactic.norm_num.nat_gcd_helper_dvd_right -> Tactic.NormNum.nat_gcd_helper_dvd_right is a dubious translation:
+lean 3 declaration is
+ forall (x : Nat) (y : Nat) (a : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) y a) x) -> (Eq.{1} Nat (Nat.gcd x y) y)
+but is expected to have type
+ forall (x : Nat) (y : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) x y) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (Nat.gcd x y) y)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_dvd_right Tactic.NormNum.nat_gcd_helper_dvd_rightₓ'. -/
theorem nat_gcd_helper_dvd_right (x y a : ℕ) (h : y * a = x) : Nat.gcd x y = y :=
Nat.gcd_eq_right ⟨a, h.symm⟩
#align tactic.norm_num.nat_gcd_helper_dvd_right Tactic.NormNum.nat_gcd_helper_dvd_right
+/- warning: tactic.norm_num.nat_gcd_helper_2 -> Tactic.NormNum.nat_gcd_helper_2 is a dubious translation:
+lean 3 declaration is
+ forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat) (u : Nat) (v : Nat) (tx : Nat) (ty : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d u) x) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d v) y) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x a) tx) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) y b) ty) -> (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) ty d) tx) -> (Eq.{1} Nat (Nat.gcd x y) d)
+but is expected to have type
+ forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) x d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) y d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) x a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) y b) d)) -> (Eq.{1} Nat (Nat.gcd x y) d)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_2 Tactic.NormNum.nat_gcd_helper_2ₓ'. -/
theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
(hx : x * a = tx) (hy : y * b = ty) (h : ty + d = tx) : Nat.gcd x y = d :=
by
@@ -813,11 +837,23 @@ theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d *
norm_cast; rw [hx, hy, h]
#align tactic.norm_num.nat_gcd_helper_2 Tactic.NormNum.nat_gcd_helper_2
+/- warning: tactic.norm_num.nat_gcd_helper_1 -> Tactic.NormNum.nat_gcd_helper_1 is a dubious translation:
+lean 3 declaration is
+ forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat) (u : Nat) (v : Nat) (tx : Nat) (ty : Nat), (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d u) x) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d v) y) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x a) tx) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) y b) ty) -> (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) tx d) ty) -> (Eq.{1} Nat (Nat.gcd x y) d)
+but is expected to have type
+ forall (d : Nat) (x : Nat) (y : Nat) (a : Nat) (b : Nat), (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) x d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMod.hMod.{0, 0, 0} Nat Nat Nat (instHMod.{0} Nat Nat.instModNat) y d) (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) y b) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) x a) d)) -> (Eq.{1} Nat (Nat.gcd x y) d)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_gcd_helper_1 Tactic.NormNum.nat_gcd_helper_1ₓ'. -/
theorem nat_gcd_helper_1 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
(hx : x * a = tx) (hy : y * b = ty) (h : tx + d = ty) : Nat.gcd x y = d :=
(Nat.gcd_comm _ _).trans <| nat_gcd_helper_2 _ _ _ _ _ _ _ _ _ hv hu hy hx h
#align tactic.norm_num.nat_gcd_helper_1 Tactic.NormNum.nat_gcd_helper_1
+/- warning: tactic.norm_num.nat_lcm_helper -> Tactic.NormNum.nat_lcm_helper is a dubious translation:
+lean 3 declaration is
+ forall (x : Nat) (y : Nat) (d : Nat) (m : Nat) (n : Nat), (Eq.{1} Nat (Nat.gcd x y) d) -> (LT.lt.{0} Nat Nat.hasLt (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero))) d) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) x y) n) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) d m) n) -> (Eq.{1} Nat (Nat.lcm x y) m)
+but is expected to have type
+ forall (x : Nat) (y : Nat) (d : Nat) (m : Nat), (Eq.{1} Nat (Nat.gcd x y) d) -> (Eq.{1} Bool (Nat.beq d (OfNat.ofNat.{0} ([mdata borrowed:1 Nat]) 0 (instOfNatNat 0))) Bool.false) -> (Eq.{1} Nat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) x y) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) d m)) -> (Eq.{1} Nat (Nat.lcm x y) m)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.nat_lcm_helper Tactic.NormNum.nat_lcm_helperₓ'. -/
theorem nat_lcm_helper (x y d m n : ℕ) (hd : Nat.gcd x y = d) (d0 : 0 < d) (xy : x * y = n)
(dm : d * m = n) : Nat.lcm x y = m :=
mul_right_injective₀ d0.ne' <| by rw [dm, ← xy, ← hd, Nat.gcd_mul_lcm]
@@ -846,6 +882,12 @@ theorem nat_not_coprime_helper (d x y u v : ℕ) (hu : d * u = x) (hv : d * v =
Nat.not_coprime_of_dvd_of_dvd h ⟨_, hu.symm⟩ ⟨_, hv.symm⟩
#align tactic.norm_num.nat_not_coprime_helper Tactic.NormNum.nat_not_coprime_helper
+/- warning: tactic.norm_num.int_gcd_helper -> Tactic.NormNum.int_gcd_helper is a dubious translation:
+lean 3 declaration is
+ forall (x : Int) (y : Int) (nx : Nat) (ny : Nat) (d : Nat), (Eq.{1} Int ((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))) nx) x) -> (Eq.{1} Int ((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))) ny) y) -> (Eq.{1} Nat (Nat.gcd nx ny) d) -> (Eq.{1} Nat (Int.gcd x y) d)
+but is expected to have type
+ forall {x : Int} {y : Int} {nx : Nat} {ny : Nat} {d : Nat}, (Eq.{1} Nat (Int.natAbs x) nx) -> (Eq.{1} Nat (Int.natAbs y) ny) -> (Eq.{1} Nat (Nat.gcd nx ny) d) -> (Eq.{1} Nat (Int.gcd x y) d)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.int_gcd_helper Tactic.NormNum.int_gcd_helperₓ'. -/
theorem int_gcd_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
(h : Nat.gcd nx ny = d) : Int.gcd x y = d := by rwa [← hx, ← hy, Int.coe_nat_gcd]
#align tactic.norm_num.int_gcd_helper Tactic.NormNum.int_gcd_helper
@@ -858,6 +900,12 @@ theorem int_gcd_helper_neg_right (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : I
rw [Int.gcd] at h⊢ <;> rwa [Int.natAbs_neg]
#align tactic.norm_num.int_gcd_helper_neg_right Tactic.NormNum.int_gcd_helper_neg_right
+/- warning: tactic.norm_num.int_lcm_helper -> Tactic.NormNum.int_lcm_helper is a dubious translation:
+lean 3 declaration is
+ forall (x : Int) (y : Int) (nx : Nat) (ny : Nat) (d : Nat), (Eq.{1} Int ((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))) nx) x) -> (Eq.{1} Int ((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))) ny) y) -> (Eq.{1} Nat (Nat.lcm nx ny) d) -> (Eq.{1} Nat (Int.lcm x y) d)
+but is expected to have type
+ forall {x : Int} {y : Int} {nx : Nat} {ny : Nat} {d : Nat}, (Eq.{1} Nat (Int.natAbs x) nx) -> (Eq.{1} Nat (Int.natAbs y) ny) -> (Eq.{1} Nat (Nat.lcm nx ny) d) -> (Eq.{1} Nat (Int.lcm x y) d)
+Case conversion may be inaccurate. Consider using '#align tactic.norm_num.int_lcm_helper Tactic.NormNum.int_lcm_helperₓ'. -/
theorem int_lcm_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
(h : Nat.lcm nx ny = d) : Int.lcm x y = d := by rwa [← hx, ← hy, Int.coe_nat_lcm]
#align tactic.norm_num.int_lcm_helper Tactic.NormNum.int_lcm_helper
mathlib commit https://github.com/leanprover-community/mathlib/commit/06a655b5fcfbda03502f9158bbf6c0f1400886f9
@@ -411,13 +411,17 @@ theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * natAbs j :
#align int.gcd_mul_right Int.gcd_mul_right
-/
+#print Int.gcd_pos_of_ne_zero_left /-
theorem gcd_pos_of_ne_zero_left {i : ℤ} (j : ℤ) (hi : i ≠ 0) : 0 < gcd i j :=
Nat.gcd_pos_of_pos_left _ <| natAbs_pos_of_ne_zero hi
#align int.gcd_pos_of_ne_zero_left Int.gcd_pos_of_ne_zero_left
+-/
+#print Int.gcd_pos_of_ne_zero_right /-
theorem gcd_pos_of_ne_zero_right (i : ℤ) {j : ℤ} (hj : j ≠ 0) : 0 < gcd i j :=
Nat.gcd_pos_of_pos_right _ <| natAbs_pos_of_ne_zero hj
#align int.gcd_pos_of_ne_zero_right Int.gcd_pos_of_ne_zero_right
+-/
#print Int.gcd_eq_zero_iff /-
theorem gcd_eq_zero_iff {i j : ℤ} : gcd i j = 0 ↔ i = 0 ∧ j = 0 :=
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: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
! This file was ported from Lean 3 source module data.int.gcd
-! leanprover-community/mathlib commit c3291da49cfa65f0d43b094750541c0731edc932
+! leanprover-community/mathlib commit 47a1a73351de8dd6c8d3d32b569c8e434b03ca47
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -411,17 +411,13 @@ theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * natAbs j :
#align int.gcd_mul_right Int.gcd_mul_right
-/
-#print Int.gcd_pos_of_non_zero_left /-
-theorem gcd_pos_of_non_zero_left {i : ℤ} (j : ℤ) (i_non_zero : i ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_left (natAbs j) (natAbs_pos_of_ne_zero i_non_zero)
-#align int.gcd_pos_of_non_zero_left Int.gcd_pos_of_non_zero_left
--/
+theorem gcd_pos_of_ne_zero_left {i : ℤ} (j : ℤ) (hi : i ≠ 0) : 0 < gcd i j :=
+ Nat.gcd_pos_of_pos_left _ <| natAbs_pos_of_ne_zero hi
+#align int.gcd_pos_of_ne_zero_left Int.gcd_pos_of_ne_zero_left
-#print Int.gcd_pos_of_non_zero_right /-
-theorem gcd_pos_of_non_zero_right (i : ℤ) {j : ℤ} (j_non_zero : j ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_right (natAbs i) (natAbs_pos_of_ne_zero j_non_zero)
-#align int.gcd_pos_of_non_zero_right Int.gcd_pos_of_non_zero_right
--/
+theorem gcd_pos_of_ne_zero_right (i : ℤ) {j : ℤ} (hj : j ≠ 0) : 0 < gcd i j :=
+ Nat.gcd_pos_of_pos_right _ <| natAbs_pos_of_ne_zero hj
+#align int.gcd_pos_of_ne_zero_right Int.gcd_pos_of_ne_zero_right
#print Int.gcd_eq_zero_iff /-
theorem gcd_eq_zero_iff {i j : ℤ} : gcd i j = 0 ↔ i = 0 ∧ j = 0 :=
@@ -634,7 +630,7 @@ theorem gcd_least_linear {a b : ℤ} (ha : a ≠ 0) :
by
simp_rw [← gcd_dvd_iff]
constructor
- · simpa [and_true_iff, dvd_refl, Set.mem_setOf_eq] using gcd_pos_of_non_zero_left b ha
+ · simpa [and_true_iff, dvd_refl, Set.mem_setOf_eq] using gcd_pos_of_ne_zero_left b ha
· simp only [lowerBounds, and_imp, Set.mem_setOf_eq]
exact fun n hn_pos hn => Nat.le_of_dvd hn_pos hn
#align int.gcd_least_linear Int.gcd_least_linear
mathlib commit https://github.com/leanprover-community/mathlib/commit/da3fc4a33ff6bc75f077f691dc94c217b8d41559
@@ -307,7 +307,7 @@ protected theorem coe_nat_lcm (m n : ℕ) : Int.lcm ↑m ↑n = Nat.lcm m n :=
lean 3 declaration is
forall (i : Int) (j : Int), 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))) (Int.gcd i j)) i
but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt (Int.gcd i j)) i
+ forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt (Int.gcd i j)) i
Case conversion may be inaccurate. Consider using '#align int.gcd_dvd_left Int.gcd_dvd_leftₓ'. -/
theorem gcd_dvd_left (i j : ℤ) : (gcd i j : ℤ) ∣ i :=
dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_left _ _
@@ -317,7 +317,7 @@ theorem gcd_dvd_left (i j : ℤ) : (gcd i j : ℤ) ∣ i :=
lean 3 declaration is
forall (i : Int) (j : Int), 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))) (Int.gcd i j)) j
but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt (Int.gcd i j)) j
+ forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt (Int.gcd i j)) j
Case conversion may be inaccurate. Consider using '#align int.gcd_dvd_right Int.gcd_dvd_rightₓ'. -/
theorem gcd_dvd_right (i j : ℤ) : (gcd i j : ℤ) ∣ j :=
dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_right _ _
@@ -327,7 +327,7 @@ theorem gcd_dvd_right (i j : ℤ) : (gcd i j : ℤ) ∣ j :=
lean 3 declaration is
forall {i : Int} {j : Int} {k : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k i) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k j) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) k ((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))) (Int.gcd i j)))
but is expected to have type
- forall {i : Int} {j : Int} {k : Int}, (Dvd.dvd.{0} Int Int.instDvdInt k i) -> (Dvd.dvd.{0} Int Int.instDvdInt k j) -> (Dvd.dvd.{0} Int Int.instDvdInt k (Nat.cast.{0} Int Int.instNatCastInt (Int.gcd i j)))
+ forall {i : Int} {j : Int} {k : Int}, (Dvd.dvd.{0} Int Int.instDvdInt k i) -> (Dvd.dvd.{0} Int Int.instDvdInt k j) -> (Dvd.dvd.{0} Int Int.instDvdInt k (Nat.cast.{0} Int instNatCastInt (Int.gcd i j)))
Case conversion may be inaccurate. Consider using '#align int.dvd_gcd Int.dvd_gcdₓ'. -/
theorem dvd_gcd {i j k : ℤ} (h1 : k ∣ i) (h2 : k ∣ j) : k ∣ gcd i j :=
natAbs_dvd.1 <| coe_nat_dvd.2 <| Nat.dvd_gcd (natAbs_dvd_natAbs.2 h1) (natAbs_dvd_natAbs.2 h2)
@@ -585,7 +585,7 @@ theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑
lean 3 declaration is
forall {a : Int} {b : Int} {d : Int}, (LE.le.{0} Int Int.hasLe (OfNat.ofNat.{0} Int 0 (OfNat.mk.{0} Int 0 (Zero.zero.{0} Int Int.hasZero))) d) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) d a) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) d b) -> (forall (e : Int), (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) e a) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) e b) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) e d)) -> (Eq.{1} Int d ((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))) (Int.gcd a b)))
but is expected to have type
- forall {a : Int} {b : Int} {d : Int}, (LE.le.{0} Int Int.instLEInt (OfNat.ofNat.{0} Int 0 (instOfNatInt 0)) d) -> (Dvd.dvd.{0} Int Int.instDvdInt d a) -> (Dvd.dvd.{0} Int Int.instDvdInt d b) -> (forall (e : Int), (Dvd.dvd.{0} Int Int.instDvdInt e a) -> (Dvd.dvd.{0} Int Int.instDvdInt e b) -> (Dvd.dvd.{0} Int Int.instDvdInt e d)) -> (Eq.{1} Int d (Nat.cast.{0} Int Int.instNatCastInt (Int.gcd a b)))
+ forall {a : Int} {b : Int} {d : Int}, (LE.le.{0} Int Int.instLEInt (OfNat.ofNat.{0} Int 0 (instOfNatInt 0)) d) -> (Dvd.dvd.{0} Int Int.instDvdInt d a) -> (Dvd.dvd.{0} Int Int.instDvdInt d b) -> (forall (e : Int), (Dvd.dvd.{0} Int Int.instDvdInt e a) -> (Dvd.dvd.{0} Int Int.instDvdInt e b) -> (Dvd.dvd.{0} Int Int.instDvdInt e d)) -> (Eq.{1} Int d (Nat.cast.{0} Int instNatCastInt (Int.gcd a b)))
Case conversion may be inaccurate. Consider using '#align int.gcd_greatest Int.gcd_greatestₓ'. -/
theorem gcd_greatest {a b d : ℤ} (hd_pos : 0 ≤ d) (hda : d ∣ a) (hdb : d ∣ b)
(hd : ∀ e : ℤ, e ∣ a → e ∣ b → e ∣ d) : d = gcd a b :=
@@ -708,7 +708,7 @@ theorem lcm_self (i : ℤ) : lcm i i = natAbs i :=
lean 3 declaration is
forall (i : Int) (j : Int), Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i ((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))) (Int.lcm i j))
but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt i (Nat.cast.{0} Int Int.instNatCastInt (Int.lcm i j))
+ forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt i (Nat.cast.{0} Int instNatCastInt (Int.lcm i j))
Case conversion may be inaccurate. Consider using '#align int.dvd_lcm_left Int.dvd_lcm_leftₓ'. -/
theorem dvd_lcm_left (i j : ℤ) : i ∣ lcm i j :=
by
@@ -721,7 +721,7 @@ theorem dvd_lcm_left (i j : ℤ) : i ∣ lcm i j :=
lean 3 declaration is
forall (i : Int) (j : Int), Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) j ((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))) (Int.lcm i j))
but is expected to have type
- forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt j (Nat.cast.{0} Int Int.instNatCastInt (Int.lcm i j))
+ forall (i : Int) (j : Int), Dvd.dvd.{0} Int Int.instDvdInt j (Nat.cast.{0} Int instNatCastInt (Int.lcm i j))
Case conversion may be inaccurate. Consider using '#align int.dvd_lcm_right Int.dvd_lcm_rightₓ'. -/
theorem dvd_lcm_right (i j : ℤ) : j ∣ lcm i j :=
by
@@ -734,7 +734,7 @@ theorem dvd_lcm_right (i j : ℤ) : j ∣ lcm i j :=
lean 3 declaration is
forall {i : Int} {j : Int} {k : Int}, (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) i k) -> (Dvd.Dvd.{0} Int (semigroupDvd.{0} Int Int.semigroup) j k) -> (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))) (Int.lcm i j)) k)
but is expected to have type
- forall {i : Int} {j : Int} {k : Int}, (Dvd.dvd.{0} Int Int.instDvdInt i k) -> (Dvd.dvd.{0} Int Int.instDvdInt j k) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int Int.instNatCastInt (Int.lcm i j)) k)
+ forall {i : Int} {j : Int} {k : Int}, (Dvd.dvd.{0} Int Int.instDvdInt i k) -> (Dvd.dvd.{0} Int Int.instDvdInt j k) -> (Dvd.dvd.{0} Int Int.instDvdInt (Nat.cast.{0} Int instNatCastInt (Int.lcm i j)) k)
Case conversion may be inaccurate. Consider using '#align int.lcm_dvd Int.lcm_dvdₓ'. -/
theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
These don't use any abstract algebra.
@@ -340,6 +340,17 @@ theorem gcd_dvd_gcd_mul_right_right (i j k : ℤ) : gcd i j ∣ gcd i (j * k) :=
gcd_dvd_gcd_of_dvd_right _ (dvd_mul_right _ _)
#align int.gcd_dvd_gcd_mul_right_right Int.gcd_dvd_gcd_mul_right_right
+/-- If `gcd a (m * n) = 1`, then `gcd a m = 1`. -/
+theorem gcd_eq_one_of_gcd_mul_right_eq_one_left {a : ℤ} {m n : ℕ} (h : a.gcd (m * n) = 1) :
+ a.gcd m = 1 :=
+ Nat.dvd_one.mp <| h ▸ gcd_dvd_gcd_mul_right_right a m n
+#align int.gcd_eq_one_of_gcd_mul_right_eq_one_left Int.gcd_eq_one_of_gcd_mul_right_eq_one_left
+
+/-- If `gcd a (m * n) = 1`, then `gcd a n = 1`. -/
+theorem gcd_eq_one_of_gcd_mul_right_eq_one_right {a : ℤ} {m n : ℕ} (h : a.gcd (m * n) = 1) :
+ a.gcd n = 1 :=
+ Nat.dvd_one.mp <| h ▸ gcd_dvd_gcd_mul_left_right a n m
+
theorem gcd_eq_left {i j : ℤ} (H : i ∣ j) : gcd i j = natAbs i :=
Nat.dvd_antisymm (Nat.gcd_dvd_left _ _) (Nat.dvd_gcd dvd_rfl (natAbs_dvd_natAbs.mpr H))
#align int.gcd_eq_left Int.gcd_eq_left
We add fermatLastTheoremThree_of_three_dvd_only_c
: To prove FermatLastTheoremFor 3
, we may assume that ¬ 3 ∣ a
, ¬ 3 ∣ b
, a
and b
are coprime and 3 ∣ c
.
From the flt3 project in LFTCM2024.
Co-authored-by: Pietro Monticone <38562595+pitmonticone@users.noreply.github.com>
@@ -364,7 +364,7 @@ theorem exists_gcd_one' {m n : ℤ} (H : 0 < gcd m n) :
⟨_, m', n', H, h⟩
#align int.exists_gcd_one' Int.exists_gcd_one'
-theorem pow_dvd_pow_iff {m n : ℤ} {k : ℕ} (k0 : 0 < k) : m ^ k ∣ n ^ k ↔ m ∣ n := by
+theorem pow_dvd_pow_iff {m n : ℤ} {k : ℕ} (k0 : k ≠ 0) : m ^ k ∣ n ^ k ↔ m ∣ n := by
refine' ⟨fun h => _, fun h => pow_dvd_pow_of_dvd h _⟩
rwa [← natAbs_dvd_natAbs, ← Nat.pow_dvd_pow_iff k0, ← Int.natAbs_pow, ← Int.natAbs_pow,
natAbs_dvd_natAbs]
@@ -30,9 +30,6 @@ import Mathlib.Order.Bounds.Basic
Bézout's lemma, Bezout's lemma
-/
-set_option autoImplicit true
-
-
/-! ### Extended Euclidean algorithm -/
@@ -49,9 +46,9 @@ def xgcdAux : ℕ → ℤ → ℤ → ℕ → ℤ → ℤ → ℕ × ℤ × ℤ
-- Porting note: these are not in mathlib3; these equation lemmas are to fix
-- complaints by the Lean 4 `unusedHavesSuffices` linter obtained when `simp [xgcdAux]` is used.
-theorem xgcdAux_zero : xgcdAux 0 s t r' s' t' = (r', s', t') := rfl
+theorem xgcdAux_zero {s t : ℤ} {r' : ℕ} {s' t' : ℤ} : xgcdAux 0 s t r' s' t' = (r', s', t') := rfl
-theorem xgcdAux_succ : xgcdAux (succ k) s t r' s' t' =
+theorem xgcdAux_succ {k : ℕ} {s t : ℤ} {r' : ℕ} {s' t' : ℤ} : xgcdAux (succ k) s t r' s' t' =
xgcdAux (r' % succ k) (s' - (r' / succ k) * s) (t' - (r' / succ k) * t) (succ k) s t := rfl
@[simp]
@@ -224,10 +224,14 @@ theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natA
_ = natAbs a / natAbs b := by rw [Int.ediv_mul_cancel H]
#align int.nat_abs_div Int.natAbs_ediv
+/-- special case of `mul_dvd_mul_iff_right` for `ℤ`.
+Duplicated here to keep simple imports for this file. -/
theorem dvd_of_mul_dvd_mul_left {i j k : ℤ} (k_non_zero : k ≠ 0) (H : k * i ∣ k * j) : i ∣ j :=
Dvd.elim H fun l H1 => by rw [mul_assoc] at H1; exact ⟨_, mul_left_cancel₀ k_non_zero H1⟩
#align int.dvd_of_mul_dvd_mul_left Int.dvd_of_mul_dvd_mul_left
+/-- special case of `mul_dvd_mul_iff_right` for `ℤ`.
+Duplicated here to keep simple imports for this file. -/
theorem dvd_of_mul_dvd_mul_right {i j k : ℤ} (k_non_zero : k ≠ 0) (H : i * k ∣ j * k) : i ∣ j := by
rw [mul_comm i k, mul_comm j k] at H; exact dvd_of_mul_dvd_mul_left k_non_zero H
#align int.dvd_of_mul_dvd_mul_right Int.dvd_of_mul_dvd_mul_right
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
@@ -161,9 +161,9 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
have hk' := Int.ofNat_ne_zero.2 (ne_of_gt (lt_of_le_of_lt (zero_le (gcd n k)) hk))
have key := congr_arg (fun (m : ℤ) => (m % k).toNat) (gcd_eq_gcd_ab n k)
simp only at key
- rw [Int.add_mul_emod_self_left, ← Int.coe_nat_mod, Int.toNat_coe_nat, mod_eq_of_lt hk] at key
+ rw [Int.add_mul_emod_self_left, ← Int.natCast_mod, Int.toNat_natCast, mod_eq_of_lt hk] at key
refine' ⟨(n.gcdA k % k).toNat, Eq.trans (Int.ofNat.inj _) key.symm⟩
- rw [Int.ofNat_eq_coe, Int.coe_nat_mod, Int.ofNat_mul, Int.toNat_of_nonneg (Int.emod_nonneg _ hk'),
+ rw [Int.ofNat_eq_coe, Int.natCast_mod, Int.ofNat_mul, Int.toNat_of_nonneg (Int.emod_nonneg _ hk'),
Int.ofNat_eq_coe, Int.toNat_of_nonneg (Int.emod_nonneg _ hk'), Int.mul_emod, Int.emod_emod,
← Int.mul_emod]
#align nat.exists_mul_mod_eq_gcd Nat.exists_mul_emod_eq_gcd
@@ -247,7 +247,7 @@ protected theorem coe_nat_lcm (m n : ℕ) : Int.lcm ↑m ↑n = Nat.lcm m n :=
theorem dvd_gcd {i j k : ℤ} (h1 : k ∣ i) (h2 : k ∣ j) : k ∣ gcd i j :=
natAbs_dvd.1 <|
- coe_nat_dvd.2 <| Nat.dvd_gcd (natAbs_dvd_natAbs.2 h1) (natAbs_dvd_natAbs.2 h2)
+ natCast_dvd_natCast.2 <| Nat.dvd_gcd (natAbs_dvd_natAbs.2 h1) (natAbs_dvd_natAbs.2 h2)
#align int.dvd_gcd Int.dvd_gcd
theorem gcd_mul_lcm (i j : ℤ) : gcd i j * lcm i j = natAbs (i * j) := by
@@ -316,11 +316,11 @@ theorem gcd_div_gcd_div_gcd {i j : ℤ} (H : 0 < gcd i j) : gcd (i / gcd i j) (j
#align int.gcd_div_gcd_div_gcd Int.gcd_div_gcd_div_gcd
theorem gcd_dvd_gcd_of_dvd_left {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd i j ∣ gcd k j :=
- Int.coe_nat_dvd.1 <| dvd_gcd (gcd_dvd_left.trans H) gcd_dvd_right
+ Int.natCast_dvd_natCast.1 <| dvd_gcd (gcd_dvd_left.trans H) gcd_dvd_right
#align int.gcd_dvd_gcd_of_dvd_left Int.gcd_dvd_gcd_of_dvd_left
theorem gcd_dvd_gcd_of_dvd_right {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd j i ∣ gcd j k :=
- Int.coe_nat_dvd.1 <| dvd_gcd gcd_dvd_left (gcd_dvd_right.trans H)
+ Int.natCast_dvd_natCast.1 <| dvd_gcd gcd_dvd_left (gcd_dvd_right.trans H)
#align int.gcd_dvd_gcd_of_dvd_right Int.gcd_dvd_gcd_of_dvd_right
theorem gcd_dvd_gcd_mul_left (i j k : ℤ) : gcd i j ∣ gcd (k * i) j :=
@@ -375,7 +375,7 @@ theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑
rw [← Nat.mul_div_cancel' h, Int.ofNat_mul, gcd_eq_gcd_ab, add_mul, mul_assoc, mul_assoc]
exact ⟨_, _, rfl⟩
· rintro ⟨x, y, h⟩
- rw [← Int.coe_nat_dvd, h]
+ rw [← Int.natCast_dvd_natCast, h]
exact
dvd_add (dvd_mul_of_dvd_left gcd_dvd_left _) (dvd_mul_of_dvd_left gcd_dvd_right y)
#align int.gcd_dvd_iff Int.gcd_dvd_iff
@@ -462,7 +462,7 @@ theorem lcm_one_right (i : ℤ) : lcm i 1 = natAbs i := by
theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k := by
rw [Int.lcm]
intro hi hj
- exact coe_nat_dvd_left.mpr (Nat.lcm_dvd (natAbs_dvd_natAbs.mpr hi) (natAbs_dvd_natAbs.mpr hj))
+ exact natCast_dvd.mpr (Nat.lcm_dvd (natAbs_dvd_natAbs.mpr hi) (natAbs_dvd_natAbs.mpr hj))
#align int.lcm_dvd Int.lcm_dvd
theorem lcm_mul_left {m n k : ℤ} : (m * n).lcm (m * k) = natAbs m * n.lcm k := by
zpow_coe_nat
to zpow_natCast
(#11528)
... and add a deprecated alias for the old name. This is mostly just me discovering the power of F2
@@ -479,7 +479,7 @@ theorem pow_gcd_eq_one {M : Type*} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
rcases m with (rfl | m); · simp [hn]
obtain ⟨y, rfl⟩ := isUnit_ofPowEqOne hm m.succ_ne_zero
simp only [← Units.val_pow_eq_pow_val] at *
- rw [← Units.val_one, ← zpow_coe_nat, ← Units.ext_iff] at *
+ rw [← Units.val_one, ← zpow_natCast, ← Units.ext_iff] at *
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
#align gcd_nsmul_eq_zero gcd_nsmul_eq_zero
@@ -498,10 +498,10 @@ protected lemma Commute.pow_eq_pow_iff_of_coprime (hab : Commute a b) (hmn : m.C
by_cases ha : a = 0; · exact ⟨0, by have := h.symm; aesop⟩
refine ⟨a ^ Nat.gcdB m n * b ^ Nat.gcdA m n, ?_, ?_⟩ <;>
· refine (pow_one _).symm.trans ?_
- conv_lhs => rw [← zpow_coe_nat, ← hmn, Nat.gcd_eq_gcd_ab]
- simp only [zpow_add₀ ha, zpow_add₀ hb, ← zpow_coe_nat, (hab.zpow_zpow₀ _ _).mul_zpow,
+ conv_lhs => rw [← zpow_natCast, ← hmn, Nat.gcd_eq_gcd_ab]
+ simp only [zpow_add₀ ha, zpow_add₀ hb, ← zpow_natCast, (hab.zpow_zpow₀ _ _).mul_zpow,
← zpow_mul, mul_comm (Nat.gcdB m n), mul_comm (Nat.gcdA m n)]
- simp only [zpow_mul, zpow_coe_nat, h]
+ simp only [zpow_mul, zpow_natCast, h]
exact ((Commute.pow_pow (by aesop) _ _).zpow_zpow₀ _ _).symm
end GroupWithZero
GroupWithZero
lemmas earlier (#10919)
Move from Algebra.GroupWithZero.Units.Lemmas
to Algebra.GroupWithZero.Units.Basic
the lemmas that can be moved.
@@ -3,6 +3,7 @@ Copyright (c) 2018 Guy Leroy. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
-/
+import Mathlib.Algebra.Group.Commute.Units
import Mathlib.Algebra.GroupWithZero.Power
import Mathlib.Algebra.Ring.Regular
import Mathlib.Data.Int.Dvd.Basic
Homogenises porting notes via capitalisation and addition of whitespace.
It makes the following changes:
@@ -46,7 +46,7 @@ def xgcdAux : ℕ → ℤ → ℤ → ℕ → ℤ → ℤ → ℕ × ℤ × ℤ
xgcdAux (r' % succ k) (s' - q * s) (t' - q * t) (succ k) s t
#align nat.xgcd_aux Nat.xgcdAux
--- porting note: these are not in mathlib3; these equation lemmas are to fix
+-- Porting note: these are not in mathlib3; these equation lemmas are to fix
-- complaints by the Lean 4 `unusedHavesSuffices` linter obtained when `simp [xgcdAux]` is used.
theorem xgcdAux_zero : xgcdAux 0 s t r' s' t' = (r', s', t') := rfl
zpow_ofNat
and ofNat_zsmul
(#10969)
Previously these were syntactically identical to the corresponding zpow_coe_nat
and coe_nat_zsmul
lemmas, now they are about OfNat.ofNat
.
Unfortunately, almost every call site uses the ofNat
name to refer to Nat.cast
, so the downstream proofs had to be adjusted too.
@@ -497,10 +497,10 @@ protected lemma Commute.pow_eq_pow_iff_of_coprime (hab : Commute a b) (hmn : m.C
by_cases ha : a = 0; · exact ⟨0, by have := h.symm; aesop⟩
refine ⟨a ^ Nat.gcdB m n * b ^ Nat.gcdA m n, ?_, ?_⟩ <;>
· refine (pow_one _).symm.trans ?_
- conv_lhs => rw [← zpow_ofNat, ← hmn, Nat.gcd_eq_gcd_ab]
- simp only [zpow_add₀ ha, zpow_add₀ hb, ← zpow_ofNat, (hab.zpow_zpow₀ _ _).mul_zpow, ← zpow_mul,
- mul_comm (Nat.gcdB m n), mul_comm (Nat.gcdA m n)]
- simp only [zpow_mul, zpow_ofNat, h]
+ conv_lhs => rw [← zpow_coe_nat, ← hmn, Nat.gcd_eq_gcd_ab]
+ simp only [zpow_add₀ ha, zpow_add₀ hb, ← zpow_coe_nat, (hab.zpow_zpow₀ _ _).mul_zpow,
+ ← zpow_mul, mul_comm (Nat.gcdB m n), mul_comm (Nat.gcdA m n)]
+ simp only [zpow_mul, zpow_coe_nat, h]
exact ((Commute.pow_pow (by aesop) _ _).zpow_zpow₀ _ _).symm
end GroupWithZero
Notable changes: lemmas were added in https://github.com/leanprover/std4/pull/538 about gcd
and lcm
, that now have implicit arguments. Mostly this is a positive change in Mathlib, we can just delete the arguments. The one to consider in review is in ModEq
.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com>
@@ -231,9 +231,6 @@ theorem dvd_of_mul_dvd_mul_right {i j k : ℤ} (k_non_zero : k ≠ 0) (H : i * k
rw [mul_comm i k, mul_comm j k] at H; exact dvd_of_mul_dvd_mul_left k_non_zero H
#align int.dvd_of_mul_dvd_mul_right Int.dvd_of_mul_dvd_mul_right
-/-- ℤ specific version of least common multiple. -/
-def lcm (i j : ℤ) : ℕ :=
- Nat.lcm (natAbs i) (natAbs j)
#align int.lcm Int.lcm
theorem lcm_def (i j : ℤ) : lcm i j = Nat.lcm (natAbs i) (natAbs j) :=
@@ -244,12 +241,7 @@ protected theorem coe_nat_lcm (m n : ℕ) : Int.lcm ↑m ↑n = Nat.lcm m n :=
rfl
#align int.coe_nat_lcm Int.coe_nat_lcm
-theorem gcd_dvd_left (i j : ℤ) : (gcd i j : ℤ) ∣ i :=
- dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_left _ _
#align int.gcd_dvd_left Int.gcd_dvd_left
-
-theorem gcd_dvd_right (i j : ℤ) : (gcd i j : ℤ) ∣ j :=
- dvd_natAbs.mp <| coe_nat_dvd.mpr <| Nat.gcd_dvd_right _ _
#align int.gcd_dvd_right Int.gcd_dvd_right
theorem dvd_gcd {i j k : ℤ} (h1 : k ∣ i) (h2 : k ∣ j) : k ∣ gcd i j :=
@@ -281,23 +273,10 @@ theorem gcd_zero_left (i : ℤ) : gcd 0 i = natAbs i := by simp [gcd]
theorem gcd_zero_right (i : ℤ) : gcd i 0 = natAbs i := by simp [gcd]
#align int.gcd_zero_right Int.gcd_zero_right
-@[simp]
-theorem gcd_one_left (i : ℤ) : gcd 1 i = 1 :=
- Nat.gcd_one_left _
-#align int.gcd_one_left Int.gcd_one_left
-
-@[simp]
-theorem gcd_one_right (i : ℤ) : gcd i 1 = 1 :=
- Nat.gcd_one_right _
-#align int.gcd_one_right Int.gcd_one_right
-
-@[simp]
-theorem gcd_neg_right {x y : ℤ} : gcd x (-y) = gcd x y := by rw [Int.gcd, Int.gcd, natAbs_neg]
-#align int.gcd_neg_right Int.gcd_neg_right
-
-@[simp]
-theorem gcd_neg_left {x y : ℤ} : gcd (-x) y = gcd x y := by rw [Int.gcd, Int.gcd, natAbs_neg]
-#align int.gcd_neg_left Int.gcd_neg_left
+#align int.gcd_one_left Int.one_gcd
+#align int.gcd_one_right Int.gcd_one
+#align int.gcd_neg_right Int.gcd_neg
+#align int.gcd_neg_left Int.neg_gcd
theorem gcd_mul_left (i j k : ℤ) : gcd (i * j) (i * k) = natAbs i * gcd j k := by
rw [Int.gcd, Int.gcd, natAbs_mul, natAbs_mul]
@@ -332,15 +311,15 @@ theorem gcd_div {i j k : ℤ} (H1 : k ∣ i) (H2 : k ∣ j) :
#align int.gcd_div Int.gcd_div
theorem gcd_div_gcd_div_gcd {i j : ℤ} (H : 0 < gcd i j) : gcd (i / gcd i j) (j / gcd i j) = 1 := by
- rw [gcd_div (gcd_dvd_left i j) (gcd_dvd_right i j), natAbs_ofNat, Nat.div_self H]
+ rw [gcd_div gcd_dvd_left gcd_dvd_right, natAbs_ofNat, Nat.div_self H]
#align int.gcd_div_gcd_div_gcd Int.gcd_div_gcd_div_gcd
theorem gcd_dvd_gcd_of_dvd_left {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd i j ∣ gcd k j :=
- Int.coe_nat_dvd.1 <| dvd_gcd ((gcd_dvd_left i j).trans H) (gcd_dvd_right i j)
+ Int.coe_nat_dvd.1 <| dvd_gcd (gcd_dvd_left.trans H) gcd_dvd_right
#align int.gcd_dvd_gcd_of_dvd_left Int.gcd_dvd_gcd_of_dvd_left
theorem gcd_dvd_gcd_of_dvd_right {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd j i ∣ gcd j k :=
- Int.coe_nat_dvd.1 <| dvd_gcd (gcd_dvd_left j i) ((gcd_dvd_right j i).trans H)
+ Int.coe_nat_dvd.1 <| dvd_gcd gcd_dvd_left (gcd_dvd_right.trans H)
#align int.gcd_dvd_gcd_of_dvd_right Int.gcd_dvd_gcd_of_dvd_right
theorem gcd_dvd_gcd_mul_left (i j k : ℤ) : gcd i j ∣ gcd (k * i) j :=
@@ -373,8 +352,8 @@ theorem ne_zero_of_gcd {x y : ℤ} (hc : gcd x y ≠ 0) : x ≠ 0 ∨ y ≠ 0 :=
theorem exists_gcd_one {m n : ℤ} (H : 0 < gcd m n) :
∃ m' n' : ℤ, gcd m' n' = 1 ∧ m = m' * gcd m n ∧ n = n' * gcd m n :=
- ⟨_, _, gcd_div_gcd_div_gcd H, (Int.ediv_mul_cancel (gcd_dvd_left m n)).symm,
- (Int.ediv_mul_cancel (gcd_dvd_right m n)).symm⟩
+ ⟨_, _, gcd_div_gcd_div_gcd H, (Int.ediv_mul_cancel gcd_dvd_left).symm,
+ (Int.ediv_mul_cancel gcd_dvd_right).symm⟩
#align int.exists_gcd_one Int.exists_gcd_one
theorem exists_gcd_one' {m n : ℤ} (H : 0 < gcd m n) :
@@ -397,13 +376,13 @@ theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑
· rintro ⟨x, y, h⟩
rw [← Int.coe_nat_dvd, h]
exact
- dvd_add (dvd_mul_of_dvd_left (gcd_dvd_left a b) _) (dvd_mul_of_dvd_left (gcd_dvd_right a b) y)
+ dvd_add (dvd_mul_of_dvd_left gcd_dvd_left _) (dvd_mul_of_dvd_left gcd_dvd_right y)
#align int.gcd_dvd_iff Int.gcd_dvd_iff
theorem gcd_greatest {a b d : ℤ} (hd_pos : 0 ≤ d) (hda : d ∣ a) (hdb : d ∣ b)
(hd : ∀ e : ℤ, e ∣ a → e ∣ b → e ∣ d) : d = gcd a b :=
dvd_antisymm hd_pos (ofNat_zero_le (gcd a b)) (dvd_gcd hda hdb)
- (hd _ (gcd_dvd_left a b) (gcd_dvd_right a b))
+ (hd _ gcd_dvd_left gcd_dvd_right)
#align int.gcd_greatest Int.gcd_greatest
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a c = 1` then `a ∣ b`.
@@ -475,22 +454,8 @@ theorem lcm_one_right (i : ℤ) : lcm i 1 = natAbs i := by
apply Nat.lcm_one_right
#align int.lcm_one_right Int.lcm_one_right
-@[simp]
-theorem lcm_self (i : ℤ) : lcm i i = natAbs i := by
- rw [Int.lcm]
- apply Nat.lcm_self
#align int.lcm_self Int.lcm_self
-
-theorem dvd_lcm_left (i j : ℤ) : i ∣ lcm i j := by
- rw [Int.lcm]
- apply coe_nat_dvd_right.mpr
- apply Nat.dvd_lcm_left
#align int.dvd_lcm_left Int.dvd_lcm_left
-
-theorem dvd_lcm_right (i j : ℤ) : j ∣ lcm i j := by
- rw [Int.lcm]
- apply coe_nat_dvd_right.mpr
- apply Nat.dvd_lcm_right
#align int.dvd_lcm_right Int.dvd_lcm_right
theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k := by
@@ -528,11 +528,10 @@ protected lemma Commute.pow_eq_pow_iff_of_coprime (hab : Commute a b) (hmn : m.C
refine ⟨fun h ↦ ?_, by rintro ⟨c, rfl, rfl⟩; rw [← pow_mul, ← pow_mul']⟩
by_cases m = 0; · aesop
by_cases n = 0; · aesop
- by_cases hb : b = 0; exact ⟨0, by aesop⟩
- by_cases ha : a = 0; exact ⟨0, by have := h.symm; aesop⟩
- refine ⟨a ^ Nat.gcdB m n * b ^ Nat.gcdA m n, ?_, ?_⟩
- all_goals
- refine (pow_one _).symm.trans ?_
+ by_cases hb : b = 0; · exact ⟨0, by aesop⟩
+ by_cases ha : a = 0; · exact ⟨0, by have := h.symm; aesop⟩
+ refine ⟨a ^ Nat.gcdB m n * b ^ Nat.gcdA m n, ?_, ?_⟩ <;>
+ · refine (pow_one _).symm.trans ?_
conv_lhs => rw [← zpow_ofNat, ← hmn, Nat.gcd_eq_gcd_ab]
simp only [zpow_add₀ ha, zpow_add₀ hb, ← zpow_ofNat, (hab.zpow_zpow₀ _ _).mul_zpow, ← zpow_mul,
mul_comm (Nat.gcdB m n), mul_comm (Nat.gcdA m n)]
@@ -3,7 +3,6 @@ Copyright (c) 2018 Guy Leroy. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
-/
-import Mathlib.Algebra.GroupPower.Lemmas
import Mathlib.Algebra.GroupWithZero.Power
import Mathlib.Algebra.Ring.Regular
import Mathlib.Data.Int.Dvd.Basic
@@ -3,10 +3,11 @@ Copyright (c) 2018 Guy Leroy. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
-/
-import Mathlib.Data.Nat.GCD.Basic
import Mathlib.Algebra.GroupPower.Lemmas
+import Mathlib.Algebra.GroupWithZero.Power
import Mathlib.Algebra.Ring.Regular
import Mathlib.Data.Int.Dvd.Basic
+import Mathlib.Data.Nat.GCD.Basic
import Mathlib.Order.Bounds.Basic
#align_import data.int.gcd from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
@@ -517,3 +518,38 @@ theorem pow_gcd_eq_one {M : Type*} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
#align gcd_nsmul_eq_zero gcd_nsmul_eq_zero
+
+variable {α : Type*}
+
+section GroupWithZero
+variable [GroupWithZero α] {a b : α} {m n : ℕ}
+
+protected lemma Commute.pow_eq_pow_iff_of_coprime (hab : Commute a b) (hmn : m.Coprime n) :
+ a ^ m = b ^ n ↔ ∃ c, a = c ^ n ∧ b = c ^ m := by
+ refine ⟨fun h ↦ ?_, by rintro ⟨c, rfl, rfl⟩; rw [← pow_mul, ← pow_mul']⟩
+ by_cases m = 0; · aesop
+ by_cases n = 0; · aesop
+ by_cases hb : b = 0; exact ⟨0, by aesop⟩
+ by_cases ha : a = 0; exact ⟨0, by have := h.symm; aesop⟩
+ refine ⟨a ^ Nat.gcdB m n * b ^ Nat.gcdA m n, ?_, ?_⟩
+ all_goals
+ refine (pow_one _).symm.trans ?_
+ conv_lhs => rw [← zpow_ofNat, ← hmn, Nat.gcd_eq_gcd_ab]
+ simp only [zpow_add₀ ha, zpow_add₀ hb, ← zpow_ofNat, (hab.zpow_zpow₀ _ _).mul_zpow, ← zpow_mul,
+ mul_comm (Nat.gcdB m n), mul_comm (Nat.gcdA m n)]
+ simp only [zpow_mul, zpow_ofNat, h]
+ exact ((Commute.pow_pow (by aesop) _ _).zpow_zpow₀ _ _).symm
+
+end GroupWithZero
+
+section CommGroupWithZero
+variable [CommGroupWithZero α] {a b : α} {m n : ℕ}
+
+lemma pow_eq_pow_iff_of_coprime (hmn : m.Coprime n) : a ^ m = b ^ n ↔ ∃ c, a = c ^ n ∧ b = c ^ m :=
+ (Commute.all _ _).pow_eq_pow_iff_of_coprime hmn
+
+lemma pow_mem_range_pow_of_coprime (hmn : m.Coprime n) (a : α) :
+ a ^ m ∈ Set.range (· ^ n : α → α) ↔ a ∈ Set.range (· ^ n : α → α) := by
+ simp [pow_eq_pow_iff_of_coprime hmn.symm]; aesop
+
+end CommGroupWithZero
$
with <|
(#9319)
See Zulip thread for the discussion.
@@ -310,11 +310,11 @@ theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * natAbs j :
#align int.gcd_mul_right Int.gcd_mul_right
theorem gcd_pos_of_ne_zero_left {i : ℤ} (j : ℤ) (hi : i ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_left _ $ natAbs_pos.2 hi
+ Nat.gcd_pos_of_pos_left _ <| natAbs_pos.2 hi
#align int.gcd_pos_of_ne_zero_left Int.gcd_pos_of_ne_zero_left
theorem gcd_pos_of_ne_zero_right (i : ℤ) {j : ℤ} (hj : j ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_right _ $ natAbs_pos.2 hj
+ Nat.gcd_pos_of_pos_right _ <| natAbs_pos.2 hj
#align int.gcd_pos_of_ne_zero_right Int.gcd_pos_of_ne_zero_right
theorem gcd_eq_zero_iff {i j : ℤ} : gcd i j = 0 ↔ i = 0 ∧ j = 0 := by
Removes nonterminal simps on lines looking like simp [...]
@@ -114,7 +114,7 @@ theorem gcdB_zero_right {s : ℕ} (h : s ≠ 0) : gcdB s 0 = 0 := by
@[simp]
theorem xgcdAux_fst (x y) : ∀ s t s' t', (xgcdAux x s t y s' t').1 = gcd x y :=
gcd.induction x y (by simp) fun x y h IH s t s' t' => by
- simp [xgcdAux_rec, h, IH]
+ simp only [h, xgcdAux_rec, IH]
rw [← gcd_rec]
#align nat.xgcd_aux_fst Nat.xgcdAux_fst
@@ -51,7 +51,7 @@ def xgcdAux : ℕ → ℤ → ℤ → ℕ → ℤ → ℤ → ℕ × ℤ × ℤ
theorem xgcdAux_zero : xgcdAux 0 s t r' s' t' = (r', s', t') := rfl
theorem xgcdAux_succ : xgcdAux (succ k) s t r' s' t' =
- xgcdAux (r' % succ k) (s' - (r' / succ k) * s) (t' - (r' / succ k) * t) (succ k) s t := rfl
+ xgcdAux (r' % succ k) (s' - (r' / succ k) * s) (t' - (r' / succ k) * t) (succ k) s t := rfl
@[simp]
theorem xgcd_zero_left {s t r' s' t'} : xgcdAux 0 s t r' s' t' = (r', s', t') := by simp [xgcdAux]
Nat.lcm_mul_left
and Nat.lcm_mul_right
(#6990)
Add two lemmas about Nat.lcm
. These results mirror Nat.gcd_mul_left present in Std.
Co-authored-by: Arend Mellendijk <FLDutchmann@users.noreply.github.com>
@@ -499,6 +499,12 @@ theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k :=
exact coe_nat_dvd_left.mpr (Nat.lcm_dvd (natAbs_dvd_natAbs.mpr hi) (natAbs_dvd_natAbs.mpr hj))
#align int.lcm_dvd Int.lcm_dvd
+theorem lcm_mul_left {m n k : ℤ} : (m * n).lcm (m * k) = natAbs m * n.lcm k := by
+ simp_rw [Int.lcm, natAbs_mul, Nat.lcm_mul_left]
+
+theorem lcm_mul_right {m n k : ℤ} : (m * n).lcm (k * n) = m.lcm k * natAbs n := by
+ simp_rw [Int.lcm, natAbs_mul, Nat.lcm_mul_right]
+
end Int
@[to_additive gcd_nsmul_eq_zero]
@@ -167,7 +167,7 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
← Int.mul_emod]
#align nat.exists_mul_mod_eq_gcd Nat.exists_mul_emod_eq_gcd
-theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : coprime n k) (hk : 1 < k) :
+theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : Coprime n k) (hk : 1 < k) :
∃ m, n * m % k = 1 :=
Exists.recOn (exists_mul_emod_eq_gcd (lt_of_le_of_lt (le_of_eq hkn) hk)) fun m hm ↦
⟨m, hm.trans hkn⟩
@@ -167,7 +167,7 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
← Int.mul_emod]
#align nat.exists_mul_mod_eq_gcd Nat.exists_mul_emod_eq_gcd
-theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : Coprime n k) (hk : 1 < k) :
+theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : coprime n k) (hk : 1 < k) :
∃ m, n * m % k = 1 :=
Exists.recOn (exists_mul_emod_eq_gcd (lt_of_le_of_lt (le_of_eq hkn) hk)) fun m hm ↦
⟨m, hm.trans hkn⟩
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>
@@ -167,7 +167,7 @@ theorem exists_mul_emod_eq_gcd {k n : ℕ} (hk : gcd n k < k) : ∃ m, n * m % k
← Int.mul_emod]
#align nat.exists_mul_mod_eq_gcd Nat.exists_mul_emod_eq_gcd
-theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : coprime n k) (hk : 1 < k) :
+theorem exists_mul_emod_eq_one_of_coprime {k n : ℕ} (hkn : Coprime n k) (hk : 1 < k) :
∃ m, n * m % k = 1 :=
Exists.recOn (exists_mul_emod_eq_gcd (lt_of_le_of_lt (le_of_eq hkn) hk)) fun m hm ↦
⟨m, hm.trans hkn⟩
Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.
The intent of this PR is to make autoImplicit
opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true
in the few files that rely on it.
That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.
I claim that many of the uses of autoImplicit
in these files are accidental; situations such as:
variables
are in scope, but pasting the lemma in the wrong sectionHaving set_option autoImplicit false
as the default prevents these types of mistake being made in the 90% of files where autoImplicit
s are not used at all, and causes them to be caught by CI during review.
I think there were various points during the port where we encouraged porters to delete the universes u v
lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.
A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18
as the no:dontcare:yes
vote ratio.
While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true
has been placed locally within a section, rather than at the top of the file.
@@ -29,6 +29,8 @@ import Mathlib.Order.Bounds.Basic
Bézout's lemma, Bezout's lemma
-/
+set_option autoImplicit true
+
/-! ### Extended Euclidean algorithm -/
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -500,7 +500,7 @@ theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k :=
end Int
@[to_additive gcd_nsmul_eq_zero]
-theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m = 1) (hn : x ^ n = 1) :
+theorem pow_gcd_eq_one {M : Type*} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m = 1) (hn : x ^ n = 1) :
x ^ m.gcd n = 1 := by
rcases m with (rfl | m); · simp [hn]
obtain ⟨y, rfl⟩ := isUnit_ofPowEqOne hm m.succ_ne_zero
@@ -2,11 +2,6 @@
Copyright (c) 2018 Guy Leroy. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.int.gcd
-! 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.Nat.GCD.Basic
import Mathlib.Algebra.GroupPower.Lemmas
@@ -14,6 +9,8 @@ import Mathlib.Algebra.Ring.Regular
import Mathlib.Data.Int.Dvd.Basic
import Mathlib.Order.Bounds.Basic
+#align_import data.int.gcd from "leanprover-community/mathlib"@"47a1a73351de8dd6c8d3d32b569c8e434b03ca47"
+
/-!
# Extended GCD and divisibility over ℤ
@@ -20,12 +20,12 @@ import Mathlib.Order.Bounds.Basic
## Main definitions
* Given `x y : ℕ`, `xgcd x y` computes the pair of integers `(a, b)` such that
- `gcd x y = x * a + y * b`. `gcd_a x y` and `gcd_b x y` are defined to be `a` and `b`,
+ `gcd x y = x * a + y * b`. `gcdA x y` and `gcdB x y` are defined to be `a` and `b`,
respectively.
## Main statements
-* `gcd_eq_gcd_ab`: Bézout's lemma, given `x y : ℕ`, `gcd x y = x * gcd_a x y + y * gcd_b x y`.
+* `gcd_eq_gcd_ab`: Bézout's lemma, given `x y : ℕ`, `gcd x y = x * gcdA x y + y * gcdB x y`.
## Tags
@@ -58,11 +58,11 @@ theorem xgcdAux_succ : xgcdAux (succ k) s t r' s' t' =
theorem xgcd_zero_left {s t r' s' t'} : xgcdAux 0 s t r' s' t' = (r', s', t') := by simp [xgcdAux]
#align nat.xgcd_zero_left Nat.xgcd_zero_left
-theorem xgcd_aux_rec {r s t r' s' t'} (h : 0 < r) :
+theorem xgcdAux_rec {r s t r' s' t'} (h : 0 < r) :
xgcdAux r s t r' s' t' = xgcdAux (r' % r) (s' - r' / r * s) (t' - r' / r * t) r s t := by
obtain ⟨r, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h.ne'
rfl
-#align nat.xgcd_aux_rec Nat.xgcd_aux_rec
+#align nat.xgcd_aux_rec Nat.xgcdAux_rec
/-- Use the extended GCD algorithm to generate the `a` and `b` values
satisfying `gcd x y = x * a + y * b`. -/
@@ -96,7 +96,8 @@ theorem gcdB_zero_left {s : ℕ} : gcdB 0 s = 1 := by
theorem gcdA_zero_right {s : ℕ} (h : s ≠ 0) : gcdA s 0 = 1 := by
unfold gcdA xgcd
obtain ⟨s, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h
- -- Porting note: `simp [xgcdAux_succ]` crashes Lean here
+ -- Porting note (https://github.com/leanprover/lean4/issues/2330):
+ -- `simp [xgcdAux_succ]` crashes Lean here
rw [xgcdAux_succ]
rfl
#align nat.gcd_a_zero_right Nat.gcdA_zero_right
@@ -105,21 +106,22 @@ theorem gcdA_zero_right {s : ℕ} (h : s ≠ 0) : gcdA s 0 = 1 := by
theorem gcdB_zero_right {s : ℕ} (h : s ≠ 0) : gcdB s 0 = 0 := by
unfold gcdB xgcd
obtain ⟨s, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h
- -- Porting note: `simp [xgcdAux_succ]` crashes Lean here
+ -- Porting note (https://github.com/leanprover/lean4/issues/2330):
+ -- `simp [xgcdAux_succ]` crashes Lean here
rw [xgcdAux_succ]
rfl
#align nat.gcd_b_zero_right Nat.gcdB_zero_right
@[simp]
-theorem xgcd_aux_fst (x y) : ∀ s t s' t', (xgcdAux x s t y s' t').1 = gcd x y :=
+theorem xgcdAux_fst (x y) : ∀ s t s' t', (xgcdAux x s t y s' t').1 = gcd x y :=
gcd.induction x y (by simp) fun x y h IH s t s' t' => by
- simp [xgcd_aux_rec, h, IH]
+ simp [xgcdAux_rec, h, IH]
rw [← gcd_rec]
-#align nat.xgcd_aux_fst Nat.xgcd_aux_fst
+#align nat.xgcd_aux_fst Nat.xgcdAux_fst
-theorem xgcd_aux_val (x y) : xgcdAux x 1 0 y 0 1 = (gcd x y, xgcd x y) := by
- rw [xgcd, ← xgcd_aux_fst x y 1 0 0 1]
-#align nat.xgcd_aux_val Nat.xgcd_aux_val
+theorem xgcdAux_val (x y) : xgcdAux x 1 0 y 0 1 = (gcd x y, xgcd x y) := by
+ rw [xgcd, ← xgcdAux_fst x y 1 0 0 1]
+#align nat.xgcd_aux_val Nat.xgcdAux_val
theorem xgcd_val (x y) : xgcd x y = (gcdA x y, gcdB x y) := by
unfold gcdA gcdB; cases xgcd x y; rfl
@@ -132,25 +134,25 @@ variable (x y : ℕ)
private def P : ℕ × ℤ × ℤ → Prop
| (r, s, t) => (r : ℤ) = x * s + y * t
-theorem xgcd_aux_P {r r'} :
+theorem xgcdAux_P {r r'} :
∀ {s t s' t'}, P x y (r, s, t) → P x y (r', s', t') → P x y (xgcdAux r s t r' s' t') := by
induction r, r' using gcd.induction with
| H0 => simp
| H1 a b h IH =>
intro s t s' t' p p'
- rw [xgcd_aux_rec h]; refine' IH _ p; dsimp [P] at *
+ rw [xgcdAux_rec h]; refine' IH _ p; dsimp [P] at *
rw [Int.emod_def]; generalize (b / a : ℤ) = k
rw [p, p', mul_sub, sub_add_eq_add_sub, mul_sub, add_mul, mul_comm k t, mul_comm k s,
← mul_assoc, ← mul_assoc, add_comm (x * s * k), ← add_sub_assoc, sub_sub]
set_option linter.uppercaseLean3 false in
-#align nat.xgcd_aux_P Nat.xgcd_aux_P
+#align nat.xgcd_aux_P Nat.xgcdAux_P
/-- **Bézout's lemma**: given `x y : ℕ`, `gcd x y = x * a + y * b`, where `a = gcd_a x y` and
`b = gcd_b x y` are computed by the extended Euclidean algorithm.
-/
theorem gcd_eq_gcd_ab : (gcd x y : ℤ) = x * gcdA x y + y * gcdB x y := by
- have := @xgcd_aux_P x y x y 1 0 0 1 (by simp [P]) (by simp [P])
- rwa [xgcd_aux_val, xgcd_val] at this
+ have := @xgcdAux_P x y x y 1 0 0 1 (by simp [P]) (by simp [P])
+ rwa [xgcdAux_val, xgcd_val] at this
#align nat.gcd_eq_gcd_ab Nat.gcd_eq_gcd_ab
end
@@ -212,8 +214,8 @@ theorem gcd_eq_gcd_ab : ∀ x y : ℤ, (gcd x y : ℤ) = x * gcdA x y + y * gcdB
theorem natAbs_ediv (a b : ℤ) (H : b ∣ a) : natAbs (a / b) = natAbs a / natAbs b := by
rcases Nat.eq_zero_or_pos (natAbs b) with (h | h)
- rw [natAbs_eq_zero.1 h]
- simp [Int.ediv_zero]
+ · rw [natAbs_eq_zero.1 h]
+ simp [Int.ediv_zero]
calc
natAbs (a / b) = natAbs (a / b) * 1 := by rw [mul_one]
_ = natAbs (a / b) * (natAbs b / natAbs b) := by rw [Nat.div_self h]
@@ -377,7 +377,7 @@ theorem exists_gcd_one {m n : ℤ} (H : 0 < gcd m n) :
#align int.exists_gcd_one Int.exists_gcd_one
theorem exists_gcd_one' {m n : ℤ} (H : 0 < gcd m n) :
- ∃ (g : ℕ)(m' n' : ℤ), 0 < g ∧ gcd m' n' = 1 ∧ m = m' * g ∧ n = n' * g :=
+ ∃ (g : ℕ) (m' n' : ℤ), 0 < g ∧ gcd m' n' = 1 ∧ m = m' * g ∧ n = n' * g :=
let ⟨m', n', h⟩ := exists_gcd_one H
⟨_, m', n', H, h⟩
#align int.exists_gcd_one' Int.exists_gcd_one'
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>
@@ -9,10 +9,10 @@ Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
! if you have ported upstream changes.
-/
import Mathlib.Data.Nat.GCD.Basic
+import Mathlib.Algebra.GroupPower.Lemmas
import Mathlib.Algebra.Ring.Regular
import Mathlib.Data.Int.Dvd.Basic
import Mathlib.Order.Bounds.Basic
-import Mathlib.Tactic.NormNum
/-!
# Extended GCD and divisibility over ℤ
@@ -179,6 +179,8 @@ end Nat
namespace Int
+theorem gcd_def (i j : ℤ) : gcd i j = Nat.gcd i.natAbs j.natAbs := rfl
+
protected theorem coe_nat_gcd (m n : ℕ) : Int.gcd ↑m ↑n = Nat.gcd m n :=
rfl
#align int.coe_nat_gcd Int.coe_nat_gcd
@@ -508,258 +510,3 @@ theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
#align gcd_nsmul_eq_zero gcd_nsmul_eq_zero
-
-/-! ### GCD prover -/
-
--- open NormNum
-
--- namespace Tactic
-
--- namespace NormNum
-
--- theorem int_gcd_helper' {d : ℕ} {x y a b : ℤ} (h₁ : (d : ℤ) ∣ x) (h₂ : (d : ℤ) ∣ y)
--- (h₃ : x * a + y * b = d) : Int.gcd x y = d := by
--- refine' Nat.dvd_antisymm _ (Int.coe_nat_dvd.1 (Int.dvd_gcd h₁ h₂))
--- rw [← Int.coe_nat_dvd, ← h₃]
--- apply dvd_add
--- · exact (Int.gcd_dvd_left _ _).mul_right _
--- · exact (Int.gcd_dvd_right _ _).mul_right _
--- #align tactic.norm_num.int_gcd_helper' Tactic.NormNum.int_gcd_helper'
-
--- theorem nat_gcd_helper_dvd_left (x y a : ℕ) (h : x * a = y) : Nat.gcd x y = x :=
--- Nat.gcd_eq_left ⟨a, h.symm⟩
--- #align tactic.norm_num.nat_gcd_helper_dvd_left Tactic.NormNum.nat_gcd_helper_dvd_left
-
--- theorem nat_gcd_helper_dvd_right (x y a : ℕ) (h : y * a = x) : Nat.gcd x y = y :=
--- Nat.gcd_eq_right ⟨a, h.symm⟩
--- #align tactic.norm_num.nat_gcd_helper_dvd_right Tactic.NormNum.nat_gcd_helper_dvd_right
-
--- theorem nat_gcd_helper_2 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
--- (hx : x * a = tx) (hy : y * b = ty) (h : ty + d = tx) : Nat.gcd x y = d := by
--- rw [← Int.coe_nat_gcd];
--- apply
--- @int_gcd_helper' _ _ _ a (-b) (Int.coe_nat_dvd.2 ⟨_, hu.symm⟩) (Int.coe_nat_dvd.2
--- ⟨_, hv.symm⟩)
--- rw [mul_neg, ← sub_eq_add_neg, sub_eq_iff_eq_add']
--- norm_cast; rw [hx, hy, h]
--- #align tactic.norm_num.nat_gcd_helper_2 Tactic.NormNum.nat_gcd_helper_2
-
--- theorem nat_gcd_helper_1 (d x y a b u v tx ty : ℕ) (hu : d * u = x) (hv : d * v = y)
--- (hx : x * a = tx) (hy : y * b = ty) (h : tx + d = ty) : Nat.gcd x y = d :=
--- (Nat.gcd_comm _ _).trans <| nat_gcd_helper_2 _ _ _ _ _ _ _ _ _ hv hu hy hx h
--- #align tactic.norm_num.nat_gcd_helper_1 Tactic.NormNum.nat_gcd_helper_1
-
--- --Porting note: the `simp only` was not necessary in Lean3.
--- theorem nat_lcm_helper (x y d m n : ℕ) (hd : Nat.gcd x y = d) (d0 : 0 < d) (xy : x * y = n)
--- (dm : d * m = n) : Nat.lcm x y = m :=
--- mul_right_injective₀ d0.ne' <| by simp only; rw [dm, ← xy, ← hd, Nat.gcd_mul_lcm]
--- #align tactic.norm_num.nat_lcm_helper Tactic.NormNum.nat_lcm_helper
-
--- theorem nat_coprime_helper_zero_left (x : ℕ) (h : 1 < x) : ¬Nat.coprime 0 x :=
--- mt (Nat.coprime_zero_left _).1 <| ne_of_gt h
--- #align tactic.norm_num.nat_coprime_helper_zero_left Tactic.NormNum.nat_coprime_helper_zero_left
-
--- theorem nat_coprime_helper_zero_right (x : ℕ) (h : 1 < x) : ¬Nat.coprime x 0 :=
--- mt (Nat.coprime_zero_right _).1 <| ne_of_gt h
--- #align tactic.norm_num.nat_coprime_helper_zero_right Tactic.NormNum.nat_coprime_helper_zero_right
-
--- theorem nat_coprime_helper_1 (x y a b tx ty : ℕ) (hx : x * a = tx) (hy : y * b = ty)
--- (h : tx + 1 = ty) : Nat.coprime x y :=
--- nat_gcd_helper_1 _ _ _ _ _ _ _ _ _ (one_mul _) (one_mul _) hx hy h
--- #align tactic.norm_num.nat_coprime_helper_1 Tactic.NormNum.nat_coprime_helper_1
-
--- theorem nat_coprime_helper_2 (x y a b tx ty : ℕ) (hx : x * a = tx) (hy : y * b = ty)
--- (h : ty + 1 = tx) : Nat.coprime x y :=
--- nat_gcd_helper_2 _ _ _ _ _ _ _ _ _ (one_mul _) (one_mul _) hx hy h
--- #align tactic.norm_num.nat_coprime_helper_2 Tactic.NormNum.nat_coprime_helper_2
-
--- theorem nat_not_coprime_helper (d x y u v : ℕ) (hu : d * u = x) (hv : d * v = y) (h : 1 < d) :
--- ¬Nat.coprime x y :=
--- Nat.not_coprime_of_dvd_of_dvd h ⟨_, hu.symm⟩ ⟨_, hv.symm⟩
--- #align tactic.norm_num.nat_not_coprime_helper Tactic.NormNum.nat_not_coprime_helper
-
--- theorem int_gcd_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
--- (h : Nat.gcd nx ny = d) : Int.gcd x y = d := by rwa [← hx, ← hy, Int.coe_nat_gcd]
--- #align tactic.norm_num.int_gcd_helper Tactic.NormNum.int_gcd_helper
-
--- theorem int_gcd_helper_neg_left (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : Int.gcd (-x) y = d :=
--- by rw [Int.gcd] at h⊢; rwa [Int.natAbs_neg]
--- #align tactic.norm_num.int_gcd_helper_neg_left Tactic.NormNum.int_gcd_helper_neg_left
-
--- theorem int_gcd_helper_neg_right (x y : ℤ) (d : ℕ) (h : Int.gcd x y = d) : Int.gcd x (-y) = d :=
--- by rw [Int.gcd] at h⊢; rwa [Int.natAbs_neg]
--- #align tactic.norm_num.int_gcd_helper_neg_right Tactic.NormNum.int_gcd_helper_neg_right
-
--- theorem int_lcm_helper (x y : ℤ) (nx ny d : ℕ) (hx : (nx : ℤ) = x) (hy : (ny : ℤ) = y)
--- (h : Nat.lcm nx ny = d) : Int.lcm x y = d := by rwa [← hx, ← hy, Int.coe_nat_lcm]
--- #align tactic.norm_num.int_lcm_helper Tactic.NormNum.int_lcm_helper
-
--- theorem int_lcm_helper_neg_left (x y : ℤ) (d : ℕ) (h : Int.lcm x y = d) : Int.lcm (-x) y = d :=
--- by rw [Int.lcm] at h⊢; rwa [Int.natAbs_neg]
--- #align tactic.norm_num.int_lcm_helper_neg_left Tactic.NormNum.int_lcm_helper_neg_left
-
--- theorem int_lcm_helper_neg_right (x y : ℤ) (d : ℕ) (h : Int.lcm x y = d) : Int.lcm x (-y) = d :=
--- by rw [Int.lcm] at h⊢; rwa [Int.natAbs_neg]
--- #align tactic.norm_num.int_lcm_helper_neg_right Tactic.NormNum.int_lcm_helper_neg_right
-
--- /-- Evaluates the `nat.gcd` function. -/
--- unsafe def prove_gcd_nat (c : instance_cache) (ex ey : expr) :
--- tactic (instance_cache × expr × expr) := do
--- let x ← ex.toNat
--- let y ← ey.toNat
--- match x, y with
--- | 0, _ => pure (c, ey, q(Nat.gcd_zero_left).mk_app [ey])
--- | _, 0 => pure (c, ex, q(Nat.gcd_zero_right).mk_app [ex])
--- | 1, _ => pure (c, q((1 : ℕ)), q(Nat.gcd_one_left).mk_app [ey])
--- | _, 1 => pure (c, q((1 : ℕ)), q(Nat.gcd_one_right).mk_app [ex])
--- | _, _ => do
--- let (d, a, b) := Nat.xgcdAux x 1 0 y 0 1
--- if d = x then do
--- let (c, ea) ← c (y / x)
--- let (c, _, p) ← prove_mul_nat c ex ea
--- pure (c, ex, q(nat_gcd_helper_dvd_left).mk_app [ex, ey, ea, p])
--- else
--- if d = y then do
--- let (c, ea) ← c (x / y)
--- let (c, _, p) ← prove_mul_nat c ey ea
--- pure (c, ey, q(nat_gcd_helper_dvd_right).mk_app [ex, ey, ea, p])
--- else do
--- let (c, ed) ← c d
--- let (c, ea) ← c a
--- let (c, eb) ← c b
--- let (c, eu) ← c (x / d)
--- let (c, ev) ← c (y / d)
--- let (c, _, pu) ← prove_mul_nat c ed eu
--- let (c, _, pv) ← prove_mul_nat c ed ev
--- let (c, etx, px) ← prove_mul_nat c ex ea
--- let (c, ety, py) ← prove_mul_nat c ey eb
--- let (c, p) ← if a ≥ 0 then prove_add_nat c ety ed etx else prove_add_nat c etx ed ety
--- let pf : expr := if a ≥ 0 then q(nat_gcd_helper_2) else q(nat_gcd_helper_1)
--- pure (c, ed, pf [ed, ex, ey, ea, eb, eu, ev, etx, ety, pu, pv, px, py, p])
--- #align tactic.norm_num.prove_gcd_nat tactic.norm_num.prove_gcd_nat
-
--- /-- Evaluates the `nat.lcm` function. -/
--- unsafe def prove_lcm_nat (c : instance_cache) (ex ey : expr) :
--- tactic (instance_cache × expr × expr) := do
--- let x ← ex.toNat
--- let y ← ey.toNat
--- match x, y with
--- | 0, _ => pure (c, q((0 : ℕ)), q(Nat.lcm_zero_left).mk_app [ey])
--- | _, 0 => pure (c, q((0 : ℕ)), q(Nat.lcm_zero_right).mk_app [ex])
--- | 1, _ => pure (c, ey, q(Nat.lcm_one_left).mk_app [ey])
--- | _, 1 => pure (c, ex, q(Nat.lcm_one_right).mk_app [ex])
--- | _, _ => do
--- let (c, ed, pd) ← prove_gcd_nat c ex ey
--- let (c, p0) ← prove_pos c ed
--- let (c, en, xy) ← prove_mul_nat c ex ey
--- let d ← ed
--- let (c, em) ← c (x * y / d)
--- let (c, _, dm) ← prove_mul_nat c ed em
--- pure (c, em, q(nat_lcm_helper).mk_app [ex, ey, ed, em, en, pd, p0, xy, dm])
--- #align tactic.norm_num.prove_lcm_nat tactic.norm_num.prove_lcm_nat
-
--- /-- Evaluates the `int.gcd` function. -/
--- unsafe def prove_gcd_int (zc nc : instance_cache) :
--- expr → expr → tactic (instance_cache × instance_cache × expr × expr)
--- | x, y =>
--- match match_neg x with
--- | some x => do
--- let (zc, nc, d, p) ← prove_gcd_int x y
--- pure (zc, nc, d, q(int_gcd_helper_neg_left).mk_app [x, y, d, p])
--- | none =>
--- match match_neg y with
--- | some y => do
--- let (zc, nc, d, p) ← prove_gcd_int x y
--- pure (zc, nc, d, q(int_gcd_helper_neg_right).mk_app [x, y, d, p])
--- | none => do
--- let (zc, nc, nx, px) ← prove_nat_uncast zc nc x
--- let (zc, nc, ny, py) ← prove_nat_uncast zc nc y
--- let (nc, d, p) ← prove_gcd_nat nc nx ny
--- pure (zc, nc, d, q(int_gcd_helper).mk_app [x, y, nx, ny, d, px, py, p])
--- #align tactic.norm_num.prove_gcd_int tactic.norm_num.prove_gcd_int
-
--- /-- Evaluates the `int.lcm` function. -/
--- unsafe def prove_lcm_int (zc nc : instance_cache) :
--- expr → expr → tactic (instance_cache × instance_cache × expr × expr)
--- | x, y =>
--- match match_neg x with
--- | some x => do
--- let (zc, nc, d, p) ← prove_lcm_int x y
--- pure (zc, nc, d, q(int_lcm_helper_neg_left).mk_app [x, y, d, p])
--- | none =>
--- match match_neg y with
--- | some y => do
--- let (zc, nc, d, p) ← prove_lcm_int x y
--- pure (zc, nc, d, q(int_lcm_helper_neg_right).mk_app [x, y, d, p])
--- | none => do
--- let (zc, nc, nx, px) ← prove_nat_uncast zc nc x
--- let (zc, nc, ny, py) ← prove_nat_uncast zc nc y
--- let (nc, d, p) ← prove_lcm_nat nc nx ny
--- pure (zc, nc, d, q(int_lcm_helper).mk_app [x, y, nx, ny, d, px, py, p])
--- #align tactic.norm_num.prove_lcm_int tactic.norm_num.prove_lcm_int
-
--- /-- Evaluates the `nat.coprime` function. -/
--- unsafe def prove_coprime_nat (c : instance_cache) (ex ey : expr) :
--- tactic (instance_cache × Sum expr expr) := do
--- let x ← ex.toNat
--- let y ← ey.toNat
--- match x, y with
--- | 1, _ => pure (c, Sum.inl <| q(Nat.coprime_one_left).mk_app [ey])
--- | _, 1 => pure (c, Sum.inl <| q(Nat.coprime_one_right).mk_app [ex])
--- | 0, 0 => pure (c, Sum.inr q(Nat.not_coprime_zero_zero))
--- | 0, _ => do
--- let c ← mk_instance_cache q(ℕ)
--- let (c, p) ← prove_lt_nat c q(1) ey
--- pure (c, Sum.inr <| q(nat_coprime_helper_zero_left).mk_app [ey, p])
--- | _, 0 => do
--- let c ← mk_instance_cache q(ℕ)
--- let (c, p) ← prove_lt_nat c q(1) ex
--- pure (c, Sum.inr <| q(nat_coprime_helper_zero_right).mk_app [ex, p])
--- | _, _ => do
--- let c ← mk_instance_cache q(ℕ)
--- let (d, a, b) := Nat.xgcdAux x 1 0 y 0 1
--- if d = 1 then do
--- let (c, ea) ← c a
--- let (c, eb) ← c b
--- let (c, etx, px) ← prove_mul_nat c ex ea
--- let (c, ety, py) ← prove_mul_nat c ey eb
--- let (c, p) ← if a ≥ 0 then
--- prove_add_nat c ety q(1) etx else prove_add_nat c etx q(1) ety
--- let pf : expr := if a ≥ 0 then q(nat_coprime_helper_2) else q(nat_coprime_helper_1)
--- pure (c, Sum.inl <| pf [ex, ey, ea, eb, etx, ety, px, py, p])
--- else do
--- let (c, ed) ← c d
--- let (c, eu) ← c (x / d)
--- let (c, ev) ← c (y / d)
--- let (c, _, pu) ← prove_mul_nat c ed eu
--- let (c, _, pv) ← prove_mul_nat c ed ev
--- let (c, p) ← prove_lt_nat c q(1) ed
--- pure (c, Sum.inr <| q(nat_not_coprime_helper).mk_app [ed, ex, ey, eu, ev, pu, pv, p])
--- #align tactic.norm_num.prove_coprime_nat tactic.norm_num.prove_coprime_nat
-
--- /-- Evaluates the `gcd`, `lcm`, and `coprime` functions. -/
--- @[norm_num]
--- unsafe def eval_gcd : expr → tactic (expr × expr)
--- | q(Nat.gcd $(ex) $(ey)) => do
--- let c ← mk_instance_cache q(ℕ)
--- Prod.snd <$> prove_gcd_nat c ex ey
--- | q(Nat.lcm $(ex) $(ey)) => do
--- let c ← mk_instance_cache q(ℕ)
--- Prod.snd <$> prove_lcm_nat c ex ey
--- | q(Nat.Coprime $(ex) $(ey)) => do
--- let c ← mk_instance_cache q(ℕ)
--- prove_coprime_nat c ex ey >>= Sum.elim true_intro false_intro ∘ Prod.snd
--- | q(Int.gcd $(ex) $(ey)) => do
--- let zc ← mk_instance_cache q(ℤ)
--- let nc ← mk_instance_cache q(ℕ)
--- (Prod.snd ∘ Prod.snd) <$> prove_gcd_int zc nc ex ey
--- | q(Int.lcm $(ex) $(ey)) => do
--- let zc ← mk_instance_cache q(ℤ)
--- let nc ← mk_instance_cache q(ℕ)
--- (Prod.snd ∘ Prod.snd) <$> prove_lcm_int zc nc ex ey
--- | _ => failed
--- #align tactic.norm_num.eval_gcd tactic.norm_num.eval_gcd
-
--- end NormNum
-
--- end Tactic
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: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
! This file was ported from Lean 3 source module data.int.gcd
-! leanprover-community/mathlib commit d4f69d96f3532729da8ebb763f4bc26fcf640f06
+! leanprover-community/mathlib commit 47a1a73351de8dd6c8d3d32b569c8e434b03ca47
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -306,13 +306,13 @@ theorem gcd_mul_right (i j k : ℤ) : gcd (i * j) (k * j) = gcd i k * natAbs j :
apply Nat.gcd_mul_right
#align int.gcd_mul_right Int.gcd_mul_right
-theorem gcd_pos_of_non_zero_left {i : ℤ} (j : ℤ) (i_non_zero : i ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_left (natAbs j) (natAbs_pos.2 i_non_zero)
-#align int.gcd_pos_of_non_zero_left Int.gcd_pos_of_non_zero_left
+theorem gcd_pos_of_ne_zero_left {i : ℤ} (j : ℤ) (hi : i ≠ 0) : 0 < gcd i j :=
+ Nat.gcd_pos_of_pos_left _ $ natAbs_pos.2 hi
+#align int.gcd_pos_of_ne_zero_left Int.gcd_pos_of_ne_zero_left
-theorem gcd_pos_of_non_zero_right (i : ℤ) {j : ℤ} (j_non_zero : j ≠ 0) : 0 < gcd i j :=
- Nat.gcd_pos_of_pos_right (natAbs i) (natAbs_pos.2 j_non_zero)
-#align int.gcd_pos_of_non_zero_right Int.gcd_pos_of_non_zero_right
+theorem gcd_pos_of_ne_zero_right (i : ℤ) {j : ℤ} (hj : j ≠ 0) : 0 < gcd i j :=
+ Nat.gcd_pos_of_pos_right _ $ natAbs_pos.2 hj
+#align int.gcd_pos_of_ne_zero_right Int.gcd_pos_of_ne_zero_right
theorem gcd_eq_zero_iff {i j : ℤ} : gcd i j = 0 ↔ i = 0 ∧ j = 0 := by
rw [gcd, Nat.gcd_eq_zero_iff, natAbs_eq_zero, natAbs_eq_zero]
@@ -430,7 +430,7 @@ theorem gcd_least_linear {a b : ℤ} (ha : a ≠ 0) :
IsLeast { n : ℕ | 0 < n ∧ ∃ x y : ℤ, ↑n = a * x + b * y } (a.gcd b) := by
simp_rw [← gcd_dvd_iff]
constructor
- · simpa [and_true_iff, dvd_refl, Set.mem_setOf_eq] using gcd_pos_of_non_zero_left b ha
+ · simpa [and_true_iff, dvd_refl, Set.mem_setOf_eq] using gcd_pos_of_ne_zero_left b ha
· simp only [lowerBounds, and_imp, Set.mem_setOf_eq]
exact fun n hn_pos hn => Nat.le_of_dvd hn_pos hn
#align int.gcd_least_linear Int.gcd_least_linear
This PR is the result of a slight variant on the following "algorithm"
_
and make all uppercase letters into lowercase_
and make all uppercase letters into lowercase(original_lean3_name, OriginalLean4Name)
#align
statement just before the next empty line#align
statement to have been inserted too early)@@ -99,6 +99,7 @@ theorem gcdA_zero_right {s : ℕ} (h : s ≠ 0) : gcdA s 0 = 1 := by
-- Porting note: `simp [xgcdAux_succ]` crashes Lean here
rw [xgcdAux_succ]
rfl
+#align nat.gcd_a_zero_right Nat.gcdA_zero_right
@[simp]
theorem gcdB_zero_right {s : ℕ} (h : s ≠ 0) : gcdB s 0 = 0 := by
Implements a linter for lean 3 declarations containing capital letters (as suggested on Zulip).
Co-authored-by: Mario Carneiro <di.gama@gmail.com>
@@ -141,6 +141,7 @@ theorem xgcd_aux_P {r r'} :
rw [Int.emod_def]; generalize (b / a : ℤ) = k
rw [p, p', mul_sub, sub_add_eq_add_sub, mul_sub, add_mul, mul_comm k t, mul_comm k s,
← mul_assoc, ← mul_assoc, add_comm (x * s * k), ← add_sub_assoc, sub_sub]
+set_option linter.uppercaseLean3 false in
#align nat.xgcd_aux_P Nat.xgcd_aux_P
/-- **Bézout's lemma**: given `x y : ℕ`, `gcd x y = x * a + y * b`, where `a = gcd_a x y` and
This was done semi-automatically with some regular expressions in vim in contrast to the fully automatic https://github.com/leanprover-community/mathlib4/pull/1523.
Co-authored-by: Moritz Firsching <firsching@google.com>
@@ -320,8 +320,8 @@ theorem gcd_pos_iff {i j : ℤ} : 0 < gcd i j ↔ i ≠ 0 ∨ j ≠ 0 :=
pos_iff_ne_zero.trans <| gcd_eq_zero_iff.not.trans not_and_or
#align int.gcd_pos_iff Int.gcd_pos_iff
-theorem gcd_div {i j k : ℤ} (H1 : k ∣ i) (H2 : k ∣ j) : gcd (i / k) (j / k) = gcd i j / natAbs k :=
- by
+theorem gcd_div {i j k : ℤ} (H1 : k ∣ i) (H2 : k ∣ j) :
+ gcd (i / k) (j / k) = gcd i j / natAbs k := by
rw [gcd, natAbs_ediv i k H1, natAbs_ediv j k H2]
exact Nat.gcd_div (natAbs_dvd_natAbs.mpr H1) (natAbs_dvd_natAbs.mpr H2)
#align int.gcd_div Int.gcd_div
@@ -404,8 +404,8 @@ theorem gcd_greatest {a b d : ℤ} (hd_pos : 0 ≤ d) (hda : d ∣ a) (hdb : d
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a c = 1` then `a ∣ b`.
Compare with `IsCoprime.dvd_of_dvd_mul_left` and
`UniqueFactorizationMonoid.dvd_of_dvd_mul_left_of_no_prime_factors` -/
-theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a c = 1) : a ∣ b :=
- by
+theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a c = 1) :
+ a ∣ b := by
have := gcd_eq_gcd_ab a c
simp only [hab, Int.ofNat_zero, Int.ofNat_succ, zero_add] at this
have : b * a * gcdA a c + b * c * gcdB a c = b := by simp [mul_assoc, ← mul_add, ← this]
@@ -96,14 +96,17 @@ theorem gcdB_zero_left {s : ℕ} : gcdB 0 s = 1 := by
theorem gcdA_zero_right {s : ℕ} (h : s ≠ 0) : gcdA s 0 = 1 := by
unfold gcdA xgcd
obtain ⟨s, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h
- simp [xgcdAux_succ]
-#align nat.gcd_a_zero_right Nat.gcdA_zero_right
+ -- Porting note: `simp [xgcdAux_succ]` crashes Lean here
+ rw [xgcdAux_succ]
+ rfl
@[simp]
theorem gcdB_zero_right {s : ℕ} (h : s ≠ 0) : gcdB s 0 = 0 := by
unfold gcdB xgcd
obtain ⟨s, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h
- simp [xgcdAux_succ]
+ -- Porting note: `simp [xgcdAux_succ]` crashes Lean here
+ rw [xgcdAux_succ]
+ rfl
#align nat.gcd_b_zero_right Nat.gcdB_zero_right
@[simp]
@@ -60,8 +60,8 @@ theorem xgcd_zero_left {s t r' s' t'} : xgcdAux 0 s t r' s' t' = (r', s', t') :=
theorem xgcd_aux_rec {r s t r' s' t'} (h : 0 < r) :
xgcdAux r s t r' s' t' = xgcdAux (r' % r) (s' - r' / r * s) (t' - r' / r * t) r s t := by
- cases r <;> [exact absurd h (lt_irrefl _),
- · rfl]
+ obtain ⟨r, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h.ne'
+ rfl
#align nat.xgcd_aux_rec Nat.xgcd_aux_rec
/-- Use the extended GCD algorithm to generate the `a` and `b` values
@@ -95,17 +95,15 @@ theorem gcdB_zero_left {s : ℕ} : gcdB 0 s = 1 := by
@[simp]
theorem gcdA_zero_right {s : ℕ} (h : s ≠ 0) : gcdA s 0 = 1 := by
unfold gcdA xgcd
- induction s
- · exact absurd rfl h
- · simp [xgcdAux_succ]
+ obtain ⟨s, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h
+ simp [xgcdAux_succ]
#align nat.gcd_a_zero_right Nat.gcdA_zero_right
@[simp]
theorem gcdB_zero_right {s : ℕ} (h : s ≠ 0) : gcdB s 0 = 0 := by
unfold gcdB xgcd
- induction s
- · exact absurd rfl h
- · simp [xgcdAux_succ]
+ obtain ⟨s, rfl⟩ := Nat.exists_eq_succ_of_ne_zero h
+ simp [xgcdAux_succ]
#align nat.gcd_b_zero_right Nat.gcdB_zero_right
@[simp]
@@ -132,14 +130,14 @@ private def P : ℕ × ℤ × ℤ → Prop
theorem xgcd_aux_P {r r'} :
∀ {s t s' t'}, P x y (r, s, t) → P x y (r', s', t') → P x y (xgcdAux r s t r' s' t') := by
- induction r, r' using gcd.induction with
- | H0 => simp
- | H1 a b h IH =>
- intro s t s' t' p p'
- rw [xgcd_aux_rec h]; refine' IH _ p; dsimp [P] at *
- rw [Int.emod_def]; generalize (b / a : ℤ) = k
- rw [p, p', mul_sub, sub_add_eq_add_sub, mul_sub, add_mul, mul_comm k t, mul_comm k s,
- ← mul_assoc, ← mul_assoc, add_comm (x * s * k), ← add_sub_assoc, sub_sub]
+ induction r, r' using gcd.induction with
+ | H0 => simp
+ | H1 a b h IH =>
+ intro s t s' t' p p'
+ rw [xgcd_aux_rec h]; refine' IH _ p; dsimp [P] at *
+ rw [Int.emod_def]; generalize (b / a : ℤ) = k
+ rw [p, p', mul_sub, sub_add_eq_add_sub, mul_sub, add_mul, mul_comm k t, mul_comm k s,
+ ← mul_assoc, ← mul_assoc, add_comm (x * s * k), ← add_sub_assoc, sub_sub]
#align nat.xgcd_aux_P Nat.xgcd_aux_P
/-- **Bézout's lemma**: given `x y : ℕ`, `gcd x y = x * a + y * b`, where `a = gcd_a x y` and
@@ -312,15 +310,7 @@ theorem gcd_pos_of_non_zero_right (i : ℤ) {j : ℤ} (j_non_zero : j ≠ 0) : 0
#align int.gcd_pos_of_non_zero_right Int.gcd_pos_of_non_zero_right
theorem gcd_eq_zero_iff {i j : ℤ} : gcd i j = 0 ↔ i = 0 ∧ j = 0 := by
- rw [Int.gcd]
- constructor
- · intro h
- exact
- ⟨natAbs_eq_zero.mp (Nat.eq_zero_of_gcd_eq_zero_left h),
- natAbs_eq_zero.mp (Nat.eq_zero_of_gcd_eq_zero_right h)⟩
- · intro h
- rw [natAbs_eq_zero.mpr h.left, natAbs_eq_zero.mpr h.right]
- apply Nat.gcd_zero_left
+ rw [gcd, Nat.gcd_eq_zero_iff, natAbs_eq_zero, natAbs_eq_zero]
#align int.gcd_eq_zero_iff Int.gcd_eq_zero_iff
theorem gcd_pos_iff {i j : ℤ} : 0 < gcd i j ↔ i ≠ 0 ∨ j ≠ 0 :=
@@ -334,8 +324,7 @@ theorem gcd_div {i j k : ℤ} (H1 : k ∣ i) (H2 : k ∣ j) : gcd (i / k) (j / k
#align int.gcd_div Int.gcd_div
theorem gcd_div_gcd_div_gcd {i j : ℤ} (H : 0 < gcd i j) : gcd (i / gcd i j) (j / gcd i j) = 1 := by
- rw [gcd_div (gcd_dvd_left i j) (gcd_dvd_right i j)]
- rw [natAbs_ofNat, Nat.div_self H]
+ rw [gcd_div (gcd_dvd_left i j) (gcd_dvd_right i j), natAbs_ofNat, Nat.div_self H]
#align int.gcd_div_gcd_div_gcd Int.gcd_div_gcd_div_gcd
theorem gcd_dvd_gcd_of_dvd_left {i k : ℤ} (j : ℤ) (H : i ∣ k) : gcd i j ∣ gcd k j :=
@@ -363,8 +352,7 @@ theorem gcd_dvd_gcd_mul_right_right (i j k : ℤ) : gcd i j ∣ gcd i (j * k) :=
#align int.gcd_dvd_gcd_mul_right_right Int.gcd_dvd_gcd_mul_right_right
theorem gcd_eq_left {i j : ℤ} (H : i ∣ j) : gcd i j = natAbs i :=
- Nat.dvd_antisymm (by unfold gcd; exact Nat.gcd_dvd_left _ _)
- (by unfold gcd; exact Nat.dvd_gcd dvd_rfl (natAbs_dvd_natAbs.mpr H))
+ Nat.dvd_antisymm (Nat.gcd_dvd_left _ _) (Nat.dvd_gcd dvd_rfl (natAbs_dvd_natAbs.mpr H))
#align int.gcd_eq_left Int.gcd_eq_left
theorem gcd_eq_right {i j : ℤ} (H : j ∣ i) : gcd i j = natAbs j := by rw [gcd_comm, gcd_eq_left H]
@@ -389,17 +377,15 @@ theorem exists_gcd_one' {m n : ℤ} (H : 0 < gcd m n) :
theorem pow_dvd_pow_iff {m n : ℤ} {k : ℕ} (k0 : 0 < k) : m ^ k ∣ n ^ k ↔ m ∣ n := by
refine' ⟨fun h => _, fun h => pow_dvd_pow_of_dvd h _⟩
- apply natAbs_dvd_natAbs.mp
- apply (Nat.pow_dvd_pow_iff k0).mp
- rw [← Int.natAbs_pow, ← Int.natAbs_pow]
- exact Int.natAbs_dvd_natAbs.mpr h
+ rwa [← natAbs_dvd_natAbs, ← Nat.pow_dvd_pow_iff k0, ← Int.natAbs_pow, ← Int.natAbs_pow,
+ natAbs_dvd_natAbs]
#align int.pow_dvd_pow_iff Int.pow_dvd_pow_iff
theorem gcd_dvd_iff {a b : ℤ} {n : ℕ} : gcd a b ∣ n ↔ ∃ x y : ℤ, ↑n = a * x + b * y := by
constructor
· intro h
rw [← Nat.mul_div_cancel' h, Int.ofNat_mul, gcd_eq_gcd_ab, add_mul, mul_assoc, mul_assoc]
- refine' ⟨_, _, rfl⟩
+ exact ⟨_, _, rfl⟩
· rintro ⟨x, y, h⟩
rw [← Int.coe_nat_dvd, h]
exact
@@ -507,6 +507,7 @@ theorem lcm_dvd {i j k : ℤ} : i ∣ k → j ∣ k → (lcm i j : ℤ) ∣ k :=
end Int
+@[to_additive gcd_nsmul_eq_zero]
theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m = 1) (hn : x ^ n = 1) :
x ^ m.gcd n = 1 := by
rcases m with (rfl | m); · simp [hn]
@@ -515,16 +516,8 @@ theorem pow_gcd_eq_one {M : Type _} [Monoid M] (x : M) {m n : ℕ} (hm : x ^ m =
rw [← Units.val_one, ← zpow_coe_nat, ← Units.ext_iff] at *
simp only [Nat.gcd_eq_gcd_ab, zpow_add, zpow_mul, hm, hn, one_zpow, one_mul]
#align pow_gcd_eq_one pow_gcd_eq_one
-
-theorem gcd_nsmul_eq_zero {M : Type _} [AddMonoid M] (x : M) {m n : ℕ} (hm : m • x = 0)
- (hn : n • x = 0) : m.gcd n • x = 0 := by
- apply Multiplicative.ofAdd.injective
- rw [ofAdd_nsmul, ofAdd_zero, pow_gcd_eq_one] <;>
- rwa [← ofAdd_nsmul, ← ofAdd_zero, Equiv.apply_eq_iff_eq]
#align gcd_nsmul_eq_zero gcd_nsmul_eq_zero
-attribute [to_additive gcd_nsmul_eq_zero] pow_gcd_eq_one
-
/-! ### GCD prover -/
-- open NormNum
Fix a lot of wrong casing mostly in the docstrings but also sometimes in def/theorem names. E.g. fin 2 --> Fin 2
, add_monoid_hom --> AddMonoidHom
Remove \n
from to_additive
docstrings that were inserted by mathport.
Move files and directories with Gcd
and Smul
to GCD
and SMul
@@ -8,7 +8,7 @@ Authors: Sangwoo Jo (aka Jason), Guy Leroy, Johannes Hölzl, Mario Carneiro
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
-import Mathlib.Data.Nat.Gcd.Basic
+import Mathlib.Data.Nat.GCD.Basic
import Mathlib.Algebra.Ring.Regular
import Mathlib.Data.Int.Dvd.Basic
import Mathlib.Order.Bounds.Basic
@@ -38,7 +38,7 @@ Bézout's lemma, Bezout's lemma
namespace Nat
-/-- Helper function for the extended GCD algorithm (`nat.xgcd`). -/
+/-- Helper function for the extended GCD algorithm (`Nat.xgcd`). -/
def xgcdAux : ℕ → ℤ → ℤ → ℕ → ℤ → ℤ → ℕ × ℤ × ℤ
| 0, _, _, r', s', t' => (r', s', t')
| succ k, s, t, r', s', t' =>
@@ -413,8 +413,8 @@ theorem gcd_greatest {a b d : ℤ} (hd_pos : 0 ≤ d) (hda : d ∣ a) (hdb : d
#align int.gcd_greatest Int.gcd_greatest
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a c = 1` then `a ∣ b`.
-Compare with `is_coprime.dvd_of_dvd_mul_left` and
-`unique_factorization_monoid.dvd_of_dvd_mul_left_of_no_prime_factors` -/
+Compare with `IsCoprime.dvd_of_dvd_mul_left` and
+`UniqueFactorizationMonoid.dvd_of_dvd_mul_left_of_no_prime_factors` -/
theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a c = 1) : a ∣ b :=
by
have := gcd_eq_gcd_ab a c
@@ -425,8 +425,8 @@ theorem dvd_of_dvd_mul_left_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab :
#align int.dvd_of_dvd_mul_left_of_gcd_one Int.dvd_of_dvd_mul_left_of_gcd_one
/-- Euclid's lemma: if `a ∣ b * c` and `gcd a b = 1` then `a ∣ c`.
-Compare with `is_coprime.dvd_of_dvd_mul_right` and
-`unique_factorization_monoid.dvd_of_dvd_mul_right_of_no_prime_factors` -/
+Compare with `IsCoprime.dvd_of_dvd_mul_right` and
+`UniqueFactorizationMonoid.dvd_of_dvd_mul_right_of_no_prime_factors` -/
theorem dvd_of_dvd_mul_right_of_gcd_one {a b c : ℤ} (habc : a ∣ b * c) (hab : gcd a b = 1) :
a ∣ c := by
rw [mul_comm] at habc
All dependencies are ported!