### Number Theory

#### This page is dedicated to Shaheed Bhai Mohar Singh Ji.

Photo of classroom activity:

**Largest known prime at present is the Mersenne prime **

**M**_{p} = 2 ^{77 232 917}*– *1

_{p}= 2

^{77 232 917}

*–*1

**This number was found in December 2017 and it has 23,249,425 digits.**

**The largest known perfect number PN is **

**PN = (****2 **^{77 232 917}*– *1)**X M**_{p}

^{77 232 917}

*–*1)

_{p}

#### Chapter 1 A Survey of Divisibility

##### Section 1.1

##### Section 1.1.2 Linear Combination Pages 6-7

##### Section 1.1.3 GCD

##### Section 1.2 Division Algorithm pages 11-18

##### Section 1.3 pages 18-24

##### Section 1.3 Euclidean Algorithm pages 24-29

##### Section 1.4 Diophantine Equations pages 30 to 36

##### Section 1.4 Diophantine Equations pages 36 to 41

##### Exercise 1.4 question 3(a) page 41

##### Exercise 1.4 question 3(a) page 41 finished off

#### Chapter 2 Primes and factorization

Section 2.1 Importance of Primes pages 45 to 47

Section 2.1 Fundamental Theorem of Arithmetic pages 47 to 53

Section 2.2 Ceiling and floor function pages 54 to 57

Section 2.2 Testing for Compositeness pages 57 to 61

Section 2.2 Primes pages 61 to 63

Section 2.3 Unsolved Problems in Number Theory pages 64 to 67

Section 2.3 Distribution of Primes pages 67 to 70

Section 2.3 Primes of 4n+1; 4n+3 pages 71 to 73

Section 2.3 Primes in an A.P. pages 73 to 76

#### Chapter 3 Theory of Modular Arithmetic

Section 3.1 Introduction to congruences pages 91-93

Section 3.1 Intro to congruences pages 94-98

Section 3.1 Intro to congruences pages 98-103

Section 3.1 Intro to congruences pages 103-4

Section 3.1 Intro to congruences pages 104-5

Section 3.1 Intro to congruences pages 106-8

The notes for this section are here:

Exercises 3.1 questions 9 and 10

Notes are here Exercises 3.1.pdf

Section 3.2 Congruent Properties of Multiplication pages 111 to 113

Section 3.2 Congruent Properties of multiplication pages 113-14

Section 3.2 Congruent Properties of multiplication pages 115-17

Section 3.3 Solving Linear Congruences pages 118 to 120

Section 3.3 Solving Linear Congruences pages 120 to 125

Section 3.3 Example 3.17 pages 125 to 126

Section 3.3 Inverse in modular arithmetic pages 126 to 128

Notes on the above are here Section 3.3

Section 3.4 Chinese Remainder Theorem pages 130 to 132

Section 3.4 Proof of the Chinese Remainder Theorem pages 133 to 136

Section 3.4.3 Applying the Chinese Remainder Theorem pages 136 to 138

Section 3.4.3 Example 3.25 Pages 138 to 140)

Notes on the above are here Section 3.4

Section 3.5 Factorization pages 141 to 144

Section 3.5 Factorization page 144 to 146

Section 3.5 Factorization by using modular arithmetic pages 146 to 147

Section 3.5 Factorization by using modular arithmetic pages 147 to 149

Here are the notes related to the above recordings:

#### Chapter 4 A Survey of Modular Arithmetic with Prime Moduli

Section 4.1 Proof of Fermat’s Little Theorem pages 153 to 156

Section 4.1.3 Applying Fermat’s Little Theorem pages 156 to 158

Applying Fermat’s Little Theorem pages 158-59

Section 4.1 Corollary to Fermat’s Little Theorem pages 159 to 162

Notes for these are here

Section 4.2 Wilson’s Theorem pages 163-65

Section 4.2 Proof of Wilson’s Theorem

Section 4.2.3 Converse of Wilson’s Theorem pages 168-69

Here are the notes Section 4.2.pdf

Section 4.3 Composite Integers pages 171-73

Section 4.3.2 Pseudoprimes pages 173-74

Section 4.3.3 Factorizing integers pages 175-77

Notes on section 4.3 are here Section 4.3.pdf

##### Chapter 5 Euler’s Generalization of Fermat’s Theorem

Section 5.1.2 Euler’s totient function for primes pages 211-14

Section 5.1.3 Phi of prime powers pages 215-17

Section 5.1.4 Euler’s totient function of any natural number pages 217-19

Section 5.1.4 Euler’s totient function examples pages 219-22

Here are the notes for section 5.1 Section 5.1.pdf

Hardy (1877 – 1947) and Ramanujan (1887 – 1920).

#### A Video about Ramanujan and Hardy

A new film about Ramanujan and Hardy

The mathematicians patterns, like a painter’s or the poet’s, must be beautiful; the ideas, like the colours or the words, must fit together in a harmonious way. Beauty is the *first test*: there is no permanent place in the world for ugly mathematics.

G.H. Hardy in A Mathematicians Apology

#### William Thurston 1946 to 2012

I think most mathematicians love mathematics for mathematics’ sake. They really do like the feeling of being in an ivory tower. For the most part, they are motivated by applications. But I believe that, whatever their personal motivation is doing for mathematics, in most cases the mathematics they generate will ultimately have significant applications. The important thing is to do mathematics. But, of course, it’s important to have people thinking about applications too.

A mathematician’s work is mostly a tangle of guesswork, analogy, wishful thinking and frustration, and proof, far from being the core of discovery, is more often than not a way of making sure that our minds are not playing tricks. Gian-Carlo Rota – 1932 to 1999.

#### Notes on Number Theory

**Corrections by Dr. Giovanna Scataglini Belghitar**

Investigation in Cryptography by Shannon O’Brien is here.

Introductory Chapter

Introductory chapter notes and exercises | Complete solutions to Introductory chapter | |

Summary of results of Introductory Chapter | Appendix A |

#### Alan Turing 1912-1954

If you are an academic and would like complete solutions to the supplementary problems then send me an email by using your university email:

k.singh@herts.ac.uk

#### Chapter 1: Introduction to Number Theory

#### Chapter 2: Primes and Their Distribution

Test on Floor and Ceiling FunctionsTest on GCD and Prime Factorization - Section 2.2

#### Chapter 3: Modular Arithmetic

**Test on modular arithmetic**

#### Chapter 4: A Survey of Linear Congruences

**Chapter 5: Eulerâ€™s Generalization of Fermatâ€™s Theorem**

#### Euler 1707 to 1783

**Test on Euler's totient Function - Section 5.1**

Chapter 6: Primitive Roots and Indices