A really trivial proof of the Lucas-Lehmer primality test

J.W. Bruce

    Research output: Contribution to journalArticle (journal)peer-review


    In the paper [1] Rosen gave a beautiful and elementary proof of the Lucas-Lehmer primality test for Mersenne numbers, i.e. those of the form Mp = 2p - 1. This test is very attractive, since it can be easily implemented on a computer, and it gives students the chance of experiencing the thrill of discovering very large (if wellknown) primes for themselves. In this article we show that it is possible to simplify Rosen's proof of the sufficiency of the test a little to eliminate any mention of algebraic numbers or questions concerning splitting of primes. In fact we only use a couple of lemmas from group theory, which are hardly worth glorifying with such a description. Of course it is the sufficiency which allows one to produce the large primes, so the half of the result we prove has its attractions. The necessity requires some basic facts concerning quadratic residues. The proof below might make a pleasant application early on in an abstract algebra course. The author was in receipt of a Fulbright award while this note was written.
    Original languageEnglish
    Pages (from-to)370-371
    JournalThe American Mathematical Monthly
    Issue number4
    Publication statusPublished - 1993


    Dive into the research topics of 'A really trivial proof of the Lucas-Lehmer primality test'. Together they form a unique fingerprint.

    Cite this