blob: fbcfd2bb33abd482b06bc72705a4d46b2b8dd727 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. or its affiliates. All Rights Reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
module
prelude
public import Init.Grind.Module.Basic
import Init.ByCases
import Init.Data.Int.DivMod.Lemmas
import Init.Data.Int.LemmasAux
import Init.Data.Int.Pow
import Init.Data.Nat.Div.Lemmas
import Init.Data.Nat.Lemmas
import Init.Omega
import Init.RCases
public section
/-!
# Commutative ring typeclasses for internal use in `grind`.
The `Lean.Grind.CommRing` class will be used to convert expressions into the internal representation via polynomials,
with coefficients expressed via `OfNat` and `Neg`.
The `IsCharP α p` typeclass expresses that the ring has characteristic `p`,
i.e. that a coefficient `OfNat.ofNat x : α` is zero if and only if `x % p = 0` (in `Nat`).
See
```
theorem ofNat_ext_iff {x y : Nat} : OfNat.ofNat (α := α) x = OfNat.ofNat (α := α) y ↔ x % p = y % p
theorem ofNat_emod (x : Nat) : OfNat.ofNat (α := α) (x % p) = OfNat.ofNat x
theorem ofNat_eq_iff_of_lt {x y : Nat} (h₁ : x < p) (h₂ : y < p) :
OfNat.ofNat (α := α) x = OfNat.ofNat (α := α) y ↔ x = y
```
-/
namespace Lean.Grind
/--
A semiring, i.e. a type equipped with addition, multiplication, and a map from the natural numbers,
satisfying appropriate compatibilities.
Use `Ring` instead if the type also has negation,
`CommSemiring` if the multiplication is commutative,
or `CommRing` if the type has negation and multiplication is commutative.
-/
class Semiring (α : Type u) extends Add α, Mul α where
/--
In every semiring there is a canonical map from the natural numbers to the semiring,
providing the values of `0` and `1`. Note that this function need not be injective.
-/
[natCast : NatCast α]
/--
Natural number numerals in the semiring.
The field `ofNat_eq_natCast` ensures that these are (propositionally) equal to the values of `natCast`.
-/
[ofNat : ∀ n, OfNat α n]
/-- Scalar multiplication by natural numbers. -/
[nsmul : SMul Nat α]
/-- Exponentiation by a natural number. -/
[npow : HPow α Nat α]
/-- Zero is the right identity for addition. -/
add_zero : ∀ a : α, a + 0 = a
/-- Addition is commutative. -/
add_comm : ∀ a b : α, a + b = b + a
/-- Addition is associative. -/
add_assoc : ∀ a b c : α, a + b + c = a + (b + c)
/-- Multiplication is associative. -/
mul_assoc : ∀ a b c : α, a * b * c = a * (b * c)
/-- One is the right identity for multiplication. -/
mul_one : ∀ a : α, a * 1 = a
/-- One is the left identity for multiplication. -/
one_mul : ∀ a : α, 1 * a = a
/-- Left distributivity of multiplication over addition. -/
left_distrib : ∀ a b c : α, a * (b + c) = a * b + a * c
/-- Right distributivity of multiplication over addition. -/
right_distrib : ∀ a b c : α, (a + b) * c = a * c + b * c
/-- Zero is right absorbing for multiplication. -/
zero_mul : ∀ a : α, 0 * a = 0
/-- Zero is left absorbing for multiplication. -/
mul_zero : ∀ a : α, a * 0 = 0
/-- The zeroth power of any element is one. -/
pow_zero : ∀ a : α, a ^ 0 = 1
/-- The successor power law for exponentiation. -/
pow_succ : ∀ a : α, ∀ n : Nat, a ^ (n + 1) = (a ^ n) * a
/-- Numerals are consistently defined with respect to addition. -/
ofNat_succ : ∀ a : Nat, OfNat.ofNat (α := α) (a + 1) = OfNat.ofNat a + 1 := by intros; rfl
/-- Numerals are consistently defined with respect to the canonical map from natural numbers. -/
ofNat_eq_natCast : ∀ n : Nat, OfNat.ofNat (α := α) n = Nat.cast n := by intros; rfl
/--
Multiplying by a numeral is consistently defined with respect to the canonical map from natural
numbers.
-/
nsmul_eq_natCast_mul : ∀ n : Nat, ∀ a : α, n • a = Nat.cast n * a := by intros; rfl
attribute [instance_reducible] Semiring.npow Semiring.ofNat Semiring.natCast
/--
A ring, i.e. a type equipped with addition, negation, multiplication, and a map from the integers,
satisfying appropriate compatibilities.
Use `CommRing` if the multiplication is commutative.
-/
class Ring (α : Type u) extends Semiring α, Neg α, Sub α where
/-- In every ring there is a canonical map from the integers to the ring. -/
[intCast : IntCast α]
/-- Scalar multiplication by integers. -/
[zsmul : SMul Int α]
/-- Negation is the left inverse of addition. -/
neg_add_cancel : ∀ a : α, -a + a = 0
/-- Subtraction is addition of the negative. -/
sub_eq_add_neg : ∀ a b : α, a - b = a + -b
/-- Scalar multiplication by the negation of an integer is the negation of scalar multiplication by that integer. -/
neg_zsmul : ∀ (i : Int) (a : α), (-i : Int) • a = -(i • a)
/-- Scalar multiplication by natural numbers is consistent with scalar multiplication by integers. -/
zsmul_natCast_eq_nsmul : ∀ n : Nat, ∀ a : α, (n : Int) • a = n • a := by intros; rfl
/-- The canonical map from the integers is consistent with the canonical map from the natural numbers. -/
intCast_ofNat : ∀ n : Nat, Int.cast (OfNat.ofNat (α := Int) n) = OfNat.ofNat (α := α) n := by intros; rfl
/-- The canonical map from the integers is consistent with negation. -/
intCast_neg : ∀ i : Int, Int.cast (R := α) (-i) = -Int.cast i := by intros; rfl
attribute [instance_reducible] Ring.intCast Ring.zsmul
/--
A commutative semiring, i.e. a semiring with commutative multiplication.
Use `CommRing` if the type has negation.
-/
class CommSemiring (α : Type u) extends Semiring α where
/-- Multiplication is commutative. -/
mul_comm : ∀ a b : α, a * b = b * a
one_mul := by intro a; rw [mul_comm, mul_one]
mul_zero := by intro a; rw [mul_comm, zero_mul]
right_distrib := by intro a b c; rw [mul_comm, left_distrib, mul_comm c, mul_comm c]
/--
A commutative ring, i.e. a ring with commutative multiplication.
-/
class CommRing (α : Type u) extends Ring α, CommSemiring α
-- We reduce the priority of these parent instances,
-- so that in downstream libraries with their own `CommRing` class,
-- the path `CommRing -> Add` is found before `CommRing -> Lean.Grind.CommRing -> Add`.
-- (And similarly for the other parents.)
attribute [instance 100] Semiring.toAdd Semiring.toMul Semiring.npow Ring.toNeg Ring.toSub
-- This is a low-priority instance, to avoid conflicts with existing `OfNat`, `NatCast`, and `IntCast` instances.
attribute [instance 100] Semiring.ofNat
attribute [local instance] Semiring.natCast Ring.intCast
-- Verify that the diamond from `CommRing` to `Semiring` via either `CommSemiring` or `Ring` is defeq.
example [CommRing α] : (CommSemiring.toSemiring : Semiring α) = (Ring.toSemiring : Semiring α) := rfl
namespace Semiring
open NatModule
variable {α : Type u} [Semiring α]
theorem natCast_eq_ofNat (n : Nat) : NatCast.natCast n = OfNat.ofNat (α := α) n := by
rw [ofNat_eq_natCast]
theorem natCast_zero : ((0 : Nat) : α) = 0 := by
rw [← ofNat_eq_natCast 0]
theorem natCast_one : ((1 : Nat) : α) = 1 := (ofNat_eq_natCast 1).symm
theorem ofNat_add (a b : Nat) : OfNat.ofNat (α := α) (a + b) = OfNat.ofNat a + OfNat.ofNat b := by
induction b with
| zero => rw [Nat.add_zero, add_zero]
| succ b ih => rw [Nat.add_succ, ofNat_succ, ih, ofNat_succ b, add_assoc]
instance toNatModule [I : Semiring α] : NatModule α :=
{ I with
zero_nsmul a := by rw [nsmul_eq_natCast_mul, ← ofNat_eq_natCast, zero_mul]
add_one_nsmul n a := by rw [nsmul_eq_natCast_mul, ← ofNat_eq_natCast, ofNat_add, right_distrib,
ofNat_eq_natCast, ← nsmul_eq_natCast_mul, ofNat_eq_natCast, natCast_one, one_mul] }
theorem natCast_add (a b : Nat) : ((a + b : Nat) : α) = ((a : α) + (b : α)) := by
rw [← ofNat_eq_natCast, ← ofNat_eq_natCast, ofNat_add, ofNat_eq_natCast, ofNat_eq_natCast]
theorem natCast_succ (n : Nat) : ((n + 1 : Nat) : α) = ((n : α) + 1) := by
rw [natCast_add, natCast_one]
theorem ofNat_mul (a b : Nat) : OfNat.ofNat (α := α) (a * b) = OfNat.ofNat a * OfNat.ofNat b := by
induction b with
| zero => simp [Nat.mul_zero, mul_zero]
| succ a ih => rw [Nat.mul_succ, ofNat_add, ih, ofNat_add, left_distrib, mul_one]
theorem natCast_mul (a b : Nat) : ((a * b : Nat) : α) = ((a : α) * (b : α)) := by
rw [← ofNat_eq_natCast, ofNat_mul, ofNat_eq_natCast, ofNat_eq_natCast]
theorem natCast_mul_comm (a : Nat) (b : α) : a * b = b * a := by
induction a
next => simp [Semiring.natCast_zero, mul_zero, zero_mul]
next ih =>
rw [Semiring.natCast_succ, Semiring.left_distrib, Semiring.right_distrib, ih]
simp [Semiring.mul_one, Semiring.one_mul]
theorem natCast_mul_left_comm (a : α) (b : Nat) (c : α) : a * (b * c) = b * (a * c) := by
induction b
next => simp [Semiring.natCast_zero, mul_zero, zero_mul]
next ih =>
rw [Semiring.natCast_succ, Semiring.right_distrib, Semiring.left_distrib, ih,
Semiring.right_distrib, Semiring.one_mul, Semiring.one_mul]
theorem pow_one (a : α) : a ^ 1 = a := by
rw [pow_succ, pow_zero, one_mul]
theorem pow_two (a : α) : a ^ 2 = a * a := by
rw [pow_succ, pow_one]
theorem pow_add (a : α) (k₁ k₂ : Nat) : a ^ (k₁ + k₂) = a^k₁ * a^k₂ := by
induction k₂
next => simp [pow_zero, mul_one]
next k₂ ih => rw [Nat.add_succ, pow_succ, pow_succ, ih, mul_assoc]
theorem pow_add_congr (a r : α) (k k₁ k₂ : Nat) : k = k₁ + k₂ → a^k₁ * a^k₂ = r → a ^ k = r := by
intros; subst k r; rw [pow_add]
theorem one_pow (n : Nat) : (1 : α) ^ n = 1 := by
induction n
next => simp [pow_zero]
next => simp [pow_succ, *, mul_one]
theorem natCast_pow (x : Nat) (k : Nat) : ((x ^ k : Nat) : α) = (x : α) ^ k := by
induction k
next => simp [pow_zero, Nat.pow_zero, natCast_one]
next k ih => simp [pow_succ, Nat.pow_succ, natCast_mul, *]
theorem nsmul_eq_ofNat_mul {α} [Semiring α] {k : Nat} {a : α} : k • a = OfNat.ofNat k * a := by
simp [ofNat_eq_natCast, nsmul_eq_natCast_mul]
end Semiring
namespace Ring
open AddCommMonoid AddCommGroup NatModule IntModule
open Semiring hiding add_assoc add_comm
variable {α : Type u} [Ring α]
theorem intCast_natCast (n : Nat) : ((n : Int) : α) = (n : α) := by
erw [intCast_ofNat]
rw [ofNat_eq_natCast]
instance toAddCommGroup [I : Ring α] : AddCommGroup α :=
{ I with }
theorem intCast_zero : ((0 : Int) : α) = 0 := by
rw [intCast_ofNat 0]
theorem intCast_one : ((1 : Int) : α) = 1 := intCast_ofNat 1
theorem intCast_neg_one : ((-1 : Int) : α) = -1 := by rw [intCast_neg, intCast_ofNat]
theorem intCast_natCast_add_one (n : Nat) : ((n + 1 : Int) : α) = (n : α) + 1 := by
rw [← Int.natCast_add_one, intCast_natCast, natCast_add, ofNat_eq_natCast]
theorem intCast_negSucc (n : Nat) : ((-(n + 1) : Int) : α) = -((n : α) + 1) := by
rw [intCast_neg, ← Int.natCast_add_one, intCast_natCast, ofNat_eq_natCast, natCast_add]
theorem intCast_nat_add {x y : Nat} : ((x + y : Int) : α) = ((x : α) + (y : α)) := by
rw [Int.ofNat_add_ofNat, intCast_natCast, natCast_add]
theorem intCast_eq_ofNat_of_nonneg (x : Int) (h : Int.ble' 0 x) : IntCast.intCast (R := α) x = OfNat.ofNat (α := α) x.toNat := by
show Int.cast x = _
rw [Int.ble'_eq_true] at h
have := Int.toNat_of_nonneg h
conv => lhs; rw [← this, Ring.intCast_natCast]
rw [Semiring.ofNat_eq_natCast]
theorem intCast_eq_ofNat_of_nonpos (x : Int) (h : Int.ble' x 0) : IntCast.intCast (R := α) x = - OfNat.ofNat (α := α) x.natAbs := by
show Int.cast x = _
rw [Int.ble'_eq_true] at h
have := Int.eq_neg_natAbs_of_nonpos h
conv => lhs; rw [this]
rw [Ring.intCast_neg, Semiring.ofNat_eq_natCast, Ring.intCast_natCast]
theorem intCast_nat_sub {x y : Nat} (h : x ≥ y) : (((x - y : Nat) : Int) : α) = ((x : α) - (y : α)) := by
induction x with
| zero =>
have : y = 0 := by omega
simp [this, intCast_zero, natCast_zero, sub_eq_add_neg, zero_add, neg_zero]
| succ x ih =>
by_cases h : x + 1 = y
· simp [h, intCast_zero, sub_self]
· have : ((x + 1 - y : Nat) : Int) = (x - y : Nat) + 1 := by omega
rw [this, intCast_natCast_add_one]
specialize ih (by omega)
rw [intCast_natCast] at ih
rw [ih, natCast_succ, sub_eq_add_neg, sub_eq_add_neg, add_assoc,
AddCommMonoid.add_comm _ 1, ← add_assoc]
theorem intCast_add (x y : Int) : ((x + y : Int) : α) = ((x : α) + (y : α)) :=
match x, y with
| (x : Nat), (y : Nat) => by
rw [intCast_nat_add, intCast_natCast, intCast_natCast]
| (x : Nat), (-(y + 1 : Nat)) => by
by_cases h : x ≥ y + 1
· have : (x + -(y+1 : Nat) : Int) = ((x - (y + 1) : Nat) : Int) := by omega
rw [this, intCast_neg, intCast_nat_sub h, intCast_natCast, intCast_natCast, sub_eq_add_neg]
· have : (x + -(y+1 : Nat) : Int) = (-(y + 1 - x : Nat) : Int) := by omega
rw [this, intCast_neg, intCast_nat_sub (by omega), intCast_natCast, intCast_neg, intCast_natCast,
neg_sub, sub_eq_add_neg]
| (-(x + 1 : Nat)), (y : Nat) => by
by_cases h : y ≥ x+ 1
· have : (-(x+1 : Nat) + y : Int) = ((y - (x + 1) : Nat) : Int) := by omega
rw [this, intCast_neg, intCast_nat_sub h, intCast_natCast, intCast_natCast, sub_eq_add_neg, add_comm]
· have : (-(x+1 : Nat) + y : Int) = (-(x + 1 - y : Nat) : Int) := by omega
rw [this, intCast_neg, intCast_nat_sub (by omega), intCast_natCast, intCast_neg, intCast_natCast,
neg_sub, sub_eq_add_neg, add_comm]
| (-(x + 1 : Nat)), (-(y + 1 : Nat)) => by
rw [← Int.neg_add, intCast_neg, intCast_nat_add, neg_add, intCast_neg, intCast_neg, intCast_natCast, intCast_natCast]
theorem intCast_sub (x y : Int) : ((x - y : Int) : α) = ((x : α) - (y : α)) := by
rw [Int.sub_eq_add_neg, intCast_add, intCast_neg, sub_eq_add_neg]
theorem ofNat_sub {x y : Nat} (h : y ≤ x) : OfNat.ofNat (α := α) (x - y) = OfNat.ofNat x - OfNat.ofNat y := by
rw [ofNat_eq_natCast, ← intCast_natCast, Int.ofNat_sub h]
rw [intCast_sub]
rw [intCast_natCast, intCast_natCast, ofNat_eq_natCast, ofNat_eq_natCast]
theorem neg_ofNat_sub {x y : Nat} (h : y ≤ x) : -OfNat.ofNat (α := α) (x - y) = OfNat.ofNat y - OfNat.ofNat x := by
rw [neg_eq_iff, ofNat_sub h, neg_sub]
theorem neg_eq_neg_one_mul (a : α) : -a = (-1) * a := by
rw [← add_left_inj a, neg_add_cancel]
conv => rhs; arg 2; rw [← one_mul a]
rw [← right_distrib, ← intCast_neg_one, ← intCast_one (α := α)]
simp [← intCast_add, intCast_zero, zero_mul]
theorem neg_eq_mul_neg_one (a : α) : -a = a * (-1) := by
rw [← add_left_inj a, neg_add_cancel]
conv => rhs; arg 2; rw [← mul_one a]
rw [← left_distrib, ← intCast_neg_one, ← intCast_one (α := α)]
simp [← intCast_add, intCast_zero, mul_zero]
theorem neg_mul (a b : α) : (-a) * b = -(a * b) := by
rw [neg_eq_neg_one_mul a, neg_eq_neg_one_mul (a * b), mul_assoc]
theorem mul_neg (a b : α) : a * (-b) = -(a * b) := by
rw [neg_eq_mul_neg_one b, neg_eq_mul_neg_one (a * b), mul_assoc]
attribute [local instance] Ring.zsmul in
theorem zsmul_eq_intCast_mul {k : Int} {a : α} : (k • a : α) = (k : α) * a := by
match k with
| (k : Nat) =>
rw [intCast_natCast, zsmul_natCast_eq_nsmul, nsmul_eq_natCast_mul]
| -(k + 1 : Nat) =>
rw [intCast_neg, neg_mul, neg_zsmul, intCast_natCast, zsmul_natCast_eq_nsmul, nsmul_eq_natCast_mul]
instance toIntModule [I : Ring α] : IntModule α :=
{ I, Semiring.toNatModule (α := α) with
zero_zsmul a := by rw [← Int.natCast_zero, zsmul_natCast_eq_nsmul, zero_nsmul]
one_zsmul a := by rw [← Int.natCast_one, zsmul_natCast_eq_nsmul, one_nsmul]
add_zsmul n m a := by rw [zsmul_eq_intCast_mul, intCast_add, right_distrib, zsmul_eq_intCast_mul, zsmul_eq_intCast_mul] }
private theorem intCast_mul_aux (x y : Nat) : ((x * y : Int) : α) = ((x : α) * (y : α)) := by
rw [Int.ofNat_mul_ofNat, intCast_natCast, natCast_mul]
theorem intCast_mul (x y : Int) : ((x * y : Int) : α) = ((x : α) * (y : α)) :=
match x, y with
| (x : Nat), (y : Nat) => by
rw [intCast_mul_aux, intCast_natCast, intCast_natCast]
| (x : Nat), (-(y + 1 : Nat)) => by
rw [Int.mul_neg, intCast_neg, intCast_mul_aux, intCast_neg, mul_neg, intCast_natCast, intCast_natCast]
| (-(x + 1 : Nat)), (y : Nat) => by
rw [Int.neg_mul, intCast_neg, intCast_mul_aux, intCast_neg, neg_mul, intCast_natCast, intCast_natCast]
| (-(x + 1 : Nat)), (-(y + 1 : Nat)) => by
rw [Int.neg_mul_neg, intCast_neg, intCast_neg, neg_mul, mul_neg, neg_neg, intCast_mul_aux,
intCast_natCast, intCast_natCast]
theorem intCast_mul_comm (a : Int) (b : α) : a * b = b * a := by
have : a = a.natAbs ∨ a = -a.natAbs := by exact Int.natAbs_eq a
cases this
next h => rw [h, Ring.intCast_natCast, Semiring.natCast_mul_comm]
next h => rw [h, Ring.intCast_neg, Ring.intCast_natCast, Ring.mul_neg, Ring.neg_mul, Semiring.natCast_mul_comm]
theorem intCast_mul_left_comm (a : α) (b : Int) (c : α) : a * (b * c) = b * (a * c) := by
have : b = b.natAbs ∨ b = -b.natAbs := by exact Int.natAbs_eq b
cases this
next h => rw [h, Ring.intCast_natCast, Semiring.natCast_mul_left_comm]
next h => rw [h, Ring.intCast_neg, Ring.intCast_natCast, Ring.neg_mul, Ring.neg_mul, Ring.mul_neg, Semiring.natCast_mul_left_comm]
theorem intCast_pow (x : Int) (k : Nat) : ((x ^ k : Int) : α) = (x : α) ^ k := by
induction k
next => simp [pow_zero, Int.pow_zero, intCast_one]
next k ih => simp [pow_succ, Int.pow_succ, intCast_mul, *]
-- Verify that the diamond from `Ring` to `NatModule` via either `Semiring` or `IntModule` is defeq.
example [Ring R] : (Semiring.toNatModule : NatModule R) = IntModule.toNatModule (M := R) := rfl
end Ring
namespace CommSemiring
open Semiring
variable {α : Type u} [CommSemiring α]
theorem mul_left_comm (a b c : α) : a * (b * c) = b * (a * c) := by
rw [← mul_assoc, ← mul_assoc, mul_comm a]
theorem mul_pow (a b : α) (n : Nat) : (a*b)^n = a^n * b^n := by
induction n
next => simp [pow_zero, mul_one]
next n ih => simp [pow_succ, ih, mul_comm, mul_assoc, mul_left_comm]
end CommSemiring
open Semiring hiding add_comm add_assoc add_zero
open Ring hiding neg_add_cancel
open CommSemiring CommRing
/--
A ring `α` has characteristic `p` if `OfNat.ofNat x = 0` iff `x % p = 0`.
Note that for `p = 0`, we have `x % p = x`, so this says that `OfNat.ofNat` is injective from `Nat` to `α`.
In the case of a semiring, we take the stronger condition that
`OfNat.ofNat x = OfNat.ofNat y` iff `x % p = y % p`.
-/
class IsCharP (α : Type u) [Semiring α] (p : outParam Nat) where
/-- Two numerals in a semiring are equal iff they are congruent module `p` in the natural numbers. -/
ofNat_ext_iff (p) : ∀ {x y : Nat}, OfNat.ofNat (α := α) x = OfNat.ofNat (α := α) y ↔ x % p = y % p
namespace IsCharP
section
variable (p) [Semiring α] [IsCharP α p]
theorem ofNat_eq_zero_iff (x : Nat) :
OfNat.ofNat (α := α) x = 0 ↔ x % p = 0 := by
rw [ofNat_ext_iff p]
simp
theorem ofNat_ext {x y : Nat} (h : x % p = y % p) : OfNat.ofNat (α := α) x = OfNat.ofNat (α := α) y := (ofNat_ext_iff p).mpr h
theorem ofNat_eq_zero_iff_of_lt {x : Nat} (h : x < p) : OfNat.ofNat (α := α) x = 0 ↔ x = 0 := by
rw [ofNat_eq_zero_iff p, Nat.mod_eq_of_lt h]
theorem ofNat_eq_iff_of_lt {x y : Nat} (h₁ : x < p) (h₂ : y < p) :
OfNat.ofNat (α := α) x = OfNat.ofNat (α := α) y ↔ x = y := by
rw [ofNat_ext_iff p, Nat.mod_eq_of_lt h₁, Nat.mod_eq_of_lt h₂]
end
section Semiring
variable (p)
variable [Semiring α] [IsCharP α p]
theorem natCast_eq_zero_iff (x : Nat) : (x : α) = 0 ↔ x % p = 0 := by
rw [← ofNat_eq_natCast]
exact ofNat_eq_zero_iff p x
theorem natCast_ext {x y : Nat} (h : x % p = y % p) : (x : α) = (y : α) := by
rw [← ofNat_eq_natCast, ← ofNat_eq_natCast]
exact ofNat_ext p h
theorem natCast_ext_iff {x y : Nat} : (x : α) = (y : α) ↔ x % p = y % p := by
rw [← ofNat_eq_natCast, ← ofNat_eq_natCast]
exact ofNat_ext_iff p
theorem natCast_emod (x : Nat) : ((x % p : Nat) : α) = (x : α) := by
rw [natCast_ext_iff p, Nat.mod_mod]
theorem ofNat_emod (x : Nat) : OfNat.ofNat (α := α) (x % p) = OfNat.ofNat x := by
rw [ofNat_eq_natCast, ofNat_eq_natCast]
exact natCast_emod p x
theorem natCast_eq_zero_iff_of_lt {x : Nat} (h : x < p) : (x : α) = 0 ↔ x = 0 := by
rw [natCast_eq_zero_iff p, Nat.mod_eq_of_lt h]
theorem natCast_eq_iff_of_lt {x y : Nat} (h₁ : x < p) (h₂ : y < p) :
(x : α) = (y : α) ↔ x = y := by
rw [natCast_ext_iff p, Nat.mod_eq_of_lt h₁, Nat.mod_eq_of_lt h₂]
end Semiring
section Ring
open AddCommMonoid AddCommGroup
variable (p) {α : Type u} [Ring α] [IsCharP α p]
private theorem mk'_aux {x y : Nat} (p : Nat) (h : y ≤ x) :
(x - y) % p = 0 ↔ ∃ k₁ k₂, x + k₁ * p = y + k₂ * p := by
rw [Nat.mod_eq_iff]
by_cases h : p = 0
· simp [h]
omega
· have h' : 0 < p := by omega
simp [h, h']
constructor
· rintro ⟨k, h⟩
refine ⟨0, k, ?_⟩
simp [Nat.mul_comm]
omega
· rintro ⟨k₁, k₂, h⟩
have : k₁ * p ≤ k₂ * p := by omega
have : k₁ ≤ k₂ := Nat.le_of_mul_le_mul_right this h'
refine ⟨k₂ - k₁, ?_⟩
simp [Nat.mul_sub, Nat.mul_comm p k₁, Nat.mul_comm p k₂]
omega
/-- Alternative constructor when `α` is a `Ring`. -/
def mk' (p : Nat) (α : Type u) [Ring α]
(ofNat_eq_zero_iff : ∀ (x : Nat), OfNat.ofNat (α := α) x = 0 ↔ x % p = 0) : IsCharP α p where
ofNat_ext_iff {x y} := by
rw [← sub_eq_zero_iff]
rw [Nat.mod_eq_mod_iff]
by_cases h : y ≤ x
· have : OfNat.ofNat (α := α) x - OfNat.ofNat y = OfNat.ofNat (x - y) := by rw [ofNat_sub h]
rw [this, ofNat_eq_zero_iff]
apply mk'_aux _ h
· have : OfNat.ofNat (α := α) x - OfNat.ofNat (α := α) y = - OfNat.ofNat (y - x) := by rw [neg_ofNat_sub (by omega)]
rw [this, neg_eq_zero, ofNat_eq_zero_iff]
rw [mk'_aux _ (by omega)]
rw [exists_comm]
apply exists_congr
intro k₁
apply exists_congr
intro k₂
simp [eq_comm]
theorem intCast_eq_zero_iff (x : Int) : (x : α) = 0 ↔ x % p = 0 :=
match x with
| (x : Nat) => by
have := ofNat_eq_zero_iff (α := α) p (x := x)
rw [Int.ofNat_mod_ofNat, intCast_natCast, ← ofNat_eq_natCast]
norm_cast
| -(x + 1 : Nat) => by
rw [Int.neg_emod, Int.ofNat_mod_ofNat, intCast_neg, intCast_natCast, neg_eq_zero]
have := ofNat_eq_zero_iff (α := α) p (x := x + 1)
rw [ofNat_eq_natCast] at this
rw [this]
simp only [Int.ofNat_dvd]
simp only [← Nat.dvd_iff_mod_eq_zero, Int.natAbs_natCast,
ite_eq_left_iff]
by_cases h : p ∣ x + 1
· simp [h]
· simp only [h, not_false_eq_true,
forall_const, false_iff, ne_eq]
by_cases w : p = 0
· simp [w]
omega
· have : ((x + 1) % p) < p := Nat.mod_lt _ (by omega)
omega
theorem intCast_ext_iff {x y : Int} : (x : α) = (y : α) ↔ x % p = y % p := by
constructor
· intro h
replace h : ((x - y : Int) : α) = 0 := by rw [intCast_sub, h, sub_self]
exact Int.emod_eq_emod_iff_emod_sub_eq_zero.mpr ((intCast_eq_zero_iff p _).mp h)
· intro h
have : ((x - y : Int) : α) = 0 :=
(intCast_eq_zero_iff p _).mpr (by rw [Int.sub_emod, h, Int.sub_self, Int.zero_emod])
replace this := congrArg (· + (y : α)) this
simpa [intCast_sub, zero_add, AddCommGroup.sub_eq_add_neg, add_assoc,
neg_add_cancel, add_zero] using this
theorem intCast_emod (x : Int) : ((x % p : Int) : α) = (x : α) := by
rw [intCast_ext_iff p, Int.emod_emod]
end Ring
end IsCharP
open AddCommGroup
theorem no_int_zero_divisors {α : Type u} [IntModule α] [NoNatZeroDivisors α] {k : Int} {a : α}
: k ≠ 0 → k • a = 0 → a = 0 := by
match k with
| (k : Nat) =>
simp only [ne_eq, Int.natCast_eq_zero]
intro h₁ h₂
replace h₁ : k ≠ 0 := by intro h; simp [h] at h₁
rw [IntModule.zsmul_natCast_eq_nsmul] at h₂
exact NoNatZeroDivisors.eq_zero_of_mul_eq_zero h₁ h₂
| -(k+1 : Nat) =>
rw [IntModule.neg_zsmul]
intro _ h
replace h := congrArg (-·) h
dsimp only at h
rw [neg_neg, neg_zero] at h
rw [IntModule.zsmul_natCast_eq_nsmul] at h
exact NoNatZeroDivisors.eq_zero_of_mul_eq_zero (Nat.succ_ne_zero _) h
end Lean.Grind