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=3−1(2)=3−1(5−1(3))=2(3)−5=2(13−2(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=13⋅2+−5⋅5
as stated. But taking this whole equation modulo 13, we get
1≡13⋅2+−5⋅5≡−5⋅5≡8⋅5(mod13)
using that multiplies of 13 vanish (are equivalent to 0) and that 8≡−5(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=1⋅11−2⋅5 and taking everything modulo 11 again, the first term vanishes and we get that −2 is the inverse of 5 modulo 11, but −2≡9(mod11), so we can also use 9 if that's more convenient. (and indeed 9×5=45=1+4×11≡1(mod11) so that works out.
No comments:
Post a Comment