Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
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
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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