Skip to main content

LUP Student Papers

LUND UNIVERSITY LIBRARIES

A Prime or Not a Prime? That is the Question

Tjora, Vetle LU (2022) In Bachelor's Theses in Mathematical Sciences MATK11 20212
Mathematics (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:
author
Tjora, Vetle LU
supervisor
organization
course
MATK11 20212
year
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}},
}