StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<ol> <li>If gcd(a,m)>1, then there is no such n. (Obvious)</li> <li>Otherwise, if m is prime, n=m-1. (<a href="http://en.wikipedia.org/wiki/Fermat%27s_little_theorem" rel="nofollow">Proof</a>)</li> <li>Otherwise (and as more general case), n=ф(m), where ф is Euler's totient function. (<a href="http://en.wikipedia.org/wiki/Euler%27s_theorem" rel="nofollow">Proof</a>)</li> </ol> <p>As you can see, computing ф(m) is essentially the same as factorization of m. This can be done in sqrt(m) time or faster, depending on how convoluted is the algorithm you use. Simple one:</p> <pre><code>int phi(m){ if(m==1) return 1; for(int d=2; d*d<m; ++d){ if(m%d != 0) continue; int deg = 1; long acc=1; for(; m%(acc*d)==0; ++deg) acc*=d; acc /= d; return phi(m/acc)*acc*(d-1)/d; } return m-1; } </code></pre> <p>Upd: My bad. a^(ф(m)) = 1 (mod m), but there can be lesser value of n (for a=1, n=1, no difference what m is; for a=14, m=15, n=2). n is divisor of ф(m), but efficiently computing least possible n seems to be tricky. Task can be divided, by using <a href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem" rel="nofollow">this</a> theorem (minimal n is least common multiple for all degrees for respective remainders). But when m is prime or has big enough prime divisor, and there is only one a (as opposed to computing n for many different a with the same m), we're kind of out of options. You may want to look at <a href="http://www.mast.queensu.ca/~math418/m418oh/m418og09.pdf" rel="nofollow">1</a>, <a href="http://www.mymathforum.com/viewtopic.php?f=21&t=36577" rel="nofollow">2</a>. </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