I was reading Wikipedia's page on Wilson's Theorem and thought a few people might enjoy fiddling with some of the underlying ideas on a computer. Here are a few leading questions.


1) Pick a prime number p, multiply the numbers 1, 2, ..., p-1, and take the result mod p. How does the result depend on p? [Computational note: to avoid overflow issues, you can multiply a few of the numbers, take the result mod p, and multiply a few more without changing the answer. Eg. (5*9*15) mod 12 = (((5*9) mod 12) * 15) mod 12.]


2) What happens if p is not prime in (1)? Are there any exceptions to this rule? Can you devise a primality testing algorithm from these results? How good is this algorithm speed-wise?


3) Two numbers a and b are called relatively prime if their prime factorizations share no common prime factors. Eg. 10 and 6 are 2*5 and 2*3 which share the factor 2, so they are not relatively prime. The Euclidean algorithm offers a very fast method for determining if two numbers are relatively prime. In pseudocode (partly stolen from Wikipedia),

Code:
function IsRelativelyPrime(a, b)
    if gcd(a, b) = 1
        return True
    else
        return False

function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod b)
Reconsider (1): the numbers 1, ..., p-1 are each relatively prime to p since p is prime. By contrast, if p is not prime, some of the numbers 1, ..., p-1 are not relatively prime to p. Redo (2) but this time only multiply those numbers 1, ..., p-1 which are relatively prime to p. How does the result depend on p? What happens if p is the power of a prime, like 2^3 = 8? Can you find some simple rules to determine the result in advance without actually multiplying everything out?


[I'd be happy to provide results, proofs, or proof outlines. I'd certainly be interested in original proofs, though without some knowledge of number and/or group theory that's asking a lot.]