1. ## number theory doubt

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

2. Originally Posted by ramanujam
how can you solve 17^-1 mod 100?

please 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
$x \cdot 17 \equiv 1$ (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:
$13 \cdot 17 \equiv 21$ (mod 100)
$23 \cdot 17 \equiv 91$ (mod 100)
$33 \cdot 17 \equiv 61$ (mod 100)
$43 \cdot 17 \equiv 31$ (mod 100)
$53 \cdot 17 \equiv 1$ (mod 100)
$63 \cdot 17 \equiv 71$ (mod 100)
$73 \cdot 17 \equiv 41$ (mod 100)
$83 \cdot 17 \equiv 11$ (mod 100)
$93 \cdot 17 \equiv 81$ (mod 100)

So it looks like $17^{-1} = 53$ (mod 100)

-Dan

3. thanks dan,
i find this concept of negative exponent very confusing indeed..
coz 17^-1 is theoretically equal to (1/17) then how come 17^-1 mod 100 is equal to 53..
could u plz explain this as well..

4. Originally Posted by ramanujam
how can u solve 17^-1 mod 100?

plz explain the method followed in solving such cases where the exponent is a negative number..
It means the inverse of a number. Given a positive interger $n$ and any integer $m$, we can write $m^{-1}=k$ (modulo $n$)) iff $mk\equiv 1 (\bmod n)$. Exactly what topsquak said. It is the inverse.
---
We want to find $x$ such that:
$17x\equiv 1 (\bmod 100)$.
Since $100 = 2^2\cdot 5^2$.
We can simulatenously solve (since $\gcd(2,5)=1$) the congruences:
$17x\equiv 1 (\bmod 4)$
$17x \equiv 1(\bmod 25)$

The first one is really simple, add 4 to RHS 4 times to get:
$17x\equiv 17 (\bmod 4) \Rightarrow x\equiv 1(\bmod 4)$

The second one is also not so bad, add 25 to RHS 2 times to get:
$17x\equiv 51 (\bmod 25)\Rightarrow x\equiv 3(\bmod 25)$

So you are left with,
$x\equiv 1 (\bmod 4)$
$x\equiv 3 (\bmod 25)$

You can use the Chinese Remainder Theorem.

To solve this modulo 100 (which is what you are looking for).

5. thanks perfect hacker

6. 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

7. 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
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.
---

$17x\equiv 1(\bmod 100)$
By definition it means,
$17x - 1 = 100y \mbox{ for some }y\in \mathbb{Z}$.
Thus,
$17x +100z = 1 \mbox{ where }z=-y$.

Now this is a linear diophatine equation.
You can use the Euclidean algorithm to solve this.
First, we need to find $\gcd(17,100)$.

$100 = 5\cdot 17 +15$
$17 = 1\cdot 15+2$
$15 = 7\cdot 2 +1$
Thus, we see that $\gcd(17,100)=1$.

Work backwards,
$15 - 7\cdot 2 = 1$
$15 - 7 (17 - 1\cdot 15) = 1$
$8\cdot 15 - 7\cdot 17 = 1$
$8 (100 - 5\cdot 17) - 7\cdot 17 = 1$
$8\cdot 100 -47\cdot 17 =1$
$17(-47)+100(8)=1$
Thus, we see that $x=-47$ works.

Meaning,
$17(-47)\equiv 1(\bmod 100)$.

Now you can add 100 to this number because we are working modulo 100 and it makes no difference to get,
$-47 + 100 \equiv 53 (\bmod 100)$.

Thus we get 53.