MA-410, Spring 2025, 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, February 28, 11:59pm
   A Mersenne number is an integer of the form M_p = 2^p – 1, where p is a prime number. Please prove GCD(M_p, M_q) = 1 for primes p ≠ q. Hint: prove for integers m ≥ n > 0 that GCD(2^m – 1, 2ⁿ – 1) = GCD(2^{m mod n} – 1, 2ⁿ – 1) = 2^{GCD(m, n)} – 1.
2. Due Friday, February 28, 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 18, 11:59pm
   Using the Chinese Remainder Algorithm from class, which is based on interpolation by divided differences, compute a (positive or negative) integer N such that 32 = 2⁵ divides N–3, 27 = 3³ divides N–2, and 25 = 5² divides N+2.
4. Due Thursday, March 18, 11:59pm
   ENT, §5.2, Problem 10, (b) only, page 92. Assuming that a and b are integers not divisible by the prime p, prove the following: (b) if a^p ≡ b^p (mod p), then a^p ≡ b^p (mod p²). [Hint: a^p ≡ b^p (mod p) implies a ≡ b (mod p), hence there exists an integer k such that a = b + pk. Now a^p – b^p = (b+pk)^p – b^p. Prove that p² divides the latter expression.]
5. Due Thursday, March 18, 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.