# Number Theory

This page is dedicated to Shaheed Bhai Mohar Singh Ji.

Photo of classroom activity

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

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

A video about Ramanujan and Hardy

Another film about Ramanujan and Hardy

Largest known prime at present is the Mersenne prime

M_{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)×M_{p}

**Note that all the video topics on this page have subtitles.**

### Introductory Chapter

Kurt Godel 1906-78

Here are the video topics and notes for the Introductory Chapter:

Videos for Section I.1 are below:

Introductory I.1 Propositional Logic pages 1-6

Video content:

- 01:31 symbolic form
- 04:10 negation
- 07:49 and connective
- 10:06 or connective
- 13:49 combining propositions

Section I.1 Propositional Logic pages 6-9

Video content

- 02:46 implication truth table
- 06:03 using implication in proof

Here are the written notes for these videos Section I.1

Introductory I.2 Introduction to Proof | Exercise I.2 | Complete solutions to Exercise I.2 |

Videos for Section I.2 are below:

Video content

- 00:29 definition of tautology
- 06:41 P⇒Q and Q⇒R then P⇒R

Section I.2.2 and I.2.3 Converse and if and only if 14-16

Video content

- 01:07 truth table for converse
- 04:02 egg example
- 06:42 if and only if

Video content

- 00:59 what is a mathematical proof
- 02:40 definition of an even number
- 09:16 definition of an odd number

Video content

- 00:10 definition of
*a|**b* - 02:16 proof of
*a|**b*and*b|**c*then*a|**c* - 06:40 summary of section I.2

Here are the written notes for these videos Section I.2

Introductory I.3 Proofs | Exercises I.3 | Complete Solutions to Exercise I.3 |

Videos for Section I.3 are below:

Section 1.3.1 If and only if proofs

Video content

- 01:32 how to construct an if and only if proof
- 07:22 proof of I.7

Section I.3.2 and I.3.3 Proof by contrapositive and WLOG

Video content

- 01:35 truth table of the converse of P⇒Q
- 05:30 Example 22
- 08:08 Without Loss of Generality – WLOG

Section I.3.4, I.3.5 and I.3.6 Proof by contradiction

Video content

- 00:07 Hardy and chess
- 02:34 procedure for proof by contradiction
- 04:30 negation examples
- 07:21 Fermat’s last theorem and Andrew Wiles
- 08:45 Pigeonhole Principle

Section I.3.6 Lemma and √2 is irrational

Video content

- 01:31 definition of a rational number
- 04:06 proof of √2 is not a rational number
- 09:08 irrational number
- 10:34 summary of section I.3

Here are the written notes for videos of Section I.3

Introductory I.4 Principle of Mathematical Induction | Exercise I.4 | Complete Solutions to Exercise I.4 |

Videos for Section I.4 are below:

Section I.4.1 Principle of Mathematical Induction

Video content

- 02:30 domino effect
- 04:06 sum of the first
*n*positive integers - 12:10 sigma notation, ∑
- 12:37 sum of the first
*n*positive odd integers

Video content

- 01:30 why use mathematical induction

Video content

- 02:59 difference between identity and equation
- 13:52 what is meant by a corollary
- 15:46 summary of section I.4

Here are the written notes for videos of Section I.4

Introductory I.5 Joy of Sets | Exercise I.5 | Complete solutions I.5 |

Videos for Section I.5 Joy of Sets are below:

Section I.5.1 Introduction to set theory

Video content

- 01:15 notation for sets
- 07:26 cardinality of a set

Video content

- 00:53 different types of numbers
- 03:32 reals in two flavours; rational and irrational

I.5.3 to I.5.5 Venn diagrams and set operations

Video content

- 00:35 John Venn
- 02:16 Venn diagrams
- 03:12 union of sets
- 05:06 intersection of sets
- 08:37 complement of a set

I.5.6 and I.5.7 Subsets and Well Ordering Principle

Video content

- 01:01 definition of subset
- 02:52 examples of subsets
- 04:16 difference between strong and ordinary induction
- 05:28 well-ordering principle
- 06:23 summary of section I.5

Here are the written notes for videos of Section I.5

Introductory I.6 Inequalities, modulus function and polynomials | Exercises I.6 | Complete Solutions to Exercise I.6 |

Videos for Section I.6 are below:

Video content

- 02:46 properties of real numbers
- 06:11 transitive property of inequality and its proof
- 10:02 inequality changes
- 14:02 a real square number ≥ 0

Section I.6 The modulus function

Video content

- 01:48 graph of mod
*x* - 04:06 distance function
- 08:40 solve inequality of the modulus function

