       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:= ExtendedGCD[3, 26]
Out= {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.

```

• Prev by Date: Re: Re: Recombining CoefficientList
• Next by Date: Re: Q: Help processing large arrays?
• Previous by thread: Re: Inverse of a Number
• Next by thread: Re: Inverse of a Number