PMATH 340 Number Theory, Assignment 3 Due: Tues July 7 Read Chapter 5 in the Lecture Notes, and work on the Exercises for Chapter 5 in the Practice Problems. Then solve each of the following problems. 1: (a) Use Fermat’s Little Theorem and the Square and Multiply Algorithm to show that the integer 2479 is not prime (without testing each prime p ≤ √2479 to see if is a factor). (b) Determine whether 221 is a pseudo-prime to the base 5. (c) Find two different values of p such that 7 · 19 · p is a Carmichael number. 2: (a) Let a ≥ 2 and m ≥ 1 be integers. Show that if am + 1 is prime, then a must be even and m must be a power of 2. (b) Show that there are infinitely many primes of the form 12k + 7 with k ∈ Z. (c) It is conjectured that for every integer n ≥ 1 there is a prime p with n2 < p < (n+ 1)2. Show that if this conjecture is true then pi(x) ≥ ⌊√x⌋ for all x ≥ 2. 3: (a) Find the smallest positive integer k with the property that there exists a prime p such that the five numbers p, p+ k, p+ 2k, p+ 3k and p+ 4k are all prime. (b) Find the smallest positive integer k with the property that there exists a prime p such that the six numbers p, p+ k, p+ 2k, p+ 3k, p+ 4k and p+ 5k are all prime.
