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.