inverse modulos

From: Johnathan Doe (No-spam-here-johnathan_doe_at_!!!NOSPAMTHANKS!!!fastmail.com.au)
Date: 12/02/04 

Date: Thu, 02 Dec 2004 17:17:27 +1100

If two numbers x and m are relatively prime, so that gcd(x, m) = 1 is
true, then x has a unique multiplicative inverse modulo m, a, so that ax
= 1 (mod m).

Knowing only the multiplicative inverse, a modulo m, and m, is it
possible to find x?

Is it true that a*x - 1 = k*m, for some k, possibly negative? Or
multiple k's? How to find the multiple k's so that x could be found?
Is that possible at all, so that the candidate k's can be found knowing
only the inverse a modulo m and m?

If there is no single way to find it, is there a reasonable trial and
error process to go through to find x given a and m?

What I suppose I am saying is, what is the relationship between x and
its inverse a modulo m?

Well, if you caught all that, hope you can help me out :)

Cheers
Johnathan

Relevant Pages

  • Re: inverse modulos
    ... >true, then x has a unique multiplicative inverse modulo m, a, so that ax ... so that the candidate k's can be found knowing ... Take the continued fraction expansion of the fraction a/m, ...
    (sci.math)
  • Re: n Inverse Modulo m
    ... For additive inverse, the inverse of n modulo m is simply -n modulo m; ... For multiplicative inverse there is no general formula, ... Euclidean Algorithm, like I said before). ...
    (sci.math)
  • Re: n Inverse Modulo m
    ... A multiplicative inverse of n modulo m is an integer x such that ... If you don't know what the extended Euclidean Algorithm is, ...
    (sci.math)
  • Re: n Inverse Modulo m
    ... A multiplicative inverse of n modulo m is an integer x such that ... Euclidean Algorithm, AS I HAVE ALREADY TOLD YOU TWICE. ... If you don't know what the extended Euclidean Algorithm is, ...
    (sci.math)
  • Re: inverse modulos
    ... > Pawel Gladki wrote: ... > them x and n, and the gcd is 1, so they are relatively prime. ... There are an infite number of x's whose modulo ... > So I can find a/the numerical solution by solving a linear diophantine ...
    (sci.math)
Quantcast