1
$\begingroup$

We know that : $( x.y )$ mod $m$ = ( ($x$ mod $m$) . ($y$ mod $m$) ) mod $m$

Is there any property for: $\frac{x}{y}$ mod $m$ like $\frac{x \mod m}{y \mod m}$ mod $m$ . I hope this fails.

I want to find an efficient way to solve: $$\frac{x_1 .x_2.x_3 ... x_i }{y_1 . y_2 . y_3 . . .y_j} \mod \ m$$ where, $x_i, x_j, m \le 10 ^9 ; $ and $\frac{x_1 .x_2.x_3 ... x_i }{y_1 . y_2 . y_3 . . .y_j}$ results in an integer

Edit: If $a \ mod \ m = \ x$ and $b \mod m =\ y$, then can we express $(\frac{a}{b} \ mod \ m)$ in terms of x, y and m ??

Any help will be appreciated :) Thanks

$\endgroup$
2

1 Answer 1

0
$\begingroup$

We have:

$a=fm+x, b=gm+y$, find $\dfrac{a}{b}\mod m$

$\dfrac{a}{b}\mod m\equiv\dfrac{fm+x}{gm+y}\mod m$

$h\equiv\dfrac{1}{gm+y}\mod m\implies (gmy+hy)\equiv1\mod m\implies hy\equiv1\mod m$

$\implies h\equiv\dfrac{1}{y}\mod m$

so $\dfrac{a}{b}\equiv\dfrac{x}{y}\mod m$.

For example, $103=3\times31+10$ and $201=6\times31+15$ so:

$\dfrac{103}{201}\mod 31\to\dfrac{10}{15}\mod31\to\dfrac{2}{3}\mod31\to42\mod31\to11\mod31$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .