Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've written Haskell function, that helps me to compute $x^{-1} \mod m$.

invM x m = invMhelp x 0 m; --modular multiplicative inverse x^-1 (mod m) = inv x m  
invMhelp x i m = if (x*i `mod` m == 1) then i else (invMhelp x (i+1) m);

For example:

Main> 13 `invM` 2109

That means $13^{-1} = 649 \mod 2109$.

How can I compute $x^{-2} \mod m$? ($x^{-2} \mod m = (x^{-1})^2 \mod m$)

Can I simply use the power of two of the multiplicative inverse and then apply the modulo m again?

Example: $13^{-1} = 649 \mod 2109$, $649^2 \mod 2109 = 1510$.

Is $13^{-2} \mod 2109$ equal to $1510$?

Sorry for the noob question, but I'm not sure about this. Thanks for answers.

share|cite|improve this question
up vote 5 down vote accepted

$\rm\: a\equiv b^{-1} \Rightarrow\ a^2 \equiv b^{-2}\: $ via congruences are preserved by multiplication (so too by squaring). If you don't yet know that property then you can instead prove the sought result as follows:

$$\rm a\equiv b^{-1}\ \:(mod\ m)\ \Rightarrow\ m\:|\: ab-1\ \Rightarrow\ m|(ab-1)(ab+1)\ =\ a^2 b^2 - 1\ \Rightarrow\ a^2 \equiv b^{-2}\ \:(mod\ m)$$

For completeness, here is the proof that congruences are preserved by mutliplication

LEMMA $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \:(mod\ m)$

Proof $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $

This congruence product rule is at the heart of many other similar product rules, for example Leibniz's product rule for derivatives in calculus, e.g. see my post here.

share|cite|improve this answer
In short: you can square before inverting, or invert before squaring. – J. M. Nov 14 '10 at 0:56

Yes. That will work.

$a \equiv b \pmod{m} \Rightarrow a^k \equiv b^k \pmod{m}$, whenever $k \in \mathbb{N}$

share|cite|improve this answer
Sivaram, looks like "\implies" doesn't work. Try "\Rightarrow". – Marek Nov 13 '10 at 18:48
Thank you, I obviously lack the basic knowledge of the number theory. – Tom Pažourek Nov 13 '10 at 18:49

Your Answer


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.