Question

I am just wondering whether there is an more efficient way than trial division on finding out inverse of mod
( that is , given positive integer a, p, find an positive b, 0<= b <= p which leads a * b = 1 (mod p)) ?
sorry for my poor English :(

Answer 1

if a and p are relatively prime then
\[a^{p-1}\equiv 1 (\text{mod} p)\]

Answer 2

so to solve
\[ab\equiv 1 (\text{mod} p)\] for b you can take
\[b=a^{p-2}\] i guess. with small numbers trial and error may work best.

Answer 3

for example if i want to solve
\[6b\equiv 1 (\text{mod} 11)\] i could take
\[6^{9}\] lets check

\[6^2=3, 6^3=7, 6^4=9, 6^5=10,6^6=5,6^7=8,6^8=4,6^9=2\] and
\[6\times 2 = 1\]

Answer 4

oh it got cut off! last one was
\[6^9=2\] and
\[2\times 6 \equiv 1(\text{mod}11)\]

Answer 5

on the other had you probably could have come up with the "2" right away.

Answer 6

right ! thanks very much!

Answer 7

yw

Answer 8

I found that Euclidean algorithm can work it out as well, say \[6b \equiv 1(\mod 11)\] we have
5 = 11 - 6 * 1
1 = 6 - 5 * 1
and then
1 = 6 - 5 * 1 = 6 - (11 - 6 * 1) * 1 = 6 * 2 - 11
and we obtain
\[b = 2\]

in the case of \[130b \equiv 1 (\mod 11)\]
we have
9 = 130 - 11 * 11
2 = 11 - 9 * 1
1 = 9 - 2 * 4
and then
1 = 9 - 2 * 4
= 9 - (11 - 9) * 4
= 9 * 5 - 11 * 4
= (130 - 11 * 11) * 5 - 11 * 4
= 130 * 5 - 11 * 59
and we obtain
b = 5

besides, \[130b \equiv 9b \equiv 1(\mod 11) \] may make it easier :)

Answer 9

ps: how to type
(mod 11)
instead of
\[(\mod 11)\]

isn't it "(\mod 11)" in slash blankets?