
#1
Jan2812, 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 (n1) 



#2
Jan2912, 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? 



#3
Jan2912, 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]nkmy = 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 