Number Theory in Haskell

number_theory.hs

-- Number Theory stuff
-- N. P. O'Donnell, 2020

module NumberTheory (congruent, factors, prime, extendedEuclideanAlgorithm, greatestCommonDivisor, lowestCommonMultiple, coPrime) where

-- Euclidean division of two integers
euclideanDivision :: Integer -> Integer -> Integer
euclideanDivision a b = toInteger (floor ((fromIntegral a) / (fromIntegral b)))


-- Congruence of 2 integers a and b, modulo n
congruent :: Integer -> Integer -> Integer -> Bool
congruent n a b = (mod a n) == (mod b n)


-- Get all the factors of an integer (excluding 1)
factors :: Integer -> [Integer]
factors n = concat (map 
        (\x -> if (euclideanDivision n x) == x then [x] else [x, euclideanDivision n x]) 
        (filter (\ x -> n `mod` x == 0) [2 .. floor(sqrt(fromIntegral n))])
    )


-- Test an integer for primality (brute force)
prime :: Integer -> Bool
prime n = length (factors n) == 0


-- Get only the prime factors of an integer
primeFactors :: Integer -> [Integer]
primeFactors n = filter prime (factors n)


-- Prime factorization
minPrimeFactor :: Integer -> Integer
minPrimeFactor n = head (primeFactors n)

primeFactorization :: Integer -> [Integer]
primeFactorization n = 
    if prime n then 
        [n]
    else 
        minPrimeFactor n : primeFactorization (euclideanDivision n (minPrimeFactor n))


-- Extended Euclidean Algorithm
extendedEuclideanAlgorithm :: Integer -> Integer -> (Integer, Integer, Integer)
extendedEuclideanAlgorithm 0 b = (b, 0, 1)
extendedEuclideanAlgorithm a b = do
    let (g, y, x) = extendedEuclideanAlgorithm (mod b a) a
    (g, x - (euclideanDivision b a) * y, y)


-- Greatest Common Divisor
greatestCommonDivisor :: Integer -> Integer -> Integer
greatestCommonDivisor a b = do
    let (gcd, _, _) = (extendedEuclideanAlgorithm a b)
    gcd


-- Lowest Common Multiple
lowestCommonMultiple :: Integer -> Integer -> Integer
lowestCommonMultiple a b = euclideanDivision (a * b) (greatestCommonDivisor a b)


-- Co-primality
coPrime :: Integer -> Integer -> Bool
coPrime a b = do
    let (gcd, _, _) = (extendedEuclideanAlgorithm a b)
    gcd == 1