Re: Inverse of a Number

*To*: mathgroup at smc.vnet.net*Subject*: [mg2566] Re: Inverse of a Number*From*: danl (Daniel Lichtblau)*Date*: Tue, 21 Nov 1995 09:24:28 -0500*Organization*: Wolfram Research, Inc.

In article <DI9Ay8.Gz at wri.com> "Enrico C. Walker" <ewalke1 at gl.umbc.edu> writes: > First of all, I thank you all those who responded to my earlier question. > My second question is How to find the inverse of a number in some Modulo > system. For example: > > 3*9 Mod 26 = 1, therefore inverse of 3 is 9 in Mod 26 system. > > a*b Mod N = 1, therefore a is inverse of b and vice versa in N > system. > > How can I solve b in Mathematica where a and N are given. Please advise. > > -RICO- > ExtendedGCD will give a list of two elements. The first is the gcd of the inputs and the second is a list of (what I believe are called) the cofactors. For example, In[2]:= ExtendedGCD[3, 26] Out[2]= {1, {9, -1}} because 9*3 + (-1)*26 == (the gcd of 3 and 26, which is) 1. More generally, for integers a and n, a is invertible modulo n iff GCD[a, n] is one, and in that case the appropriate cofactor gives the inverse (just take the eqn c1*a + c2*n == 1 and mod out by n). So what you want is ExtendedGCD[a, n][[2, 1]]. Daniel Lichtblau Wolfram Research, Inc.