honorsthesis

                                               Fun with Inverses Modulo n

                                                        Introduction

     In this thesis our goal is to describe a numerical algorithm, which, given n, finds pairs of numbers such that: 1) their product has remainder 1 when divided by n; 2) they satisfy certain maximal property, to be explained later. Such pairs have been considered in [2], [3] and some of their properties have been studied. However, there are some unanswered questions, which are difficult to approach theoretically. An algorithm for numeric generation of such pairs and finding their difference is expected to give some inside leads to finding the answers. Such an algorithm is described and a program implementation of it using Maple 8 is given, together with some demo outputs for specific n�s.

                                                   Setting Up the Field

     Let be the set of numbers , which are all the remainders you get when dividing an integer by . can be considered the set of equivalence classes of integers modulo   in the following way. We say   if and only if   have one and the same remainder modulo . By we denote the class of integers                       . There is a unique , , such that . We can introduce addition and multiplication in   by:   : and : , and we can verify   gets the properties of a commutative ring.   An element    is invertible in , if there is a class   such that when the two classes are multiplied together you get the class of 1, i.e. . We call   the inverse of , and we write it as or . The class of   is invertible if the greatest common divisor,   in , i.e.   are relatively prime. By using the Euclidean Algorithm we can prove that there exist such that . Translating this to classes, it can be reformulated as follows:
     Since , then
o
o
o
o but is , so
o so
Let   denote the multiplicative group of the invertible elements of .
     Consider   and its multiplicative table. By looking at the table, we can see the invertible elements and their inverses. Thus, the inverse of   is , i.e.      and .
     So, . The numbers 1, 3, 5, and 7 are relatively prime with 8, and therefore their classes are invertible. The numbers 0, 2, 4, 6, and 8 are not relatively prime with 8, and therefore their classes are not invertible.
     Thus, if and gcd , then . Suppose is prime, then all of the numbers,   are relatively prime to and will be invertible elements . In particular, if is prime, then and   will be invertible in .
     Take the prime number 11. We know . The multiplicative table of , for example, can be used to find the inverses of these classes.
     We can see the inverses, i.e.                  and .

Undergraduate Honors Thesis
(Under Construction)

Button from http://welcome.to/PoohsPage