Let $x = a\bmod M, y = b\bmod M$, where $M$ is a prime number.
I do not know $a$ and $b$, but I know $x$ and $y$ and $M$.
Is it possible to calculate $ (a/b)\bmod M $?
Sorry if it sounds too junior
Asked
Active
Viewed 22 times
0
-
If $M$ is prime and $(b,M)=1$, then $b$ is invertible$\bmod M$, so you can take $a\cdot b^{-1}\bmod M$ – sharding4 Jun 05 '17 at 01:47
-
@sharding4 but I do not know $a$, $b$, I only know $x$, $y$... – shole Jun 05 '17 at 01:48
-
They're the same$\bmod M$. You should be able to use the Euclidean algorithm to find an inverse for $y\bmod M$. Then $x(y)^{-1}\equiv a(b)^{-1}\bmod M$ – sharding4 Jun 05 '17 at 01:50
-
Let $a = 22, b = 8, M = 3$, then $ (a/b) mod M = 0 $, but $ (x/y) mod M $ = $ (1*2) mod M $ = 2 ... – shole Jun 05 '17 at 01:56
-
$a/b\bmod M \equiv 0$ is incorrect. Why do you say that? Look at $2\cdot 8 -3\cdot 5 =1$ which tells you that $2$ is an inverse for $8\bmod 3$ – sharding4 Jun 05 '17 at 01:59
-
@sharding4 oh man I am dumb. You are right...sorry & thanks! – shole Jun 05 '17 at 02:01
-
1We all get a little smarter as we figure out our mistakes. – sharding4 Jun 05 '17 at 02:07