{- |
Description: Gaussian primes using the two-square theorem
Copyright: Copyright (C) 2022 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P45" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P45 (isGaussianPrime') where

import           Data.Complex
import           Problems.P31

{- | Using Fermat's two-square theorem, it can be shown that a Gaussian integer \(a+bi\) is prime
if and only if it falls into one of the following categories:

* |a| is prime and \(|a| \equiv 3 \mod 4\), if \(b=0\).
* |b| is prime and \(|b| \equiv 3 \mod 4\), if \(a=0\).
* \( a^2 + b^2 \) is prime, if \( a \neq 0 \) and \( b \neq 0 \).

Use this property to determine whether a Gaussian integer is a Gaussian prime.
-}
isGaussianPrime' :: Complex Integer -> Bool
isGaussianPrime' :: Complex Integer -> Bool
isGaussianPrime' (Integer
a :+ Integer
0) = Integer -> Integer
forall a. Num a => a -> a
abs Integer
a Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
3 Bool -> Bool -> Bool
&& Integer -> Bool
forall a. Integral a => a -> Bool
isPrime (Integer -> Integer
forall a. Num a => a -> a
abs Integer
a)
isGaussianPrime' (Integer
0 :+ Integer
b) = Integer -> Integer
forall a. Num a => a -> a
abs Integer
b Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
3 Bool -> Bool -> Bool
&& Integer -> Bool
forall a. Integral a => a -> Bool
isPrime (Integer -> Integer
forall a. Num a => a -> a
abs Integer
b)
isGaussianPrime' (Integer
a :+ Integer
b) = Integer -> Bool
forall a. Integral a => a -> Bool
isPrime (Integer
aInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
bInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
b)