Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Кольца НОД

Кольца НОД (кольца с наибольшим общим делителем) — это коммутативные кольца с единицей, в которых для любых двух элементов существует наибольший общий делитель (НОД). Эти кольца являются важным классом алгебраических структур, обобщающих свойства целых чисел.

Определение кольца НОД

Кольцо НОД — это коммутативное кольцо с единицей \(R\), в котором для любых двух элементов \(a, b \in R\) существует их наибольший общий делитель (НОД). Наибольший общий делитель \(d = \text{НОД}(a, b)\) определяется следующим образом:

Свойства колец НОД

Примеры колец НОД

Зачем нужны кольца НОД?

Кольца НОД находят применение в различных областях:

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

Кольца НОД - коммутативное кольцо с единицей с добавлением наибольшего общего делителя и наименьшего общего кратного.

Кольца НОД поддерживают следующие операции:

Для Кольца НОД должны соблюдаться законы родителей:

, а также следующие законы:

Код

trait GCDRing[A] extends CRingWithUnity[A]:
  def gcd(x: A, y: A): A

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

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

(Z, +, *)

given GCDRing[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)

  extension (a: Int) override def inverse: Int = -a

Законы

Законы наследуются от коммутативного кольца с единицей.

Кроме того:

... // Законы коммутативного кольца с единицей

def checkGCDLCMMultiplication[A](x: A, y: A)(using
    gr: GCDRing[A]
): ValidatedNel[String, Unit] =
  Either.cond[String, Unit](
    gr.times(gr.gcd(x, y), gr.lcm(x, y)) == gr.times(y, x),
    (),
    "Произведение НОД и НОК должно равняться произведению чисел: gcd(x, y) * lcm(x, y) = x * y"
  ).toValidatedNel

def checkGCDAssociativity[A](x: A, y: A, z: A)(using
    gr: GCDRing[A]
): ValidatedNel[String, Unit] =
  Either.cond[String, Unit](
    gr.gcd(gr.gcd(x, y), z) == gr.gcd(x, gr.gcd(y, z)),
    (),
    "Не соблюдается ассоциативность НОД: gcd(gcd(x, y), z) = gcd(x, gcd(y, z))"
  ).toValidatedNel

def checkLCMAssociativity[A](x: A, y: A, z: A)(using
    gr: GCDRing[A]
): ValidatedNel[String, Unit] =
  Either.cond[String, Unit](
    gr.lcm(gr.lcm(x, y), z) == gr.lcm(x, gr.lcm(y, z)),
    (),
    "Не соблюдается ассоциативность НОК: lcm(lcm(x, y), z) = lcm(x, lcm(y, z))"
  ).toValidatedNel

def checkGCDCommutativity[A](x: A, y: A)(using
    gr: GCDRing[A]
): ValidatedNel[String, Unit] =
  Either.cond[String, Unit](
    gr.gcd(x, y) == gr.gcd(y, x),
    (),
    "Не соблюдается коммутативность НОД: gcd(x, y) = gcd(y, x)"
  ).toValidatedNel

def checkLCMCommutativity[A](x: A, y: A)(using
    gr: GCDRing[A]
): ValidatedNel[String, Unit] =
  Either.cond[String, Unit](
    gr.lcm(x, y) == gr.lcm(y, x),
    (),
    "Не соблюдается коммутативность НОК: lcm(x, y) = lcm(y, x)"
  ).toValidatedNel

Схема

classDiagram
    class Semigroup~A~{
        +combine(x: A, y: A) A
    }  
    class Monoid~A~{
        +empty() A
    }
    Semigroup <|-- Monoid
    class CommutativeSemigroup~A~
    Semigroup <|-- CommutativeSemigroup  
    class Group~A~{
      +inverse(x: A) A
    }  
    Monoid <|-- Group 
    class CommutativeMonoid~A~
    Monoid <|-- CommutativeMonoid
    CommutativeSemigroup <|-- CommutativeMonoid
    class AbelianGroup~A~
    Group <|-- AbelianGroup
    CommutativeMonoid <|-- AbelianGroup
    class Semiring~A~
    CommutativeMonoid <|-- Semiring
    class MultiplicativeSemigroup~A~{
        +times(x: A, y: A) A
    }
    MultiplicativeSemigroup <|-- Semiring
    Semigroup .. MultiplicativeSemigroup
    class Ring~A~
    AbelianGroup <|-- Ring
    Semiring <|-- Ring
    class CommutativeSemiring~A~
    Semiring <|-- CommutativeSemiring
    class SemiringWithUnity~A~{
        +one() A
    }
    Semiring <|-- SemiringWithUnity
    class CommutativeRing~A~
    Ring <|-- CommutativeRing
    CommutativeSemiring <|-- CommutativeRing
    class RingWithUnity~A~
    Ring <|-- RingWithUnity
    SemiringWithUnity <|-- RingWithUnity
    class CommutativeRingWithUnity~A~
    CommutativeRing <|-- CommutativeRingWithUnity
    RingWithUnity <|-- CommutativeRingWithUnity
    class GCDRing~A~{
        +gcd(x: A, y: A) A
        +lcm(x: A, y: A) A
    }
    CommutativeRingWithUnity <|-- GCDRing

Реализация в библиотеках

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

import spire.algebra.GCDRing
import spire.math.Rational
import spire.std.int.*

GCDRing.plus(Rational(1, 2), Rational(1, 3))
// val res0: spire.math.Rational = 5/6
GCDRing.times(Rational(1, 2), Rational(1, 3))
// val res1: spire.math.Rational = 1/6
GCDRing.pow(Rational(1, 2), 3)
// val res2: spire.math.Rational = 1/8
GCDRing.negate(Rational(1, 2))
// val res3: spire.math.Rational = -1/2
GCDRing.minus(Rational(1, 2), Rational(1, 3))
// val res4: spire.math.Rational = 1/6
GCDRing.zero[Rational]
// val res5: spire.math.Rational = 0
GCDRing.one[Rational]
// val res6: spire.math.Rational = 1
GCDRing.gcd(15, 10)
// val res7: Int = 5
GCDRing.lcm(15, 10)
// val res8: Int = 30

Ссылки: