multiplicative

command
Version: v0.0.0-...-9d64b2e Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 25, 2021 License: MIT Imports: 1 Imported by: 0

README

Modular multiplicative inverse

Source: GeeksforGeeks
Source: Wikipedia - Modular Multiplicative Inverse

Given two integers ‘a’ and ‘m’, find modular multiplicative inverse of ‘a’ under modulo ‘m’.
The modular multiplicative inverse is an integer ‘x’ such that.

a x ≅ 1 (mod m)

The value of x should be in {0, 1, 2, … m-1}, i.e., in the range of integer modulo m.
The multiplicative inverse of “a modulo m” exists if and only if a and m are relatively prime (i.e., if gcd(a, m) = 1).

Example

Input: a = 3, m = 11
Output: 4
Since (43) mod 11 = 1, 4 is modulo inverse of 3(under 11).
One might think, 15 also as a valid output as "(15
3) mod 11" is also 1, but 15 is not in ring {0, 1, 2, ... 10}, so not valid.

Input: a = 10, m = 17
Output: 12
Since (10*12) mod 17 = 1, 12 is modulo inverse of 10(under 17).

Documentation

The Go Gopher

There is no documentation for this package.

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL