# Modular Inverse using Extended Euclidean Algorithm

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.

• Just add $n^2$. – Yuval Filmus Apr 11 '11 at 3:44
• @Yuval. Thanks ! It seems so easy now that you mention it :) I don't know why it didn't occur to me before. – Nik Apr 11 '11 at 3:50

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$.