Originally Posted by

**ramanujam** this is how i have done,plz tell me if there is anything wrong..

m trying to solve

17x = 1 mod 100

using euclidean algorithm this is wat i get

100 = 17*5+15----> eqn 1

17 = 15*1+2---->eqn 2

15 = 7*2 + 1

2 = 2*1

now working bacwards

1 = 15-(7*2)

1 = 15 - (17-15*1)*7

1 = 100-(17*5) - 17*7 + 15*7

1 = 100 - 17 *12 - 15*7

1= 100 - 17*12 + (100-17*5)*7

1 = 100(8) - 17*47

which is of the form

100(8)+17(-47)=1

17* (-47) = 1 mod 100

since we are looking for a positive no hence x = (-47)+100 = 53

m not too sure abt the reasoning of my last step..

plz tell me

cheers