Safe Haskell | None |
---|---|

Language | Haskell98 |

This module provides a type class for Euclidean domains. A Euclidean domain is a ring with a notion of division with remainder, and therefore greatest common divisors.

- class (Eq a, Ring a) => EuclideanDomain a where
- euclid_mod :: EuclideanDomain a => a -> a -> a
- euclid_div :: EuclideanDomain a => a -> a -> a
- euclid_gcd :: EuclideanDomain a => a -> a -> a
- extended_euclid :: EuclideanDomain a => a -> a -> (a, a, a, a, a)
- euclid_inverse :: EuclideanDomain a => a -> Maybe a
- is_unit :: EuclideanDomain a => a -> Bool
- inv_mod :: EuclideanDomain a => a -> a -> Maybe a
- euclid_divides :: EuclideanDomain a => a -> a -> Bool
- euclid_associates :: EuclideanDomain a => a -> a -> Bool
- euclid_extract_power :: EuclideanDomain a => a -> a -> (Integer, a)
- rounddiv :: Integral a => a -> a -> a

# Euclidean domains

## Definition

class (Eq a, Ring a) => EuclideanDomain a where Source #

A type class for Euclidean domains. A Euclidean domain is a ring with a Euclidean function and a division with remainder.

The Euclidean function for the Euclidean domain. This is a
function *rank* : *R*\{0} → ℕ such that:

- for all nonzero
*a*,*b*∈*R*,*rank*(*a*) ≤*rank*(*ab*); - if
*b*≠ 0 and (*q*,*r*) =*a*`divmod`

*b*, then either*r*= 0 or*rank*(*r*) <*rank*(*b*).

divmod :: a -> a -> (a, a) Source #

Given *a* and *b*≠0, return a quotient and remainder for
division of *a* by *b*. Specifically, return (*q*,*r*) such that
*a* = *qb* + *r*, and such that *r* = 0 or *rank*(*r*) < *rank*(*b*).

## Functions

euclid_mod :: EuclideanDomain a => a -> a -> a infixl 7 Source #

Calculate the remainder for the division of *x* by *y*. Assumes
that *y* ≠ 0.

euclid_div :: EuclideanDomain a => a -> a -> a infixl 7 Source #

Calculate the quotient for the division of *x* by *y*, ignoring
the remainder, if any. This is typically, but not always, used in
situations where the remainder is known to be 0 ahead of time.
Assumes that *y* ≠ 0.

euclid_gcd :: EuclideanDomain a => a -> a -> a Source #

Calculate the greatest common divisor in any Euclidean domain.

extended_euclid :: EuclideanDomain a => a -> a -> (a, a, a, a, a) Source #

Perform the extended Euclidean algorithm. On inputs *x* and
*y*, this returns (*a*,*b*,*s*,*t*,*d*) such that:

*d*= gcd(*x*,*y*),*ax*+*by*=*d*,*sx*+*ty*= 0,*at*-*bs*= 1.

euclid_inverse :: EuclideanDomain a => a -> Maybe a Source #

Find the inverse of a unit in a Euclidean domain. If the given
element is not a unit, return `Nothing`

.

is_unit :: EuclideanDomain a => a -> Bool Source #

Determine whether an element of a Euclidean domain is a unit.

inv_mod :: EuclideanDomain a => a -> a -> Maybe a Source #

Compute the inverse of *a* in *R*/(p), where *R* is a Euclidean
domain. Note: this works whenever *a* and *p* are relatively
prime. If *a* and *p* are not relatively prime, return `Nothing`

.

euclid_divides :: EuclideanDomain a => a -> a -> Bool Source #

Check whether *a* is a divisor of *b*.

euclid_associates :: EuclideanDomain a => a -> a -> Bool Source #

Check whether *a* and *b* are associates, i.e., differ at most by
a multiplicative unit.

euclid_extract_power :: EuclideanDomain a => a -> a -> (Integer, a) Source #

Given elements *x* and *y* of a Euclidean domain, find the
largest *k* such that *x* can be written as *y*^{k}*z*.
Return the pair (*k*, *z*).

If *x*=0 or *y* is a unit, return (*0*, *x*).