Register to reply

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

by smslca
Tags: congruent
Share this thread:
smslca
#1
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
Fungus deadly to AIDS patients found to grow on trees
Canola genome sequence reveals evolutionary 'love triangle'
Scientists uncover clues to role of magnetism in iron-based superconductors
smslca
#2
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
#3
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):
http://www.mast.queensu.ca/~math418/m418oh/m418oh04.pdf


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