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.