Given two positive numbers \$x\$ and \$n\$ with \$x<2^n\$, write the shortest possible function to compute \$x^{-1} \mod 2^n\$. In other words, find \$y\$ such that \$xy=1 \mod 2^n\$.

Your function must complete in a reasonable time for at least \$n=64\$, so exhaustive search will not work.

If the inverse does not exist, you must indicate that to the caller somehow (throw an exception, return a sentinel value, etc).

If you're wondering where to start, try the Extended Euclidean Algorithm.

  • \$\begingroup\$ this is going to be a single statement in some math softwares \$\endgroup\$ – st0le Jan 29 '11 at 23:45
  • 1
    \$\begingroup\$ @st0le: Right, and you wouldn't be allowed to use such a function in such systems. :-D \$\endgroup\$ – Chris Jester-Young Jan 30 '11 at 0:20
  • \$\begingroup\$ Exponentiation has higher precedence than modulo, correct? \$\endgroup\$ – S.S. Anne Mar 4 '20 at 22:08

12 Answers 12


Python 95 89

c is your function. Returns 0 if there is no inverse (i.e. when x is even).

p=lambda x,y,m:y and p(x,y/2,m)**2*x**(y&1)%m or 1
c=lambda x,n:[0,p(x,2**n-1,2**n)][x%2]

Python, 29 bytes

lambda x,n:pow(x,2**n-1,2**n)

This returns 0 for even x. It uses Euler’s theorem, with the observation that 2^n − 1 is divisible by 2^(n − 1) − 1, via Python’s builtin fast modular exponentiation. This is plenty fast enough for n up to 7000 or so, where it starts taking more than about a second.


Python 3.8 (pre-release), 25 bytes

lambda a,b:pow(a,-1,2**b)

Try it online!


Mathematica - 22


f[x,n] returns y with x*y=1 mod 2^n, otherwise x is not invertible modulo 2^n


GolfScript (23 chars)


The sentinel result for a non-existent inverse is 0.

This is a simple application of Euler's theorem. \$x^{\varphi(2^n)} \equiv 1 \pmod {2^n}\$, so \$x^{-1} \equiv x^{2^{n-1}-1} \pmod {2^n}\$

Unfortunately that's rather too big an exponential to compute directly, so we have to use a loop and do modular reduction inside the loop. The iterative step is \$x^{2^k-1} = \left(x^{2^{k-1}-1}\right)^2 \times x\$ and we have a choice of base case: either k=1 with


or k=2 with


I'm working on another approach, but the sentinel is more difficult.

