- #1

- 64

- 0

then is there any way to find the value of 'y' , such that

((m*y) mod n) is congruent to (n-1)

- Thread starter smslca
- Start date

- #1

- 64

- 0

then is there any way to find the value of 'y' , such that

((m*y) mod n) is congruent to (n-1)

- #2

- 64

- 0

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

- 695

- 2

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

- Last Post

- Replies
- 7

- Views
- 10K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 9K

- Last Post

- Replies
- 2

- Views
- 4K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 7

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 3K