Modular Inverse using Extended Euclidean Algorithm

Question

I am trying to find the modular inverse for [(n+1) mod 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 mod 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.

Answer 1

If $1-n$ is a modular inverse, then so is $(1-n) + k*n^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$.