Prove that if (n)=n, then n is 1 or 2 Solution Let n = j * k, for some integers

Question

Prove that if (n)=n, then n is 1 or 2

Explanation / Answer

Let n = j * k, for some integers j and k both exceeding 1. 2^(n) - 1 = 2^(jk) - 1 = (2^(j))^(k) - 1. = (2^(j) - 1) [(2^(j))^(k - 1) + (2^(j))^(k - 2) + (2^(j))^(k - 3) + .. + 1]. Now, for j > 1, you have 2^(j) > 2, thus 2^(j) - 1 > 1. The other factor is a sum of powers, which can never be negative, with the smallest possible total for k > 1 being: [(2^(j))^(k - 1) + 1] = [(number greater than 2)^(k - 1) + 1]. Notice k > 1 so k - 1 > 0. = [(number greater than 2)^(number greater than 0) + 1] > 1. So, this is a product of two factors, both greater than 1. Therefore, this is composite. ----- Note that this is a one-way proof. If 2^(n) - 1 is composite, it tells you nothing about n. Examples: 2^(11) - 1 = 2048 - 1 = 2047 = 23 * 89 composite. Here n = 11 (prime). 2^(4) - 1 = 16 - 1 = 15 = 3 * 5 composite. Yet here n = 4 (composite).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.