From Wikipedia:

In modular arithmetic,   the modular multiplicative inverse of an integer    a    modulo    m    is an integer    x    such that





a

x
≡
1


(
mod

m
)

.


{\displaystyle a\,x\equiv 1{\pmod {m}}.}


Or in other words, such that:





∃
k
∈

Z

,

a

x
=
1
+
k

m


{\displaystyle \exists k\in \mathbb {Z} ,\qquad a\,x=1+k\,m}


It can be shown that such an inverse exists   if and only if    a    and    m    are coprime,   but we will ignore this for this task.



Task

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in
your language,   compute the modular inverse of   42 modulo 2017.




 
with Ada.Text_IO;use Ada.Text_IO;
procedure modular_inverse is
  -- inv_mod calculates the inverse of a mod n. We should have n>0 and, at the end, the contract is a*Result=1 mod n
  -- If this is false then we raise an exception (don't forget the -gnata option when you compile 
  function inv_mod (a : Integer; n : Positive) return Integer with post=> (a * inv_mod'Result) mod n = 1 is 
    -- To calculate the inverse we do as if we would calculate the GCD with the Euclid extended algorithm 
    -- (but we just keep the coefficient on a)
    function inverse (a, b, u, v : Integer) return Integer is
     (if b=0 then u else inverse (b, a mod b, v, u-(v*a)/b));
  begin
    return inverse (a, n, 1, 0);
  end inv_mod;
begin 
  -- This will output -48 (which is correct)
  Put_Line (inv_mod (42,2017)'img);
  -- The further line will raise an exception since the GCD will not be 1
  Put_Line (inv_mod (42,77)'img);
  exception when others => Put_Line ("The inverse doesn't exist."); 
end modular_inverse;
 