Register to reply

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

by smslca
Tags: congruent
Share this thread:
Jan28-12, 10:34 PM
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)
Phys.Org News Partner Science news on
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds
Jan29-12, 12:00 AM
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?
Jan29-12, 03:03 AM
P: 688
Hi, smsica,
you are looking for a solution to the congruency[tex]my \equiv -1 \pmod n[/tex]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[tex]my+1 = nk[/tex]or[tex]nk-my = 1[/tex]Call z = -y, and look for solutions k,z to[tex]nk+mz = 1[/tex]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):

Register to reply

Related Discussions
Congruent Curves Differential Geometry 0
Prove a^5 congruent to a (mod 15) Biology, Chemistry & Other Homework 1
N congruent 3 mod 4 Linear & Abstract Algebra 7
Not congruent? Math & Science Software 1
Congruent Modulo Linear & Abstract Algebra 1