
Algebra.PrincipalIdealDomain 





Synopsis 

class (C a, C a) => C a where    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



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.
   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
   Least common multiple

  Instances  


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 twooperandgcd.



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.



Like diophantine, but a is minimal
with respect to the measure function of the Euclidean algorithm.




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










propDiophantineMin :: (Eq a, C a) => a > a > a > a > Bool  Source 






















Produced by Haddock version 2.6.0 