Algebra.Structures.EuclideanDomain

Representation of Euclidean domains. That is integral domains with an Euclidean functions and decidable division.

Documentation

class IntegralDomain a => EuclideanDomain a where

Euclidean domains

Given a and b compute (q,r) such that a = bq + r and r = 0 || norm r < norm b. Where norm is the Euclidean function.

Methods

norm :: a -> Integer

quotientRemainder :: a -> a -> (a, a)

Instances

EuclideanDomain Z

(Field k, Eq k) => EuclideanDomain (UPoly k x)

propNorm :: (EuclideanDomain a, Eq a) => a -> a -> Bool

Check both that |a| = |ab| and |a| = 0 for all a,b.

propQuotRem :: (EuclideanDomain a, Eq a) => a -> a -> Bool

propEuclideanDomain :: (EuclideanDomain a, Eq a) => a -> a -> a -> Property

modulo :: EuclideanDomain a => a -> a -> a

quotient :: EuclideanDomain a => a -> a -> a

divides :: (EuclideanDomain a, Eq a) => a -> a -> Bool

euclidAlg :: (EuclideanDomain a, Eq a) => a -> a -> a

The Euclidean algorithm for calculating the GCD of a and b.

genEuclidAlg :: (EuclideanDomain a, Eq a) => [a] -> a

Generalized Euclidean algorithm to compute GCD of a list of elements.

lcmE :: (EuclideanDomain a, Eq a) => a -> a -> a

Lowest common multiple, (a*b)/gcd(a,b).

genLcmE :: (EuclideanDomain a, Eq a) => [a] -> a

Generalized lowest common multiple to compute lcm of a list of elements.

extendedEuclidAlg :: (EuclideanDomain a, Eq a) => a -> a -> (a, a)

The extended Euclidean algorithm.

Computes x and y in ax + by = gcd(a,b).

genExtendedEuclidAlg :: (EuclideanDomain a, Eq a) => [a] -> [a]

Generalized extended Euclidean algorithm.

Solves a_1 x_1 + ... + a_n x_n = gcd (a_1,...,a_n)