A Prime or Not a Prime? That is the Question
(2022) In Bachelor's Theses in Mathematical Sciences MATK11 20212Mathematics (Faculty of Engineering)
Mathematics (Faculty of Sciences)
- Abstract
- In this survey, we shall prove the Lucas–Lehmer primality test used to find the
Mersenne primes. A proof of the Law of Cubic Reciprocity will also be presented,
which will be applied in the proof of a generalisation of the Lucas–Lehmer primality
test. - Popular Abstract
- Among the integers, aside from maybe 0 and 1, the primes are no doubt the most interesting ones. Not only are they interesting in their own rights, but they can also be utilised to
construct mathematical objects like rings, fields, groups and so on. Going outside of mathematics, primes can be used in computer science and play an essential role in cryptography;
sensitive data online are kept safe because of primes. Primes even find their way into folklore
and mythology. Just think of the Holy Trinity, or how three 7’s means jackpot in Las Vegas,
or Friday the 13th.
Unfortunately, it remains a difficult task to check if an integer is prime. There are no
simple algorithms that immediately tells you if a number is prime or not. Of... (More) - Among the integers, aside from maybe 0 and 1, the primes are no doubt the most interesting ones. Not only are they interesting in their own rights, but they can also be utilised to
construct mathematical objects like rings, fields, groups and so on. Going outside of mathematics, primes can be used in computer science and play an essential role in cryptography;
sensitive data online are kept safe because of primes. Primes even find their way into folklore
and mythology. Just think of the Holy Trinity, or how three 7’s means jackpot in Las Vegas,
or Friday the 13th.
Unfortunately, it remains a difficult task to check if an integer is prime. There are no
simple algorithms that immediately tells you if a number is prime or not. Of course, with
some time at hand, anyone can figure out all the primes less than 100. With more time, one
can do the same for the primes less than 1000. However, there is a limit to anyone’s patience,
and for large integers, even computers are not efficient enough.
However, there are ways to test if an integer is prime, aptly named primality tests. One
such test is the Lucas–Lehmer test, a test that can check very large integers, but alas, only
tests a small portion of the integers known as the Mersenne numbers. Luckily, one can
generalise the Lucas–Lehmer test to test a larger part of the integers. This thesis will give a
proof of both the Lucas–Lehmer test and a generalised version. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9098369
- author
- Tjora, Vetle LU
- supervisor
- organization
- course
- MATK11 20212
- year
- 2022
- type
- M2 - Bachelor Degree
- subject
- keywords
- primality testing, Lucas--Lehmer, number theory, cubic reciprocity, Mersenne primes
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFMA-4137-2022
- ISSN
- 1654-6229
- other publication id
- 2022:K15
- language
- English
- id
- 9098369
- date added to LUP
- 2022-09-08 13:37:43
- date last changed
- 2022-09-08 13:37:43
@misc{9098369, abstract = {{In this survey, we shall prove the Lucas–Lehmer primality test used to find the Mersenne primes. A proof of the Law of Cubic Reciprocity will also be presented, which will be applied in the proof of a generalisation of the Lucas–Lehmer primality test.}}, author = {{Tjora, Vetle}}, issn = {{1654-6229}}, language = {{eng}}, note = {{Student Paper}}, series = {{Bachelor's Theses in Mathematical Sciences}}, title = {{A Prime or Not a Prime? That is the Question}}, year = {{2022}}, }