Although ancient Chinese mathematicians did good work coming up with their remainder theorem, they did not always get it right. They had a test for primality. The test said that n is prime if and only if n divides (2^n - 2).
a. Give an example that satisfies the condition using an odd prime.
b. The condition is obviously true for n = 2. Prove that the condition is true if n is an odd prime (proving the if condition).
c. Give an example of an odd n that is not prime and that does not satisfy the condition. You can do this with nonprime numbers up to a very large value. This misled the Chinese mathematicians into thinking that if the condition is true then n is prime.
d. Unfortunately, the ancient Chinese never tried n = 341, which is nonprime (341 = 11 * 31), yet 341 divides 2^341 - 2 without remainder. Demonstrate that 2341  2 (mod 341) (disproving the only if condition). Hint: It is not necessary to calculate 2^341; play around with the congruences instead.