This master's thesis explores Mersenne primes and the Lucas–Lehmer test. Mersenne primes, which take the form 2^p-1, where p is a prime number, are the largest known prime numbers. Their primality is verified using the Lucas–Lehmer test, which is formulated as an algorithm in the form of a recursive sequence. In this thesis, we prove the validity of the test in two distinct ways. First, we employ only elementary techniques from number theory, then we present a second proof using algebraic methods. Along the way, we introduce all the necessary concepts from number theory, with particular emphasis on linear and quadratic congruences. We also provide a complete proof of the Law of Quadratic Reciprocity, which constitutes one of the key components in establishing the correctness of the Lucas–Lehmer test.
|
