How Can You Find 'y' When ((m*y) mod n) ≡ (n-1)?

[smslca]

If given a 'n' value and m = floor ( squareroot(n) )
then is there any way to find the value of 'y' , such that

((m*y) mod n) is congruent to (n-1)

 

[smslca]

with the help of a friend
i figured out that, if m is the divisor of n, it won't be possible to get a solution .
But what about the other values?

 

[dodo]

Hi, smsica,
you are looking for a solution to the congruencymy \equiv -1 \pmod nThe definition of congruency says that two numbers are congruent to n when their difference is a multiple of n; so solving this congruency can be expressed as finding integers y,k such thatmy+1 = nkornk-my = 1Call z = -y, and look for solutions k,z tonk+mz = 1You do that using the Extended Euclidean Algorithm; you will find that a solution can only be found when m and n are coprime, that is, when GCD(m,n)=1.

There is a simpler example here (with numbers whose GCD is larger than 1, but the mechanics of the algorithm are the same):
http://www.mast.queensu.ca/~math418/m418oh/m418oh04.pdf