Sunday, 22 October 2017

elementary number theory - Euclid Algorithm to Find Muliplicative Inverse




Here I am trying to find the multiplicative inverse of 19 respect to 29.



19x1(mod29)



What I tried



29=1(19)+10 19=1(10)+9 10=1(9)+1.



From backtracking, I came up with the



1=2(29)3(19) 



However, 3 is not a multiplicative inverse of the 29. Where am I making a mistake?




I looked many answers including this answer; however, couldn't figure out my mistake.


Answer



What you have found indeed is that 326 is the multiplicative inverse of 19 mod29.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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