Problem 5 of Chapter 13 of A Concise Introduction to Pure Mathematics

Prove that there are infinitely many primes in form of 4k+3.

Proof:

Assume the statement is wrong, there is a max number of primes in that form.
Then the following number should not be a prime:

N = 4*((4k1+3)*(4k2+3)*....(4km+3)) + 3

Where 4k1+3, 4k2+3....4km+3 includes all the primes in the form of 4k+3 except 3(k <> 0)

Factorize N, get N = p1*p2*p3...*pn

N co-prime with N-3, because:

4*(4k1+3)*(4k2+3)*....(4km+3)) does not have 3 as a factor (k <> 0)

A number can only take the form of one of the following:
4m, 4m+1, 4m+2,4m+3
and 4m and 4m+2 are obviously not prime

Therefore p1, p2...pn are all in forms of 4m+1

However,

p1*p2=(4m1+1)*(4m2+1) = 16m1*m2 + 4m1 + 4m2 + 1 = 4*(4m1*m2+m1+m2)+1

Therefore p1*p2 is also in form of 4m+1, continue this till pn, N=p1*p2*...*pn is
in form of 4m+1.

But N = 4*K+3.

Contradiction.

End of Proof.

Problem 8.11 of A Concise Introduction to Pure Mathmatics

Just for this question, count 1 as a prime number. A well-know result in number theory says that for every integer x>= 3, there is a prime number p such that 1/2x < p < x. Using this result and strong induction, prove that every positive integer is equal to a sum of primes, all of which are different.

Proof:

1) The statement is true for 3, 3 = 1 + 2.
2) Assume the statement is true for all s <= n
3) For n + 1, make p is a prime between 1/2(n+1) and (n + 1). then n + 1 = p + s, and s < 1/2(n + 1). According to 2) s equal to sum of different primes (p0 + p1 + p2 + ...), and since p > 1/2 (n+1) > s, p is different from (p0,p1,p2...). Therefore n + 1 is a sum of different primes.

End of Proof.