It is a popular pastime amongst mathematicians to search for primes. The latest ‘largest known prime’ is often quoted in the popular press. A common place to search for primes is amongst numbers of the form 2p − 1, where p is itself prime. The purpose of this article is to present two interesting sequences which provide rewarding classroom exercises. A list of these exercises is given and some conclusions regarding the prime-ness of the so-called Mersenne number 2p − 1 are drawn. The final test for prime-ness which we deduce was devised by Edouard Lucas in France at the end of the nineteenth century. The proof, which we have tried to break down into a sequence of elementary exercises, is due to D. H. Lehmer, who in the 1930s used his remarkable electro-mechanical machine to find the largest prime then known.