|Jan28-12, 10:34 PM||#1|
((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)
|Jan29-12, 12:00 AM||#2|
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||#3|
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):
|Similar Threads for: ((my) mod n ) congruent to n-1|
|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|