17 Dec
2003
17 Dec
'03
11:17 p.m.
I find that for the numbers I have tried, that (p-1)! mod p = (p-1) if p is prime, else it equals 0, with one exception (p=4). So if this is true (probably a standard result; it sounds familiar) then it might actually be easier to find the factorial of a larger number mod a prime than a smaller one.
Using "~" to mean congruence, and "L()" as the Legendre symbol, the general rule is: (p - 1)! ~ -L(a/p)a^((p - 1)/2) mod p. L(a/p) will equal 1 or -1, depending on whether or not a is a quadratic residue mod p. The result stems from Euler's criterion. - Mark - -- Mark Chen chen@netcom.com 415/329-6913 finger for PGP public key D4 99 54 2A 98 B1 48 0C CF 95 A5 B0 6E E0 1E 1D