{- |
Description: Gaussian integer divisibility
Copyright: Copyright (C) 2022 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P43" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P43 (gaussianDividesBy) where

import           Data.Complex
import           Solutions.Arithmetic (dividesBy, gaussianMultiply)

-- | Determine whether a Gaussian integer is divisible by another.
gaussianDividesBy
  -- | \(x\)
  :: Complex Integer
  -- | \(y\)
  -> Complex Integer
  -- | \(y \mid x\), i.e., whether \(x\) is divisible by \(y\)
  -> Bool
gaussianDividesBy :: Complex Integer -> Complex Integer -> Bool
gaussianDividesBy Complex Integer
_ (Integer
0 :+ Integer
0)        = Bool
False
gaussianDividesBy Complex Integer
_ (Integer
1 :+ Integer
0)        = Bool
True
gaussianDividesBy Complex Integer
_ (-1 :+ Integer
0)       = Bool
True
gaussianDividesBy Complex Integer
_ (Integer
0 :+ Integer
1)        = Bool
True
gaussianDividesBy Complex Integer
_ (Integer
0 :+ -1)       = Bool
True
gaussianDividesBy Complex Integer
x y :: Complex Integer
y@(Integer
c :+ Integer
d) =
  Complex Integer -> Integer
forall a. Complex a -> a
realPart Complex Integer
numerator Integer -> Integer -> Bool
forall a. Integral a => a -> a -> Bool
`dividesBy` Integer
denominator Bool -> Bool -> Bool
&& Complex Integer -> Integer
forall a. Complex a -> a
imagPart Complex Integer
numerator Integer -> Integer -> Bool
forall a. Integral a => a -> a -> Bool
`dividesBy` Integer
denominator
  -- Normalizing x / y = (x * conjugate y) / (y * conjugate y)
  -- so that the denominator is purely real.
  where numerator :: Complex Integer
numerator = Complex Integer -> Complex Integer -> Complex Integer
gaussianMultiply Complex Integer
x (Complex Integer -> Complex Integer)
-> Complex Integer -> Complex Integer
forall a b. (a -> b) -> a -> b
$ Complex Integer -> Complex Integer
forall a. Num a => Complex a -> Complex a
conjugate Complex Integer
y
        denominator :: Integer
denominator = Integer
cInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
c Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
dInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
d