Friday, 8 November 2013

Basic modular inverses



I know how to do modular inverses in a hypothetical sense with the Euclidian method, and have been trying to do the, but I seem to keep getting the incorrect answer.




I'm trying to find the inverse of 5(mod13), for example.
The answer should be 8, but I can't seem to get that. These are my steps:
13=2(5)+35=1(3)+23=1(2)+1



1=31(2)=31(51(3))=2(3)5=2(132(5))5=2(13)4(5)5=2(13)5(5)



I'm sure I'm just misunderstanding the steps, but I don't know how.



Also, can the same method to used to find the inverse of 5(mod11), since 11=2(5)+1? I immediately don't know how to proceed from here.


Answer




Ok, after applying the extended Euclidean algorithm applied to 13 (modulus) and 5 (the number you want to invert)
you will find that



1=132+55



as stated. But taking this whole equation modulo 13, we get



1132+555585(mod13)



using that multiplies of 13 vanish (are equivalent to 0) and that 85(mod13) (add 13 to 5). So 8 and 5 are each other's inverses in Z13. And indeed 5×8=40 is one plus 39, a multiple of 13.




For 5 modulo 11 we first write 1 as a combination of 11 and 5:



1=11125 and taking everything modulo 11 again, the first term vanishes and we get that 2 is the inverse of 5 modulo 11, but 29(mod11), so we can also use 9 if that's more convenient. (and indeed 9×5=45=1+4×111(mod11) so that works out.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...