Video content

- 01:08 meaning of product notation, ∏
- 05:22 completing the square
- 14:19 minimum of a quadratic

Video content

- 00:36 pattern of the binomial expansion
- 02:08 Pascal’s triangle
- 07:08 summary of section I.6

Here are the written notes for videos on Section I.6

Notes on the complete Introductory Chapter:

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

Summary of results of Introductory Chapter | Appendix A |

The remaining video topics are from the book:

The companion website is at the following link here.

This book examines the patterns and beauty of positive integers by using elementary methods. It discusses some of the outstanding problems which have not been resolved even after hundreds of years of trying. A challenging problem, even for powerful computers, is factorizing integers and the book highlights some methods that are used to simplify this. We factorize integers of the type *x ^{2} ± a* and solve the equivalent non – linear Diophantine equation

*x*±

^{2}*a =*

*py*where

*p*is prime. To see if such equations have integer solutions, we use the ‘Law of Quadratic Reciprocity’ which is one of the most powerful results in number theory. The methods of factorization use a new arithmetic called ‘clock arithmetic’ which also helps in finding the last few digits of a large number without writing down all the digits. The book applies clock arithmetic to test whether a given number is prime or composite. We conclude by showing one of the great results of mathematics that a prime number which leaves a reminder of one after dividing by four can be written as the sum of two squares. However, a prime number which leaves a remainder of three after dividing by four

*cannot*be written as the sum of two squares. Most of the results in the book are placed in a historical context.

Della Avery, Agnes Bonivart and Dr Laurence Taylor made significant contribution to improving the book.

Agnes Bonivart

#### Chapter 1 A Survey of Divisibility

Video content

- 01:48 notation for divisibility
- 05:10 properties of divisors
- 08:24 τ function

Section 1.1.2 Linear Combination Pages 6-7

Video content

04:45 linear combination theorem

06:48 extension of the theorem

Video content

- 02:22 definition of gcd
- 10:17 important property of the gcd
- 16:56 summary of section 1.1

Section 1.2 Division Algorithm pages 11-18

Video content

- 03:39 quotient and remainder
- 05:53 applying the division algorithm
- 16:33 summary of section 1.2

Video content

- 01:08 computers
- 05:26 Bezout’s Identity
- 07:00 relatively prime (coprime)
- 08:15 Euclid’s lemma
- 13:19 biography of Euclid

Section 1.3 Euclidean Algorithm pages 24-29

Video content

- 03:29 procedure of Euclid’s Algorithm
- 09:55 solving linear equations
- 15:04 Diophantine equations

Section 1.4 Diophantine Equations pages 30 to 36

A scene from Die Hard

Video content

- 00:32 Die Hard
- 04:06 Diophantus
- 10:58 general Diophantine equations

Section 1.4 Diophantine Equations pages 36 to 41

Video content

- 05:58 how to find solutions of a linear Diophantine equation
- 13:38 real-life example

#### Chapter 2 Primes and factorization

Section 2.1 Importance of Primes pages 45 to 47

Video content

- 01:32 definition of a prime and composite number
- 04:14 public-key encryption

Section 2.1 Fundamental Theorem of Arithmetic pages 47 to 53

Video content

- 01:53 building blocks of numbers
- 02:33 properties of primes
- 15:10 fundamental theorem of arithmetic
- 18:35 summary of section 2.1

Section 2.2 Ceiling and floor function pages 54 to 57

Video content

- 02:41 definition of floor function
- 06:33 graph of floor function
- 07:08 definition of ceiling function
- 10:19 graph of ceiling function

Section 2.2 Testing for Compositeness pages 57 to 61

Video content

- 03:21 test for compositeness
- 08:58 test for primality
- 12:17 easier test

Section 2.2 Primes pages 61 to 63

Video content

- 00:21 Eratosthenes
- 04:25 notation π(
*x*) - 05:24 proof there are infinitely many primes
- 12:30 summary of section 2.2

Section 2.3 Unsolved Problems in Number Theory pages 64 to 67

Yitang Zhang 1955-present

Video content

- 00:36 Fermat’s Last Theorem
- 02:12 twin prime conjecture
- 05:48 Lagrange’s conjecture
- 06:54 Goldbach’s conjecture
- 10:09 Landau’s conjecture

Section 2.3 Distribution of Primes pages 67 to 70

Video content

- 01:31 Lucas prime
- 02:22 Electronic Frontier Foundation
- 05:04 graph of π(
*x*) - 06:05 prime gap
- 09:16
*n*consecutive composite integers

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

