Question

7^-1 (mod 26)

Answer 1

mod?

Answer 2

modulo. @George, can you show me the guess and check one?

Answer 3

\[7\cdot1\equiv7\neq1\pmod{26}\]\[7\cdot2\equiv14\neq1\pmod{26}\]\[7\cdot3\equiv21\neq1\pmod{26}\]\[7\cdot4\equiv2\neq1\pmod{26}\]\[7\cdot5\equiv9\neq1\pmod{26}\]\[\vdots\]Until you get \[7x\equiv1\pmod{26}\]

Answer 4

so basically find ax that equals 1mod26?

Answer 5

7*11 = 77 = -1 (mod 26)

So 7*(-11) = -77 = 1 (mod 26)

Because -11 = 15 (mod 26), this means 7*15 = 1 (mod 26)

Answer 6

Correct. You could also find \(\phi(26)=12\) so by Euler's theorem you know\[7^{11}\equiv1\pmod{26}\]Then you can calculate this by computer or hand.

Answer 7

Typo there. You know \[7^{12}\equiv1\pmod{26}\]so\[7\cdot7^{11}\equiv1\pmod{26}\]which implies\[7^{11}\equiv7^{-1}\pmod{26}\]

Answer 8

However, this relies on knowing \(\phi(26)\). In practice, the only fast way to compute inverses modulo \(n\) where \(n\) is a composite number is by using the Extended Euclidean Algorithm.

Answer 9

I FINALLY GET IT. THANKS

Answer 10

3^-1 (mod 26)
9x= 1 (mod 26)
3*17= -1 (mod 26)
3*-17= 1 (mod 26)
-17= 9 (mod 26)
Is that right?

Answer 11

yes, 3^-1 = 9 (mod 26)

Answer 12

It's a little too much on the guess and check side for me, but it's correct.

Answer 13

Just for kicks, if you want an example where that method is rather unfeasible, try finding\[8332745929^{-1} \pmod{16534528044}\]

Answer 14

Gee thanks >.<
Can't you just make a program on Python?

Answer 15

You definitely could. And the fastest programs (to my knowledge) are a slightly streamlined version of the extended euclidean algorithm.