Prove each of the assertions below Any prime of the form 3n

Prove each of the assertions below Any prime of the form 3n + 1 is also of the form 6m + 1. Each integer of the form 3n + 2 has a prime factor of this form.

Solution

3(b) Let N, where N = 3n + 2 for some integer n, be given. It should be clear that N 2 (mod 3). Suppose that N has no prime factor p of the form 3n + 2. Then, for each prime factor p_i of N, we have that p_i 1 (mod 3).

To see this, consider that each p_i must be congruent to 1 or 2 (mod 3), since if p_i 0 (mod 3), then p_i = 3, but then N is divisible by 3, contradicting the assumption that N 2 (mod 3). By assumption, p_i is not congruent to 2 (mod 3), so it must be that p_i 1 (mod 3).

But if p_i 1 (mod 3), then for any positive integer power k, we have (p_i)^k 1^k = 1 (mod 3). Further, the product of all (p_i)^(k_i) in the prime factorization of N is congruent to 1 (mod 3). Hence, N 1 (mod 3). But, by assumption, N 2 (mod 3), a contradiction. Hence, N must have some prime factor such that p_i 2 (mod 3); that is, p_i = 3n+2 for some integer n.

11(b)

The proof is by contradiction,and it goes like this: assume otherwise that k is not an odd

number. That means k is even. Because it is even, k = 2n for some positive integer n. Thus

substituting 2n for k in the expression of p you get: p = 2^(2n) - 1. But 2^(2n) = 4^n. So

p = 4^n - 1. But you already knew that 3 divides 4^n - 1 for all naturals n. This means 3

divides p, and since p is a prime p must be 3. So 2^k - 1 = p = 3 ==> k = 2. Since k is not

equal to 2, p can\'t be 3. But then p is a composite number because 1, 3, and p are three

distinct factors of p, contradicting the assumption that it is a prime number. So k must

be odd.