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 ?


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

  • 6
    $\begingroup$ Just add $n^2$. $\endgroup$ – Yuval Filmus Apr 11 '11 at 3:44
  • $\begingroup$ @Yuval. Thanks ! It seems so easy now that you mention it :) I don't know why it didn't occur to me before. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.