Go back to previous page
Forum URL: http://www.cut-the-knot.org/cgi-bin/dcforum/forumctk.cgi
Forum Name: College math
Topic ID: 7
Message ID: 1
#1, RE: modular arithmetic and encryption
Posted by alexb on Oct-31-00 at 12:27 PM
In response to message #0
Well, the intention here is to this kind of problems that involve numbers much, much larger than 7 or 160. But as an example, let's solve

(1) 7d = 1 (mod 160)

The equation is equivalent to

(2) 7d - 160x = 1

An extension of Euclid's algorithm is used to solve such equations. Here's a solution:

(3) 7·23 - 160·1 = 1

Subtract (3) from (2):

(4) 7·(d - 23) - 160·(x - 1) = 1

It thus follows that

d = 23 + 160t
x = 1 + 7t

solve (2). Therefore, d = 23 solves (1).

All the best,
Alexander Bogomolny