Thursday 7 December 2017

number theory - Solving $frac{x}{y}$ mod $m$ efficiently?

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

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...