module Solutions.P42 (multiplicativeInverse) where
multiplicativeInverse :: Integral a => a -> a -> Maybe a
multiplicativeInverse :: forall a. Integral a => a -> a -> Maybe a
multiplicativeInverse a
a a
n
| a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
n = a -> a -> Maybe a
forall a. Integral a => a -> a -> Maybe a
multiplicativeInverse (a
a a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
n) a
n
| a
r a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
1 = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ a
x a -> a -> a
forall a. Integral a => a -> a -> a
`mod` a
n
| Bool
otherwise = Maybe a
forall a. Maybe a
Nothing
where (a
r,a
x,a
_) = (a, a) -> (a, a) -> (a, a) -> (a, a, a)
forall a. Integral a => (a, a) -> (a, a) -> (a, a) -> (a, a, a)
reduce (a
n,a
a) (a
0,a
1) (a
1,a
0)
reduce :: Integral a => (a,a) -> (a,a) -> (a,a) -> (a,a,a)
reduce :: forall a. Integral a => (a, a) -> (a, a) -> (a, a) -> (a, a, a)
reduce (a
0,a
r') (a
_,a
x') (a
_,a
y') = (a
r',a
x',a
y')
reduce (a
r,a
r') (a
x,a
x') (a
y,a
y') = (a, a) -> (a, a) -> (a, a) -> (a, a, a)
forall a. Integral a => (a, a) -> (a, a) -> (a, a) -> (a, a, a)
reduce (a
r'a -> a -> a
forall a. Num a => a -> a -> a
-a
qa -> a -> a
forall a. Num a => a -> a -> a
*a
r, a
r) (a
x'a -> a -> a
forall a. Num a => a -> a -> a
-a
qa -> a -> a
forall a. Num a => a -> a -> a
*a
x, a
x) (a
y'a -> a -> a
forall a. Num a => a -> a -> a
-a
qa -> a -> a
forall a. Num a => a -> a -> a
*a
y, a
y)
where q :: a
q = a
r' a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
r