19 lines
886 B
Plaintext
19 lines
886 B
Plaintext
From [http://en.wikipedia.org/wiki/Modular_multiplicative_inverse Wikipedia]:
|
|
|
|
In [[wp:modular arithmetic|modular arithmetic]], the '''modular multiplicative inverse''' of an [[integer]] <big> ''a'' </big> [[wp:modular arithmetic|modulo]] <big> ''m'' </big> is an integer <big> ''x'' </big> such that
|
|
|
|
::<math>a\,x \equiv 1 \pmod{m}.</math>
|
|
|
|
Or in other words, such that:
|
|
|
|
::<math>\exists k \in\Z,\qquad a\, x = 1 + k\,m</math>
|
|
|
|
It can be shown that such an inverse exists if and only if <big> ''a'' </big> and <big> ''m'' </big> are [[wp:coprime|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.
|
|
<br><br>
|
|
|