Евклидово кольцо

Формальное определение

Евклидово кольцо — это кольцо НОД, которое также поддерживает евклидово деление (например, поэтапное или целочисленное деление).

Формально евклидовы кольца определяют евклидову функцию f

такую, что для любого x и y в A, если y ненулевое, то существуют q и r (частное и остаток) такие, что a = b*q + r и r = 0 или f(r) < f(b). Для целых чисел обычно f - это функция абсолютного значения.

EuclideanRing[A]

добавляет следующие операции:

quot (/~, a /~ b): частное (евклидово деление)
mod (%, a % b): остаток

В целых числах евклидово частное и остаток соответствуют делению с остатком; однако знак результата является вопросом соглашения. Для рациональных чисел (или с плавающей запятой) a /~ b = a / b

и a % b = 0 по определению.

Помимо законов кольца НОД:

Замыкание сложения (closure): для \(\forall x, y \in R\) выполняется \(x + y \in R\).
Ассоциативность сложения (associativity): для \(\forall x, y, z \in R\) выполняется \((x + y) + z = x + (y + z)\).
Существование нулевого элемента: существует \(\exists 0 \in R\) такой, что для \(\forall x \in R\) выполняется \(0 + x = x + 0 = x\)
Обратимость сложения: для \(\forall x \in R\) существует \((-x)\) такой, что \(x + (-x) = (-x) + x = 0\)
Коммутативность сложения (commutative): для \(\forall x, y \in R\) выполняется \(x + y = y + x\).
Замыкание умножения (closure): для \(\forall x, y \in R\) выполняется \(x * y \in R\).
Ассоциативность умножения (associativity): для \(\forall x, y, z \in R\) выполняется \((x * y) * z = x * (y * z)\).
Существование единичного элемента: \(\exists 1 \in R \quad \forall x \in R \quad x * 1 = 1 * x = x\)
Коммутативность умножения: для \(\forall x, y \in R\) выполняется \(x * y = y * x\).
Дистрибутивность (distributivus, распределительный закон): для \(\forall x, y, z \in R\) выполняется \(x * (y + z) = x * y + x * z\) и \((x + y) * z = x * z + y * z\).
для \(\forall x, y \in R\) выполняется \(gcd(x, y) * lcm(x, y) = x * y\).
Ассоциативность НОД: для \(\forall x, y, z \in R\) выполняется \(gcd(gcd(x, y), z) = gcd(x, gcd(y, z))\).
Коммутативность НОД: для \(\forall x, y \in R\) выполняется \(gcd(x, y) = gcd(y, x)\).
Ассоциативность НОК: для \(\forall x, y, z \in R\) выполняется \(lcm(lcm(x, y), z) = lcm(x, lcm(y, z))\).
Коммутативность НОК: для \(\forall x, y \in R\) выполняется \(lcm(x, y) = lcm(y, x)\).

должен соблюдаться закон:

b * (a /~ b) + (a % b) = a

Определение в виде кода на Scala

trait EuclideanRing[A] extends GCDRing[A]:
  def quot(x: A, y: A): A

  def mod(x: A, y: A): A

Законы в виде кода на Scala

trait EuclideanRingLaw extends GCDRingLaw:
  def checkEuclideanRingLaw[A: EuclideanRing](
      x: A,
      y: A,
      z: A
  ): ValidatedNel[String, Unit] =
    checkGCDRingLaw(x, y, z) combine
      check(
        EuclideanRing[A].combine(
          EuclideanRing[A].times(
            y,
            EuclideanRing[A].quot(x, y)
          ),
          EuclideanRing[A].mod(x, y)
        ) == x,
        "b * (a /~ b) + (a % b) = a"
      )

Примеры

Числа относительно сложения с 0 и умножения с 1

(Z, +, *)

given EuclideanRing[Int] with
  val empty: Int                   = 0
  val one: Int                     = 1
  def combine(x: Int, y: Int): Int = x + y
  def times(x: Int, y: Int): Int   = x * y
  def gcd(x: Int, y: Int): Int = if y == 0 then x else gcd(y, x % y)
  def lcm(x: Int, y: Int): Int                 = times(x, y) / gcd(x, y)
  def quot(x: Int, y: Int): Int                = x / y
  def mod(x: Int, y: Int): Int                 = x % y
  extension (a: Int) override def inverse: Int = -a

Реализация

Реализация в Spire

import spire.algebra.EuclideanRing
import spire.std.int.*

EuclideanRing.plus(15, 10)
// val res0: Int = 25
EuclideanRing.times(15, 10)
// val res1: Int = 150
EuclideanRing.pow(15, 2)
// val res2: Int = 225
EuclideanRing.negate(15)
// val res3: Int = -15
EuclideanRing.minus(15, 10)
// val res4: Int = 5
EuclideanRing.zero[Int]
// val res5: Int = 0
EuclideanRing.one[Int]
// val res6: Int = 1
EuclideanRing.gcd(15, 10)
// val res7: Int = 5
EuclideanRing.lcm(15, 10)
// val res8: Int = 30
EuclideanRing.equot(15, 10)
// val res9: Int = 1
EuclideanRing.emod(15, 10)
// val res10: Int = 5
EuclideanRing.equotmod(15, 10)
// val res11: (Int, Int) = (1,5)

Ссылки:

scalabook