StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In the ring of integers modulo <code>C</code>, these equations are equivalent:</p> <blockquote> <p><code>A / B (mod C)</code><br> <code>A * (1/B) (mod C)</code><br> <code>A * B</code><sup>-1</sup><code>(mod C)</code>.</p> </blockquote> <p>Thus you need to find <code>B</code><sup>-1</sup>, the multiplicative inverse of <code>B</code> modulo <code>C</code>. You can find it using e.g. extended Euclidian algorithm.</p> <p>Note that not every number has a multiplicative inverse for the given modulus.</p> <p>Specifically, <code>B</code><sup>-1</sup> exists if and only if <code>gcd(B, C) = 1</code> (i.e. <code>B</code> and <code>C</code> are coprime).</p> <h3>See also</h3> <ul> <li><a href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse" rel="noreferrer">Wikipedia/Modular multiplicative inverse</a></li> <li><a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm" rel="noreferrer">Wikipedia/Extended Euclidian algorithm</a></li> </ul> <hr> <h3>Modular multiplicative inverse: Example</h3> <p>Suppose we want to find the multiplicative inverse of 3 modulo 11.</p> <p>That is, we want to find</p> <blockquote> <p><code>x = 3</code><sup>-1</sup><code>(mod 11)</code><br> <code>x = 1/3 (mod 11)</code><br> <code>3x = 1 (mod 11)</code></p> </blockquote> <p>Using extended Euclidian algorithm, you will find that:</p> <blockquote> <p><code>x = 4 (mod 11)</code></p> </blockquote> <p>Thus, the modular multiplicative inverse of 3 modulo 11 is 4. In other words:</p> <blockquote> <p><code>A / 3 == A * 4 (mod 11)</code> </p> </blockquote> <hr> <h3>Naive algorithm: brute force search</h3> <p>One way to solve this:</p> <blockquote> <p><code>3x = 1 (mod 11)</code></p> </blockquote> <p>Is to simply try <code>x</code> for all values <code>0..11</code>, and see if the equation holds true. For small modulus, this algorithm may be acceptable, but extended Euclidian algorithm is much better asymptotically.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload