Copyright | Copyright (C) 2021 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

Some solutions to Problems.P42 of Ninety-Nine Haskell Problems.

## Synopsis

- multiplicativeInverse :: Integral a => a -> a -> Maybe a

# Documentation

multiplicativeInverse :: Integral a => a -> a -> Maybe a Source #

Compute the multiplicative inverse \(x\) of a given integer \(a\) and modulus \(n\) lying in the range \(0 \leq x < n\).

Uses the extended Euclidean algorithm and the fact that \(ax \equiv 1 \pmod{n}\) if \(ax+ny=1\).