how can u solve 17^-1 mod 100?
plz explain the method followed in solving such cases where the exponent is a negative number..
thanks
You are looking for a number x such that
(mod 100)
Basically we're down to trial and error, but we can make the following observation: since the base is 100 we can simply start looking at numbers that multiply by 7 to end in a 1. So we start with this list:
3, 13, 23, 33, 43, 53, 63, 73, 83, 93
We also know that in the integer system x is going to have to be larger than 6 to make 17x > 100, so we can count out the 3. (Small savings, but in other problems it might cut the list down significantly.)
So let's try them:
(mod 100)
(mod 100)
(mod 100)
(mod 100)
(mod 100)
(mod 100)
(mod 100)
(mod 100)
(mod 100)
So it looks like (mod 100)
-Dan
It means the inverse of a number. Given a positive interger and any integer , we can write (modulo )) iff . Exactly what topsquak said. It is the inverse.
---
We want to find such that:
.
Since .
We can simulatenously solve (since ) the congruences:
The first one is really simple, add 4 to RHS 4 times to get:
The second one is also not so bad, add 25 to RHS 2 times to get:
So you are left with,
You can use the Chinese Remainder Theorem.
To solve this modulo 100 (which is what you are looking for).
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
I see you decided not to do it my way.
Using the Euclidean algorithm is another good way to do it.
I just cannot follow what you do!
Here, what an learn frum die meister to how to present mathematical arguments.
---
By definition it means,
.
Thus,
.
Now this is a linear diophatine equation.
You can use the Euclidean algorithm to solve this.
First, we need to find .
Thus, we see that .
Work backwards,
Thus, we see that works.
Meaning,
.
Now you can add 100 to this number because we are working modulo 100 and it makes no difference to get,
.
Thus we get 53.