MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

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.


  • 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