Question

How to find inverse of 11 mod 26?
Please, help

Answer 1

\[ \text{ I think }11^{-1} \mod 26 \text{ is equvialent to solving } \\ 11x \equiv 1 \mod 26 \]

Answer 2

oh yeah @freckles is correct

Answer 3

oh, it is ikram, I am sorry friend, you changed your avatar. hehehe. I am trying to solve it now.
@freckles Thanks for the tip :)

Answer 4

@ikram002p show me your way, please

Answer 5

ok so first way is trial but ur gotta be lucky , as seems 19 is the solution!

Answer 6

you can also do that euclidean thing

Answer 7

I have final on November 10. On my book, it says
\(a^{-1}=a^{\phi (26)-1}\)
I know how to find it, but it takes a long time to do. I am looking for the fastest way to find it out to save time on test.:)

Answer 8

this way is so fast with phi function

Answer 9

@freckles how to do with euclidean?
@ikram002p no, it is not

Answer 10

but be careful its like this.
a^phi(26)= 1 mod 26

Answer 11

phi (26) = 13,
phi (26) -1 = 12
11^ 12 =? mod 26

Answer 12

well see phi(26)=12 (do u know how to get it ? )

Answer 13

\[11x-26k=1 \\ 26=11(2)+4 \\ 11=4(2)+3 \\ 4=3(1)+1 \\ \text{ now back through } \\ 4-3=1 \\ 4-[11-4(2)]=1 \\ 4-11+4(2)=1 \\ 4(3)-11=1 \\ 3(26-11(2)]-11=1 \\ 3(26)-11(6)-11=1 \\ 3(26)+11(-7)=1 \\ 11(-7)-26(-3)=1 \\ x= \equiv -7 \mod 26 =19\]

Answer 14

Yes, It is easier. Thanks @freckles

Answer 15

and @Loser66 here is the rule

for any arbitrary number a,b such that gcd(a,b)=1
then

\(\Large a^{\phi(b)}=1 \mod b\)

Answer 16

gcd(11,26)=1 then directly we can write

\(\Large 11^{\phi(26)}=1 \mod 26 \\ \Large \text{ note that } \phi(26)=12 \\\Large 11^{12}=1 \mod 26 \)

Answer 17

ermm so for origin equation

11x=1 mod 26
x=11^11 mod 26 u can simplify it and u can use it like this only.

Answer 18

yeah that should work

for \((a,n)=1\), from euler generalization of little fermat we have :

\(1\equiv a^{\phi(n)}\pmod{n}\)

multiply \(a^{-1}\) both sides

Answer 19

this is a pretty useless formula however
reducing \(a^{\phi(n)-1}\) may not be any faster compared to other methods when the exponent or \(a\) is large enough

Answer 20

well its the fastest way compared to euclidean algorithm ;-), and yet it could be so fast as

11^6=-1 mod 26.

Answer 21

yes, that is the problem. And on test, I am not allowed to use calculator. :)
one mistake can ruin my work.

Answer 22

trust your professor tha the gives human friendly numbers in the test

Answer 23

Euclidean method seems the best choice here. :)
Thanks all for helping out.

Answer 24

I am rather well prepare for test than waiting for luck. :)

Answer 25

u can use a trick with phi(n) divisors idk its up to u @loser66. my teacher never came up with sensible numbers xD so cant hold on the trust only.

Answer 26

Thanks you guys.

Answer 27

=D

Answer 28

good luck though!

Answer 29

Thank you.