[Math] Modular Inverse using Extended Euclidean Algorithm

modular arithmetic

I am trying to find the modular inverse for $(n+1)\pmod {n^2}$ using EEA and I end up getting $1-n$ as the modular inverse. But, I want the inverse to be a positive number since its modular arithmetic.

Example: For $n = 3$, the modular inverse of $4 \pmod 9$ is $-2$ using EEA. But $7$ is positive modular inverse which I require.

I am not sure how to solve this problem. Can anyone help me ?

Thanks.

P.S: Sorry about the formatting. I am new to this website and still trying to get the hang of it.

Best Answer

If $1-n$ is a modular inverse, then so is $(1-n) + kn^2$ for any integer k. In your case, to get the inverse between $0$ and $n^2$, you can take $k=1$ to get the inverse as $n^2-n+1$.

Related Question