# Computing modular inverses $65537^{-1\!}\bmod (10^n\!-1)$ for large $n$

I have the following formula: $$d \cdot 65537 \equiv 1 \pmod{9999...}$$ I have to find $$d$$, even in case the modulo is 30 digits long.

This means I am not supposed to brute force it, but I haven't yet come across to anything that would help me with this matter.

I thought cryptography uses modulo exactly because this problem is hard to solve. Can you give a hint on how to approach this problem? I think the 65537 prime is supposed to help in some way, but I'm not sure how.

• Your solution can't be unique: if $d_1$ is such a solution, then so is $d_2=d_1+9999999...$. – probablystuck May 17 at 15:16
• Welcome to Math Stack Exchange. Note $2^{16}=65536$ – J. W. Tanner May 17 at 15:17
• The Euclidean algoirthm works well, even if one of the terms is quite large. – lulu May 17 at 15:18
• So you need to find such $d$ so that $d\left(2^{16}+1\right) + 1 = 10^k$ for some integer $k$ – gt6989b May 17 at 15:19
• To be clear: $30$ digits is not especially big for the euclidean algorithm. wolfram alpha is able to handle it almost instantaneously. – lulu May 17 at 15:27