trait EuclidianRing should not be a Ring

The docs give it away EuclideanRing implements a Euclidean domain.

However, there's a problem: a Euclidian domain need not be a Ring.

Approximately & intuitively, euclidean domains defines some set of of integral or whole numbers. These might well be the set of natural numbers (0, 1, 2, 3 etc), which don't have closed subtraction operation.

A ring however, must include a subtraction operation; that's what the n in ring signifies (n for 'negation').

Unfortunately, the trait hierarchy in the algebra package is over-constrained: it makes EuclideanRing extend Ring even though the operations it introduces, based around divmod, dividing whole numbers to yield a quotient and a remainder, do not require the negation aspect of rings.

trait EuclideanRing[@sp(Int, Long, Float, Double) A] extends Any with GCDRing[A] { self =>
  def euclideanFunction(a: A): BigInt
  def equot(a: A, b: A): A
  def emod(a: A, b: A): A
  def equotmod(a: A, b: A): (A, A) = (equot(a, b), emod(a, b))
  def gcd(a: A, b: A)(implicit ev: Eq[A]): A =
    EuclideanRing.euclid(a, b)(ev, self)
  def lcm(a: A, b: A)(implicit ev: Eq[A]): A =
    if (isZero(a) || isZero(b)) zero else times(equot(a, gcd(a, b)), b)

The impact is that it's not possible to implement a complete & correct algebra for natural numbers (non-negative integers) using the Cats hierarchy.

Start with algebra-core/src/main/scala/algebra/ring/EuclideanRing.scala at the trait hierarchy and read the surrounding GCDRing and divmod-related definitions. Trace the existing hierarchy and implementations to determine the compatibility impact of separating Euclidean-domain operations from ring negation. Done means the algebra package can represent non-negative integers without an over-constrained hierarchy and its affected tests or implementations remain correct.