Algebra.PrincipalIdealDomain
 Contents Class Standard implementations for instances Algorithms Properties
Synopsis
class (C a, C a) => C a where
 extendedGCD :: a -> a -> (a, (a, a)) gcd :: a -> a -> a lcm :: a -> a -> a
euclid :: (C a, C a) => (a -> a -> a) -> a -> a -> a
extendedEuclid :: (C a, C a) => (a -> a -> (a, a)) -> a -> a -> (a, (a, a))
extendedGCDMulti :: C a => [a] -> (a, [a])
diophantine :: C a => a -> a -> a -> Maybe (a, a)
diophantineMin :: C a => a -> a -> a -> Maybe (a, a)
diophantineMulti :: C a => a -> [a] -> Maybe [a]
chineseRemainder :: C a => (a, a) -> (a, a) -> Maybe (a, a)
chineseRemainderMulti :: C a => [(a, a)] -> Maybe (a, a)
propMaximalDivisor :: C a => a -> a -> a -> Property
propGCDDiophantine :: (Eq a, C a) => a -> a -> Bool
propExtendedGCDMulti :: (Eq a, C a) => [a] -> Bool
propDiophantine :: (Eq a, C a) => a -> a -> a -> a -> Bool
propDiophantineMin :: (Eq a, C a) => a -> a -> a -> a -> Bool
propDiophantineMulti :: (Eq a, C a) => [(a, a)] -> Bool
propDiophantineMultiMin :: (Eq a, C a) => [(a, a)] -> Bool
propChineseRemainder :: (Eq a, C a) => a -> a -> [a] -> Property
propDivisibleGCD :: C a => a -> a -> Bool
propDivisibleLCM :: C a => a -> a -> Bool
propGCDIdentity :: (Eq a, C a) => a -> Bool
propGCDCommutative :: (Eq a, C a) => a -> a -> Bool
propGCDAssociative :: (Eq a, C a) => a -> a -> a -> Bool
propGCDHomogeneous :: (Eq a, C a) => a -> a -> a -> Bool
propGCD_LCM :: (Eq a, C a) => a -> a -> Bool
Class
 class (C a, C a) => C a where Source

A principal ideal domain is a ring in which every ideal (the set of multiples of some generating set of elements) is principal: That is, every element can be written as the multiple of some generating element. gcd a b gives a generator for the ideal generated by a and b. The algorithm above works whenever mod x y is smaller (in a suitable sense) than both x and y; otherwise the algorithm may run forever.

Laws:

```   divides x (lcm x y)
x `gcd` (y `gcd` z) == (x `gcd` y) `gcd` z
gcd x y * z == gcd (x*z) (y*z)
gcd x y * lcm x y == x * y
```

(etc: canonical)

Minimal definition: * nothing, if the standard Euclidean algorithm work * if extendedGCD is implemented customly, gcd and lcm make use of it

Methods
 extendedGCD :: a -> a -> (a, (a, a)) Source

Compute the greatest common divisor and solve a respective Diophantine equation.

```   (g,(a,b)) = extendedGCD x y ==>
g==a*x+b*y   &&  g == gcd x y
```

TODO: This method is not appropriate for the PID class, because there are rings like the one of the multivariate polynomials, where for all x and y greatest common divisors of x and y exist, but they cannot be represented as a linear combination of x and y. TODO: The definition of extendedGCD does not return the canonical associate.

 gcd :: a -> a -> a Source

The Greatest Common Divisor is defined by:

```   gcd x y == gcd y x
divides z x && divides z y ==> divides z (gcd x y)   (specification)
divides (gcd x y) x
```
 lcm :: a -> a -> a Source
Least common multiple
Instances
 C Int C Integer C T (Ord a, C a, C a) => C (T a) (C a, C a) => C (T a)
Standard implementations for instances
 euclid :: (C a, C a) => (a -> a -> a) -> a -> a -> a Source
 extendedEuclid :: (C a, C a) => (a -> a -> (a, a)) -> a -> a -> (a, (a, a)) Source
Algorithms
 extendedGCDMulti :: C a => [a] -> (a, [a]) Source
Compute the greatest common divisor for multiple numbers by repeated application of the two-operand-gcd.
 diophantine :: C a => a -> a -> a -> Maybe (a, a) Source

A variant with small coefficients.

Just (a,b) = diophantine z x y means a*x+b*y = z. It is required that gcd(y,z) divides x.

 diophantineMin :: C a => a -> a -> a -> Maybe (a, a) Source
Like diophantine, but a is minimal with respect to the measure function of the Euclidean algorithm.
 diophantineMulti :: C a => a -> [a] -> Maybe [a] Source
 chineseRemainder :: C a => (a, a) -> (a, a) -> Maybe (a, a) Source
Not efficient enough, because GCD/LCM is computed twice.
 chineseRemainderMulti :: C a => [(a, a)] -> Maybe (a, a) Source
For Just (b,n) = chineseRemainder [(a0,m0), (a1,m1), ..., (an,mn)] and all x with x = b mod n the congruences x=a0 mod m0, x=a1 mod m1, ..., x=an mod mn are fulfilled.
Properties
 propMaximalDivisor :: C a => a -> a -> a -> Property Source
 propGCDDiophantine :: (Eq a, C a) => a -> a -> Bool Source
 propExtendedGCDMulti :: (Eq a, C a) => [a] -> Bool Source
 propDiophantine :: (Eq a, C a) => a -> a -> a -> a -> Bool Source
 propDiophantineMin :: (Eq a, C a) => a -> a -> a -> a -> Bool Source
 propDiophantineMulti :: (Eq a, C a) => [(a, a)] -> Bool Source
 propDiophantineMultiMin :: (Eq a, C a) => [(a, a)] -> Bool Source
 propChineseRemainder :: (Eq a, C a) => a -> a -> [a] -> Property Source
 propDivisibleGCD :: C a => a -> a -> Bool Source
 propDivisibleLCM :: C a => a -> a -> Bool Source
 propGCDIdentity :: (Eq a, C a) => a -> Bool Source
 propGCDCommutative :: (Eq a, C a) => a -> a -> Bool Source
 propGCDAssociative :: (Eq a, C a) => a -> a -> a -> Bool Source
 propGCDHomogeneous :: (Eq a, C a) => a -> a -> a -> Bool Source
 propGCD_LCM :: (Eq a, C a) => a -> a -> Bool Source