1. [12 marks] Number theory. Prove each of the following statements. For each one, you may use the statements from previous question parts (including part (a)) as "external facts" in your proofs. You may also use the following facts, as long as you clearly refer to them: Vo.be 2, 2a 2b 21 - Va,b,c ez, a 10cc VpEN, Prime(p) (Vk, dezt, dpl d=1Vpd) Vno EN, En EN, n > no A Prime(n) (Fact 1) (Fact 2) (Fact 3) (Fact 4) (a) (Do not hand in this question part is not graded.] Prove that for every pair of integers d and n,d does not divide any number between nd and (n + 1)d, exclusive, (b) Prove that for every prime p and positive integer k, god( n) = 1 for every positive integer n between p* and pe + p. exclusive. (c) Prove that for every positive integer m, there are infinitely many natural numbers n such that godin, n + m) = 1. For this part, you must include a translation of the above statement into predicate logic, using the same structure for "infinitely mary" that we saw in the Course Notes and on Problem Set 1. Hint: Fact 4 (infinitely many primes") allows you to choose a prime number that is as large as you want (d) Prove that every prime gap is equal to 1 or is divisible by 2. (Refer to Problem Set 1 for the definition of "prime gap.) Updated Jan 30: you may use the domain Z instead of N for prime gaps in this