2 expanded posts ยท every known parent and child
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. Hal
> 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