The key observation is that we can build the inverse up bit by bit: if \$xy \equiv 1 \pmod{2^{k-1}}\$ then \$xy \in \{ 1, 1 + 2^{k-1} \} \pmod{2^k}\$, and if \$x\$ is odd we have \$x(y + xy-1) \equiv 1 \pmod{2^k}\$. (If you're not convinced, check the two cases separately). So we can start at any suitable base case and apply the transformation \$y' = (x+1)y - 1\$ a suitable number of times.

Since \$0x \equiv 1 \pmod {2^0}\$ we get, by induction

\$x\left(\frac{1 - (x+1)^n}{x}\right) \equiv 1 \pmod {2^n}\$

where the inverse is the sum of a geometric sequence. I've shown the derivation to avoid the rabbit-out-of-a-hat effect: given this expression, it's easy to see that (given that the bracketed value is an integer, which follows from its derivation as a sum of an integer sequence) the product on the left must be in the right equivalence class if \$x+1\$ is even.

That gives the 19-char function


which gives correct answers for inputs which have an inverse. However, it's not so simple when \$x\$ is even. One potentially interesting option I've found is to add x&1 rather than 1.


This seems to give sentinel values of either \$0\$ or \$2^{n-1}\$, but I haven't yet proved that.

Taking that one step further, we can ensure a sentinel of \$0\$ for even numbers by changing the expression \$1 - (x+1)^n\$ into \$1 - 1^n\$:


That ties with the direct application of Euler's theorem for code length, but is going to have worse performance for large \$n\$. If we take the arguments the other way round, as n x f, we can save one character and get to 22 chars:


Ruby - 88 characters

Use the function f.

def e a,b;a%b==0?[0,1]:(x,y=e(b,a%b);[y,x-(y*(a/b))])end
def f x,n;e(x,2**n)[0]*(x%2)end

Simply the recursive function from the linked wiki page, returns 0 on error.

  • \$\begingroup\$ You can save some characters by inlining e: (e=->a,b{...})[x,2**n][0]. Can also save a character by testing a%b<1 instead of a%b==0. \$\endgroup\$ – histocrat Jun 12 '14 at 14:19

Haskell, 42 bytes


Using an algorithm based on Hensel’s lemma that doubles the number of digits in every iteration, this runs in under a second for n up to about 30 million!


Pyth, 9 bytes


Try it here!

Takes input in reverse order. Or, 9 bytes too: .^EtK^2QK.


.^Et^2Q^2  - Full program.

.^         - Pow function. The same in Python (pow).
  E        - The second input.
    ^2Q    - And 2 ^ first input.
   t       - Decremented.
       ^2  - And 2 ^ first input again.

GAP, 39 bytes

f:=function(x,n)return 1/x mod 2^n;end;

f(x,n) returns the inverse of x modulo 2^n and gives an error message

Error, ModRat: for <r>/<s> mod <n>, <s>/gcd(<r>,<s>) and <n> must be coprime

if no inverse exists.


GolfScript, 10 9 bytes


Try it online!

A port of Mr. XCoder's solution, to GS. Stack manipulation is a little messy, could probably be done with a little tomfoolery. Takes in input as X N.

V 1.1 : Improved stack manip, it sucks a lot less now.

2\?:q(?q% #Multiplicative Inverse
2\        #Move "2" to the second pos on the stack. X 2 N
  ?       #Exponentiate. X 2^N
   :q     #Remember, q is 2^N.
     (    #Decrement. X 2^N-1
      ?   #Exponentiate. X^(2^N-1)
       q? #Mod by 2^N.

# X^([2^N] -1) % 2^N is the multiplicative inverse, since
# X^([2^N] -1)*X = X^(2^N)
# which is 1 mod 2^N if X and 2^N are coprime.

If there is no M.I., it will return 0.


Jelly, 5 bytes


Try it online!

Takes input with \$n\$ first and \$x\$ second, returns \$0\$ if no such inverse exists. The Footer in the TIO link reverses the input for you and formats the test cases.

How it works

2*æi@ - Main link. Takes n on the left and x on the right
2*    - Yield 2*n
  æi@ - Modular inverse of x, modulo 2*n, or if none exists, 0.

Python 3, 77 57 bytes

f=lambda x,n,b=1,i=1:n and f(x,n-1,b-(b&i)*~-x,i+i)or b%i

Outgolfed all you snek users (except for the pow(x, -1, 2**n) cheapshots) with nothing but pure algorithm.

Try it online! (Only uses Python 3.8 for comparison against pow(a,-1,2**n))

Ungolfed version:

def func(value, shift, acc = 1, mask = 1):
    if value != 0:
        return func(value, shift - 1, acc - (acc & mask) * (value - 1), mask << 1)
        return acc & (mask - 1)

Or, as a loop with size hacks removed:

def func(value, exponent):
    value -= 1
    acc = 1
    for i in range(exponent):
        if acc & (1 << i):
            acc -= value << i
    return acc & ((1 << i) - 1)


The function is a lambda called f. It takes two positive integers, and returns either the multiplicative modular inverse or zero.

You may be wondering what the heck is going on. This uses a different, faster, and smaller algorithm for modular inverse for powers of 2 instead of the Euclidian approach.

I'm not going to go too far into the details of why it works, as it is really complex and explained better by others. Translation: even I don't fully understand it.

This set of algorithms is explained here on algassert with a related algorithm explained here on Crypto SE with some interesting papers linked.

This algorithm actually uses no true multiplication (just shifts), the multiplication is just a shortcut for size.

This naturally returns 0 for even numbers, as the odd subtraction (we start with x - 1) causes a chain reaction of trailing with 0b0, which, when masked off, turns the result to zero. No need for a manual sentinel.

0000 0001 - 0000 1101 -> 1111 0010
1111 0010 - 0001 1010 -> 1110 0000

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.