Prove or disprove

for all x,y,z ∈ ℤ*253 (basically integers from 1 to 253)

[(x*y mod 253) = (x*z mod 253)] implies y = z

In other words, when equation x*y mod 253 = w for x, w ∈ ℤ*253 admits a solution, then there's always a unique solution y ∈ ℤ*253

This post was edited by moutonguerrier on Oct 10 2019 10:16am

pick x that's not invertible in Z/253Z, like x = 11 since 253 = 11*23
then
0 mod 253 = 11*23 mod 253 = (11*23 + 11*23) mod 253 = 11*46 mod 253
so this fails for (x,y,z) = (11,23,46)

amazing !

thanks for the help

I guess it simply means to pick an x so that x*y mod 253 = 0

So you cannot invert the function and get only one solution (you would get many solutions if you invert it, thus not invertible).

yes?


I could use (x,y,z) = (11,23, z)
where z can equal 46 or 69 or ... up to 253.

This post was edited by moutonguerrier on Oct 10 2019 06:07pm

How would I do this if this was mod prime ?

lets say
with x,y,z ∈ ℤ*29
x*y mod 29 = x*z mod 29 implies y=z

Would this actually imply y=z ? idk how to proceed with mod prime

This post was edited by moutonguerrier on Oct 10 2019 06:27pm

Yes, you can pick 46, 69, etc. but don't go all the way to 253 because 253 is 0 mod 253 and if I understand correctly you want (x,y,z) non-zero (not sure what Z*253 is, I've never encountered this notation, I assume you mean Z/253Z*)
If x,y,z are allowed to be 0 then 11*0 = 23*11 is even simpler



If your modulus is a prime then any non-zero x is invertible (Z/pZ is a field), so you indeed have x*y mod 29 = x*z mod 29 => y mod 29 = z mod 29, as long as x is not 0 mod 29

This post was edited by Hanako on Oct 11 2019 01:05am