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

by smslca
Tags: congruent
smslca is offline
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 Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
smslca is offline
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?
dodo is offline
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