mersenneforum.org > Math ((my) mod n ) congruent to n-1
 Register FAQ Search Today's Posts Mark Forums Read

 2012-01-29, 04:36 #1 smslca   Apr 2011 7 Posts ((my) mod n ) congruent to n-1 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)
 2012-01-29, 06:01 #2 smslca   Apr 2011 1112 Posts 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?
2012-01-29, 11:30   #3
ccorn

Apr 2010

22×37 Posts

Quote:
 Originally Posted by 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)
Yes, for any m coprime to n. The key algorithm is fundamental and famous: Look up the Extended Euclidean Algorithm (XGCD). You ask for y being the negated multiplicative inverse of m mod n. The XGCD gives you the multiplicative inverse, which is n-y in your terms.

Last fiddled with by ccorn on 2012-01-29 at 11:41