MA-410, Spring 2024, Homework 2, due as indicated for each problem.

All solutions must be submitted on the Moodle web site for the class at wolfware.ncsu.edu. You may upload a photo of your handwritten solution or a file of your typed solution.
Note my office hours on my schedule.

1. Due Friday, March 1, 11:59pm
   Please prove for all positive integers M, N that GCD(10^M – 1, 10^N – 1) = 10^{GCD(M, N)} – 1.
2. Due Friday, March 1, 11:59pm
   Let the Fermat numbers be F_n= 2²ⁿ + 1 for integers n ≥ 0. Please prove that 2^F_n-1 ≡ 1 (mod F_n) for all n ≥ 0. [cf. ENT, §5.2, Problem 15(b), page 93.]
3. Due Thursday, March 7, 11:59pm
   Using the Chinese Remainder Algorithm from class, which is based on interpolation by divided differences, compute an integer N such that 32 = 2⁵ divides N–1, 27 = 3³ divides N and 25 = 5² divides N+1.
4. Due Thursday, March 7, 11:59pm
   ENT, §5.2, Problem 12, page 93. Prove that if p is an odd prime and k is an integer satisfying 1 ≤ k ≤ p–1, then the binomial coefficient $\left(\genfrac{}{}{0ex}{}{\mathrm{p–1}}{\mathrm{k }}\right)$ ≡ (–1)^k (mod p). Hint: induction on k.
5. Due Thursday, March 7, 11:59pm
   ENT, §5.2, Problem 19, page 93. Prove that if 6k+1, 12k+1 and 18k+1 are all prime numbers, then (6k+1)(12k+1)(18k+1) is a Carmichael number. Example: 1729 = 7 × 13 × 19.
   Bonus addition:
   If 36k+1 is also a prime number, then (6k+1)(12k+1)(18k+1)(36k+1) is an additional Carmichael number. Example: 63973 = 7 × 13 × 19 × 37.