Video content

- 04:32 odd primes
- 06:06 product of primes which look like 4
*n*+1 - 09:38 proof of infinitely many primes which look like 4
*n*+3

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

Video content

- 00:20 biography of Dirichlet
- 02:34 analytic number theory (onion milkshake)
- 04:50 Dirichlet’s theorem
- 08:28 generating primes
- 11:06 summary of section 2.3

**Test on Floor and Ceiling FunctionsTest on GCD and Prime Factorization – Section 2.2**

#### Chapter 3 Theory of Modular Arithmetic

Carl Friedrich Gauss 1777-1855

Section 3.1 Introduction to congruences pages 91-93

Video content

- 03:23 modulo
*n* - 06:06 3rd September 1939
- 12:09 definition of congruence
- 13:11 Gauss

Section 3.1 Intro to congruences pages 94-98

Video content

- 00:57
*a≡*0 (mod*n*) - 04:12 Division Algorithm and congruence
- 13:06 definition of a complete system of residues
- 20:12 modulo 5 clock

Section 3.1 Intro to congruences pages 98-103

Video content

- 06:26 incongruent
- 07:01 properties of congruences
- 15:18 applying to clock arithmetic

Section 3.1 Intro to congruences pages 103-4

Video content

- 00:18 applying modular arithmetic to a factorial question
- 06:10 adding and multiplying by
*c*

Section 3.1 Intro to congruences pages 104-5

Video content

- 01:06 rules of indices in modular arithmetic
- 03:18 evaluating the last digit of 3
^{101}

Section 3.1 Intro to congruences pages 106-8

Video content

- 04:44 polynomials in modular arithmetic
- 05:06 testing for divisibility by 9
- 07:24 summary of section 3.1

The notes for this section are here: section 3.1

Exercises 3.1 questions 9 and 10

Video content

- 01:29 last digit of powers of 100
- 08:44 last digit of 2014
^{2014}

Video content

- 01:03 applying Division Algorithm

Notes are here Exercises 3.1

Section 3.2 Congruent Properties of multiplication pages 113-14

Video content

- 01:51 linear congruence
- 04:58 general cancellation law
- 07:43 cancellation law with prime modulo

Section 3.2 Congruent Properties of multiplication pages 115-17

Video content

- 02:34 relatively prime
- 06:08 examining
*a×*b≡0 (mod*p*) and*a²≡**b² (*mod p)

Notes on section 3.2 are here Section 3.2

Section 3.3 Solving Linear Congruences pages 118 to 120

Video content

- 04:31 same solution
- 08:56 least non-negative residues
- 16:08 no solution

Section 3.3 Solving Linear Congruences pages 120 to 125

Video content

- 01:05 criteria for solutions of linear congruences
- 15:56 number of incongruent solutions
- 25:24 using the formula to solve linear congruences

Section 3.3 Example 3.17 pages 125 to 126

Video content

- 05:31 finding the other solution

Section 3.3 Inverse in modular arithmetic pages 126 to 128

Video content

- 04:52 inverse in modular arithmetic
- 06:54 definition of inverse in modular arithmetic
- 11:45 inverse does not exist
- 14:20 self inverse

Notes on the above are here Section 3.3

Section 3.4 Chinese Remainder Theorem pages 130 to 132

Video content

- 01:39 soldiers problem
- 03:20 simultaneous congruences
- 11:04 equating equations

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

Video content

- 01:09 pairwise prime
- 03:18 statement of the Chinese Remainder Theorem
- 04:13 existence of solutions
- 13:24 uniqueness of solutions

Section 3.4.3 Applying the Chinese Remainder Theorem pages 136 to 138

Video content

- 03:50 checking pairwise prime
- 12:40 substituting into the formula
- 15:42 unique solution

Section 3.4.3 Example 3.25 Pages 138 to 140)

Video content

- 01:30 getting rid of the coefficient
- 11:45 substituting into the formula
- 16:06 summary of the Chinese Remainder Theorem

Notes on the above are here Section 3.4

Three questions on modular arithmetic

Section 3.5 Factorization pages 141 to 144

Video content

- 01:44 website security
- 06:15 how long does it take to factorize an integer
- 06:57 RSA
- 09:29 difference of two squares
- 11:02 perfect square
- 15:07 factorizing 13 081

An introduction to the mathematics behind the RSA algorithm by Jamie Cassar is here.

Jamie Cassar

Section 3.5 Factorization page 144 to 146

Video content

- 00:19 triumvirate of French mathematicians
- 02:07 factorizing 12 371
- 07:49 procedure for Fermat factorization
- 10:51 identity

