Over a million developers have joined DZone.

Modular Inverse Function

DZone's Guide to

Modular Inverse Function

Free Resource
This function calculates & returns the inverse of a modulo n, both of which should be positive.  If the inverse does not exist, 0 is returned.  If you don't know what this means, don't bother.

int modInverse(int a, int n) {
 int i = n, v = 0, d = 1;
 while (a>0) {
  int t = i/a, x = a;
  a = i % x;
  i = x;
  x = d;
  d = v - t*x;
  v = x;
 v %= n;
 if (v<0) v = (v+n)%n;
 return v;

Opinions expressed by DZone contributors are their own.


Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.


{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}