← Back to topics
Topic

Modular Arithmetic - divide

A
Amtrix
Is there a way to do this:
[( a mod m ) / ( b mod m )] mod m ==(a/b) mod m
?????

EDIT: I ask about the left side of the equation
p
picsel
I think there should be no help during the competition.

But you should try search function :)
A
Amtrix
Well ok then i go a little google :P. We can then discuss after the competetion...
A
Amtrix
The competetion ended :D
b
boba5551
One way to solve it is using Diophantus equation and another is using Fermat's theorem and as fas as I know it work only for primer numbers, what is 10007.
p
picsel
Well gates said it here (check Fermat's little theorem for more info):
http://www.z-trening.com/new/www/html/forum.php?show_board=10008&ref_id=10008&view_topic=111230


( A / B ) % m = ( ( A % m ) * ( B^( m - 2 ) % m ) ) % m , if m is prime
g
gates
if we want to calculate modular inverse of b
then we have
b^-1 = ( 1/b ) mod m
b * b^-1 = 1 ( mod m )

using Fermat's Little theorem we have b^( m-1 ) = 1

so we have:
b * b^-1 = b^( m-1 ) ( mod m )
b^-1 = b^( m-2 ) ( mod m )