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

- class IntegralDomain a => EuclideanDomain a where
- norm :: a -> Integer
- quotientRemainder :: a -> a -> (a, a)

- propNorm :: (EuclideanDomain a, Eq a) => a -> a -> Bool
- 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
- genEuclidAlg :: (EuclideanDomain a, Eq a) => [a] -> a
- lcmE :: (EuclideanDomain a, Eq a) => a -> a -> a
- genLcmE :: (EuclideanDomain a, Eq a) => [a] -> a
- extendedEuclidAlg :: (EuclideanDomain a, Eq a) => a -> a -> (a, a)
- genExtendedEuclidAlg :: (EuclideanDomain a, Eq a) => [a] -> [a]

# Documentation

class IntegralDomain a => EuclideanDomain a whereSource

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.

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

EuclideanDomain Z | |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The extended Euclidean algorithm.

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

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

Generalized extended Euclidean algorithm.

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