constructive-algebra-0.3.0: A library of constructive algebra.

Algebra.Structures.EuclideanDomain

Description

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

Synopsis

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.

Methods

norm :: a -> IntegerSource

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

Instances

 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

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)