Compute modular inverse Given two positive numbers \$x\$ and \$n\$ with \$x&lt;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.
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.