## RE r*s = 1 mod p

Expand Messages
• Yes, we can! You want to find the inverse of a number s modulo p. As p is prime, we have GCD(s,p) = 1 and it exists an unique inverse r
Message 1 of 1 , May 5, 2005
• 0 Attachment
Yes, we can!

You want to find the inverse of a number s modulo p. As p is prime, we have GCD(s,p) = 1
and it exists an unique inverse r<p for s (as you said well).

The procedure is as follows:

1) We make use of Euclid's algorithm to find a chain of decreasing numbers a1, a2,...,a_l
with a1 == s and a_l == 1 (p == q1*s + a_2, n == q2*a_2 + a_3, a_2 == q3*a_3 + a_4...)

2) We do algebra with the last equation to clear the value of a_(l-1). We go through the
chain in the bottom-up way, substituting a_(k-1) with the value in terms of a_(k), till
you find p as a linear dependence of s and -1. Then you have the inverse of s modulo p.

I know I don't explain it very well in english, so I will give some examples:

a) Find the inverse of 3 (mod 5).

1) 5 == 3*1 + 2 , 3 == 2*1 + 1 --> 2 == 3 - 1

2) 5 == 3*1 + 2 == 3*1 + (3 - 1) == 3*(1+1) - 1 == 3*2 - 1

Then 5 + 1 == 3*2 and 2 is the inverse of 3 modulo 5.

b) Find the inverse of 7 (mod 24)

1) 24 == 7*3 + 3, 7 == 3*2 + 1 --> 3 == (7 - 1) / 2

2) 24 == 7*3 + 3 == 7*3 + (7-1) / 2 --> 24*2 == 2*7*3 + (7-1) == 7(6+1) - 1

2*24 +1 == 7*7

An we have that 7 is its own inverse modulo 24
----------------------------------------------

I hope this helps. If it is not clear enough, I will try to explain it further.

Jose Brox

----- Original Message -----
From: "Mark Underwood" <mark.underwood@...>
Sent: Thursday, May 05, 2005 9:41 PM
Subject: [PrimeNumbers] r*s = 1 mod p

Hi all

If we are given a prime p and r < p, can we easily find the (unique)
s < p such that

r*s = 1 mod p?

Let's assume we can. Then of course the t < p that satisfies

r*t = n mod p

for any n < p is exactly

t = (s*n) mod p

But can we find the original s (easily) in the first place?

Mark

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/