Extended Essay
Mathematics
What is modular arithmetic, and how can
it be applied to solve problems in the field
of number theory?
An essay on linear congruences and their uses
Word count: [3989]
,Contents
1 Introduction
2 Modular Arithmetic
2.1 Introduction
2.2 Operational Properties
3 Significant Theorems
3.1 The Chinese Remainder Theorem
3.2 Fermat’s Little Theorem
4 Divisibility Tests
5 Number Theory Problems
6 Conclusion
7 Appendices
8 Bibliography
2
,1 Introduction
In this essay, I will answer the research question, ‘What is modular arithmetic,
and how can it be applied to solve problems in the field of number theory?’
Initially, the basic concept of modular arithmetic will be introduced, before
establishing its foundational properties. Subsequently, I will set out two
significant theorems that are central to the topic and to the 5 original solutions
to number theory problems that I will present in the last section of my essay, the
majority of which are posed by the United Kingdom Mathematics Trust (UKMT).
A variety of sources were used in my research, including the online resources
Encyclopaedia Britannica [1] and Brilliant.org [2] and the books Concepts of
Modern Mathematics [3] and Concrete Mathematics [4].
Modular arithmetic is a topic that has tremendous significance and applicability
in pure mathematics, principally in number theory, along with practical uses in
cryptography and checksum calculations. Having been a keen participant in
UKMT Mathematics Challenges since I was 13, I find modular arithmetic
particularly compelling as it can be utilised in order to produce succinct and
elegant solutions to the types of questions I have enjoyed doing for several years.
The aim of this essay is two-fold: to outline what modular arithmetic is and to
clearly demonstrate its usefulness in solving number theory problems, as
evidenced by my own original solutions.
3
, 2 Modular Arithmetic
2.1 Introduction
Established by Carl Friedrich Gauss in his 1801 book ‘Disquisitiones
Arithmeticae’ (Arithmetical Investigations) [3], modular arithmetic is a system of
arithmetic solely concerned with the remainders of integers when they are
divided by a chosen value, called the modulus. Gauss introduced the following
notation:
Let a, b, r ∈ ℤ and n ∈ ℤ+.
The remainder, r, when a is divided by the modulus, n, is denoted by:
𝑎 ≡ 𝑟 (mod 𝑛).
If a and b have the same remainder when divided by n, they are congruent
modulo n. This is written as:
𝑎 ≡ 𝑏 (mod 𝑛)
or
𝑎 mod 𝑛 = 𝑏 mod 𝑛 .
For example,
16 ≡ 9 (mod 7)
because 16 and 9 both leave a remainder of 2 when divided by 7.
4
Mathematics
What is modular arithmetic, and how can
it be applied to solve problems in the field
of number theory?
An essay on linear congruences and their uses
Word count: [3989]
,Contents
1 Introduction
2 Modular Arithmetic
2.1 Introduction
2.2 Operational Properties
3 Significant Theorems
3.1 The Chinese Remainder Theorem
3.2 Fermat’s Little Theorem
4 Divisibility Tests
5 Number Theory Problems
6 Conclusion
7 Appendices
8 Bibliography
2
,1 Introduction
In this essay, I will answer the research question, ‘What is modular arithmetic,
and how can it be applied to solve problems in the field of number theory?’
Initially, the basic concept of modular arithmetic will be introduced, before
establishing its foundational properties. Subsequently, I will set out two
significant theorems that are central to the topic and to the 5 original solutions
to number theory problems that I will present in the last section of my essay, the
majority of which are posed by the United Kingdom Mathematics Trust (UKMT).
A variety of sources were used in my research, including the online resources
Encyclopaedia Britannica [1] and Brilliant.org [2] and the books Concepts of
Modern Mathematics [3] and Concrete Mathematics [4].
Modular arithmetic is a topic that has tremendous significance and applicability
in pure mathematics, principally in number theory, along with practical uses in
cryptography and checksum calculations. Having been a keen participant in
UKMT Mathematics Challenges since I was 13, I find modular arithmetic
particularly compelling as it can be utilised in order to produce succinct and
elegant solutions to the types of questions I have enjoyed doing for several years.
The aim of this essay is two-fold: to outline what modular arithmetic is and to
clearly demonstrate its usefulness in solving number theory problems, as
evidenced by my own original solutions.
3
, 2 Modular Arithmetic
2.1 Introduction
Established by Carl Friedrich Gauss in his 1801 book ‘Disquisitiones
Arithmeticae’ (Arithmetical Investigations) [3], modular arithmetic is a system of
arithmetic solely concerned with the remainders of integers when they are
divided by a chosen value, called the modulus. Gauss introduced the following
notation:
Let a, b, r ∈ ℤ and n ∈ ℤ+.
The remainder, r, when a is divided by the modulus, n, is denoted by:
𝑎 ≡ 𝑟 (mod 𝑛).
If a and b have the same remainder when divided by n, they are congruent
modulo n. This is written as:
𝑎 ≡ 𝑏 (mod 𝑛)
or
𝑎 mod 𝑛 = 𝑏 mod 𝑛 .
For example,
16 ≡ 9 (mod 7)
because 16 and 9 both leave a remainder of 2 when divided by 7.
4
