Why does cross-multiplication not work with modulus?

103 Views Asked by At

I want to find whether the statement $(a/b)modp < (c)modp$ holds true or false without calculating the multiplicative inverse of b (as it's a very costly procedure when the size of b increases around 500 bits). Workaround I thought was to cross multiply and check if (a)modp < (b*c)modp. But it is not showing consistency...
Consider mod 7.

Consider $(5/3)mod7 < 4$
=$(5*5)mod7 < 4$ (inverse of 3=5 as (3*5)mod7=1)
=$4 < 4$ which is false.
Now consider $5 < (3*4)mod7$
=$5 < 5$ which is false

Now consider $(1/3)mod7 < 3$
=$(1*5)mod7 < 3$
=$5 < 3$ which is false
Now consider $1 < (3*3)mod7$
=$1 < 2$ which is true!!

Is this method wrong? If yes, why is it wrong? I imagine it should have not caused any problems!! Also, what else i can do to check whether (a/b)modp < (c)modp holds true or false without calculating the multiplicative inverse of b?

UPDATE!!--- Assume $c=(p+1)/2$. What can i do for this special condition?

Other examples..
Consider $(3/2)mod7>4$
The right way to do this is to calculate the inverse of 2.
$=(3*4)mod7>4$
$=5>4$ which is true
Now consider cross multiplication
$3>(4*2)mod7 = 3>1$ which is true.
What this can mean is that instead of finding the inverse which is very time consuming when the no of bits exceed 500, i can just cross-multiply and then compare as i get the same result.

Consider $(3/5)mod7 > 4$
$=(3*3)mod7>4$
$=2>4$ which is false
Now consider cross-multiplication
$=3>(4*5)mod7$
$3>6$ which is false. So, cross multiplication seems like its working.. But no!!

Consider $(5/4)mod7 > 4$
$=(5*2)mod7 > 4$
$=3 > 4$ which is false
Now, consider cross-multiplication
$=5 > (4*4)mod7$
$=5 > 2$ which is true!!

See the discrepancy here.. Is this method wrong? What else can i do? Am i missing a minor detail here and this method here can give the right answers?