Section 3.5 Factorization by using modular arithmetic pages 146 to 147

Video content

- 00:22 non-trivial factor
- 01:25 factorization theorem
- 04:20 proof of the factorization theorem

Section 3.5 Factorization by using modular arithmetic pages 147 to 149

Video content

- 00:50 factorizing 12 349
- 06:07 matching up squares

Here are the notes related to the above recordings: Section 3.5

**Test on modular arithmetic**

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

Fermat 1601-65

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

Video content

- 00:56 evaluating 7
^{52}*≡**x*(mod 11) - 07:01 the remainder of 3
^{101}after dividing by 31

Applying Fermat’s Little Theorem pages 158-59

Video content

- 00:05 inverse using F
*l*T - 04:27 solving a linear congruence using F
*l*T

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

Video content

- 02:59 showing the product of two consecutive integers is even
- 06:11 pseudoprime
- 08:56 the converse of F
*l*T is false - 10:06 Carmichael number
- 11:48 infinitely many Carmichael numbers

Notes for these are here Section 4.1

Section 4.2 Wilson’s Theorem pages 163-65

Video content

- 02:24 John Wilson
- 03:06 Ibn al_haytham
- 07:15 multiplicative inverse
- 08:09 evaluating
*x≡*12! (mod 13)

Section 4.2 Proof of Wilson’s Theorem

Video content

- 00:48 lemma to prove Wilson’s Theorem
- 03:09 statement of Wilson’s Theorem
- 03:47 considering the primes 2 and 3
- 07:24 residues which are not self invertible
- 08:58 pairing up the residues
- 11:14 example of using Wilson’s Theorem

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

Video content

- 00:53 proof by contradiction
- 02:19 applying without loss of generality (WLOG)
- 07:37 general result

Here are the notes Section 4.2

Section 4.3 Composite Integers pages 171-73

Video content

- 01:10 test for compositeness
- 10:13 general Fermat’s composite test
- 11:24 showing that 4369 is composite

Section 4.3.2 Pseudoprimes pages 173-74

Video content

- 03:21 definition of a pseudoprime
- 03:53 showing 91 is a base 3 pseudoprime
- 08:56 smallest pseudoprime bases 3, 5 and 7

Section 4.3.3 Factorizing integers pages 175-77

Video content

- 00:50 using an algebraic identity
- 03:10 factorizing 2
^{18}–1 = 262 143 - 10:44 converse of Proposition (4.9)
- 11:06 be careful of statements

Notes on section 4.3 are here Section 4.3

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

Euler 1707 to 1783

Video content

- 02:50 Euler’s totient or φ(n) function
- 06:49 probability of a number is relatively prime
- 07:13 definition of φ(n)
- 08:43 Cardinality of a set
- 10:52 example 5.1

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

Video content

- 00:08 brief biography of Euler
- 01:47 Euler totient function of a prime
- 10:09 Euler totient function of a prime power
- 10:57 example 5.2
- 14:15 example 5.3

Section 5.1.3 φ of prime powers pages 215-17

Video content

- 02:47 cardinality
- 03:52 example 5.4
- 10:48 limitations of the formula

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

Video content

- 01:04 Euler totient function is multiplicative
- 05:36 extension of Euler’s totient function
- 11:33 Euler totient function of an integer in prime decomposition

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

Video content

- 01:05 explanation of φ(n) for various n values
- 10:40 graph of Euler’s totient function
- 11:56 table of values
- 12:24 proof of φ(n) is always even for n>2
- 17:39 summary of section 5.1

Here are the notes for section 5.1 Section 5.1

**Test on Euler’s totient Function – Section 5.1**

An investigation into how Euler solved the Basel problem by Chloe Huxter is here.

An investigation into Euler and his contribution to graph theory by Molly Hurley is here.

##### Chapter 6 Primitive Roots and Indices

Exercises 6.1 question 8 and 6.2 question 13

Here are the notes on these exercises Exercises on chapter 6

##### Chapter 7 Quadratic Residues

Exercises 7.1 questions 4 and 5 and Exercises 7.1 questions 4 and 5

The notes for these exercises are here exercises on chapter 7

Investigation in Cryptography by Shannon O’Brien is here.

Shanon O’Brien

An investigation into Cryptography with Microsoft Excel by Samir Butt is here.

Introduction into Cryptography by Sam Worton is here.

Sam Worton

A good account of the history of mathematics is MacTutor History of Mathematics which is here.

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.

#### Alan Turing 1912-1954

A film about the life of Alan Turing is below: