Multiplicative inverse ($17^{-1} \mod 31$)?

So. Sorry for bothering you with such a simple question, but I can't really get this done.

It's just an exam question in which I need to use CRT in order to calculate the RSA signature of a msg m=101(dec), given RSA public modulus n=527=p*q=17*31.

So using CRT I need to calculate $p^{-1}\mod q$, which is, for the Euclidean Extended Algorithm, equal to $p^{\phi(q)-1} \mod q$. Or in other terms $17^{-1}\mod 31 = 17^{29} \mod 31.$

My exercise book shows a (imo) wrong result for this calculation. Can you please do the calculation (I used a Square&Multiply strategy) and tell me what you get? Also, is there any tool (online or not) which can help me doing fast MOD calculations like this one without having to do them manually? Thanks in advance and sorry for the "useless" and "noobish" question.

• $17^{-1}\bmod 31=11$. Does this help you? – SEJPM Jul 11 '15 at 17:13
• Yes, thank you. Did you do the calculation manually? Or did you use a tool? – user3333434 Jul 11 '15 at 17:17
• as far as tools go, you may want to look for a CAS being able to do number and group theory related operations. See Wikipedia for a list. Personally I use the outdated Derive 6, which isn't available any longer. – SEJPM Jul 11 '15 at 17:18
• It's not hard to write the code to calculate the multiplicative inverse (as I did in this answer to another question), but if you just want to calculate it one time for something you're working on, it's a built in function in various languages. For example, use PowerMod[17,-1,31] in Mathematica or Wolfram Alpha. See more ways to do it on RosettaCode. – Charphacy Jul 11 '15 at 18:54
• Use Extended Euclidean algorithm to the pair (17,31). Then you will get a Bezout identity $a17+b31=1.$ Take modulo 31 and you are done. The inverse is $a$. – 111 Jul 19 '15 at 17:58