How do I compute x^(-2) mod m?

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
649


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

-

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

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

-
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