Weekly Contest for September 27, 2011

 % cd your-pc2-directory
 % /homes/cs390cp/pc2/bin/pc2team &

Log in using your individually assigned “teamX” account and password. You can work in the current window/directory, creating a subdirectory for each problem.

• A: Light, More Light
• B: Prelude One to Carmichael Numbers -- Primality Testing
• C: Prelude Two to Carmichael Numbers -- Efficient Power Mod
• D: Carmichael Numbers
• E: Euclid Problem
• F: Prelude to Factovisors
• G: Factovisors
• H: Repackaging

Remember: If you've already solved one or more of these problems, try (1) solving again without referring to your old solution, and/or (2) using a different language (Java or C++). If you want to work on an additional problem from the book, let me know.

Hints:

• A: Find a pattern. The solution is extremely short and efficient.
• B: Repeated divisions is fine (be sure to skip even numbers after 2 and only test as large as necessary).
• C: Observe that, if k is even, n ^ k mod p is (n ^ (k/2) mod p) ^ 2 mod p. Generalize and handle the case for k odd.
• D: Combine the two preludes.
• E: The Extended Euclid Algorithm for GCD (given in the text), given in the text, solves this problem directly.
• F: Brute force factorization is fine. You'll want to keep a table of (p,e) pairs for each prime, p, that divides e times.
• G: Theorem: The highest power of p that divides n! is n/p + n/p^2 + n/p^3 …. So, p^e divides n! if this sum is at least e before n/p^k reaches 0.
• H: The text suggests using the Diophantine solution method given there. Note that you don't actually need to compute the solution, just determine whether or not a solution exists.