{- |
Description: Gaussian integer divisibility
Maintainer: dev@chungyc.org

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

import           Data.Complex
import qualified Solutions.P43 as Solution

-- \$setup
-- >>> import Data.Complex

{- | A Gaussian integer is a complex number where both the real and imaginary parts are integers.
If $$x$$ and $$y$$ are Gaussian integers where $$y \neq 0$$,
then $$x$$ is said to be divisible by $$y$$
if there is a Guassian integer $$z$$ such that $$x=yz$$.

Determine whether a Gaussian integer is divisible by another.

=== Examples

$$10 = 2 \times 5$$, so

>>> (10 :+ 0) gaussianDividesBy (2 :+ 0)
True

$$10 = -2i \times 5i$$, so

>>> (10 :+ 0) gaussianDividesBy (0 :+ 2)
True

However, there is no Gaussian integer $$x$$ such that $$5+2i = (2-i)x$$, so

>>> (5 :+ 2) gaussianDividesBy (2 :+ (-1))
False

=== __Hint__

For $$y \neq 0$$, $$z = xy$$ means that $$x = \frac{z}{y}$$.
If you multiply both the numerator and denominator by $$\overline{y}$$,
the conjugate of $$y$$, then you can normalize the denominator to be a real number.
You can then use this to check whether the real and imaginary parts are integers.
Recall that $$\overline{a+bi} = a-bi$$ and $$(a+bi)(c+di) = (ac-bd) + (bc+ad)i$$
for real numbers $$a$$, $$b$$, $$c$$, and $$d$$.
-}
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 -> Complex Integer -> Bool
Solution.gaussianDividesBy