Question

Hello, can someone show me the correct steps in solving this number theory practice question?

(Please be legible).

Thank you.

21. . Let a and n be natural numbers such that n 1 and a" - 1 is prime a. Prove that a-2. b. Prove that n must be prime. [Hint: Use your result from part a.]

Answer 1

Let a, n elementof N and a^n - 1 is prime. Now, a) a^n - 1 = (a - 1) (a^n - 1 + a^n - 2 + Ellipsis + a + 1). Then (a - 1) divides a^n - 1. Hence a^n - 1 is prime if and only if a - 1 = 1 = > a = 2. Hence, we must have that a = 2. b) From (a), we have that a^n - 1 = 2^n - 1 is prime. Suppose that n is not prime. Then n = m k for some m, k elementof Z - {1}. Then, 2^n - 1 = 2^m k - 1 = (2^m)^k - 1 = (2^m - 1) ((2^m)^k - 1 + (2^m)^k - 2 + Ellipsis + 2^m + 1) (2^m - 1) divides w^n - 1 whenever n is composite. But, this is a contradiction to the fact that 2^n - 1 is prime.