# ((my) mod n ) congruent to n-1

by smslca
Tags: congruent
 P: 63 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)
 P: 63 with the help of a friend i figured out that, if m is the divisor of n, it wont be possible to get a solution . But what about the other values?
 P: 687 Hi, smsica, you are looking for a solution to the congruency$$my \equiv -1 \pmod n$$The 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 that$$my+1 = nk$$or$$nk-my = 1$$Call z = -y, and look for solutions k,z to$$nk+mz = 1$$You 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

 Related Discussions Differential Geometry 0 Biology, Chemistry & Other Homework 1 Linear & Abstract Algebra 7 Math & Science Software 1 Linear & Abstract Algebra 1