mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-01-29, 04:36   #1
smslca
 
Apr 2011

7 Posts
Default ((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)
smslca is offline   Reply With Quote
Old 2012-01-29, 06:01   #2
smslca
 
Apr 2011

1112 Posts
Default

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?
smslca is offline   Reply With Quote
Old 2012-01-29, 11:30   #3
ccorn
 
ccorn's Avatar
 
Apr 2010

22×37 Posts
Default

Quote:
Originally Posted by smslca View Post
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
ccorn is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 01:21.

Thu Nov 26 01:22:00 UTC 2020 up 76 days, 22:32, 3 users, load averages: 2.49, 2.07, 1.86

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.