Thursday, 7 December 2017

number theory - Solving fracxy mod m efficiently?

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




Is there any property for:
xy 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}...