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

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

share|improve this question

2 Answers 2

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|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|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. –  tomp Nov 13 '10 at 18:49

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.