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
Mp = 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)×Mp
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:
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 x2 ± a and solve the equivalent non – linear Diophantine equation x2 ± 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 4n+1
- 09:38 proof of infinitely many primes which look like 4n+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 3101
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 20142014
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
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 752 ≡ x (mod 11)
- 07:01 the remainder of 3101 after dividing by 31
Applying Fermat’s Little Theorem pages 158-59
Video content
- 00:05 inverse using FlT
- 04:27 solving a linear congruence using FlT
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 FlT 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 218 –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
Section 4.4 Mersenne Numbers page 182-84
Video content
- 02:44 brief biography of Father Mersenne
- 07:55 Mersenne’s list of primes
- 09:50 Frank Cole factorizes a Mersenne prime (number)
- 11:00 John Watkins book
- 13:03 Great Internet Mersenne Prime Search
Section 4.4.2 Factorizing Mersenne numbers page 184-86
Video content
- 00:43 deficiency of the square root method for factorizing
- 01:43 examining the factors of 2n ±1
- 13:14 example 4.17
Section 4.4.2 Factorizing Mersenne numbers page 186-88
Video content
- 00:33 types of primes dividing 2n – 1 or 2n + 1
- 02:42 example 4.18
- 07:13 example 4.19
Section 4.4.3 Germain primes page 188-190
Sophie Germain 1776-1831
Video content
- 00:33 definition of Germain prime
- 01:48 brief biography of Sophie Germain
- 05:12 prime index does not imply 2p – 1 is prime
- 12:21 example 4.20
Section 4.4.3 Germain primes pages 191-93
Video content
- 00:30 composite Mersenne numbers
- 03:06 an efficient way to factorize Mersenne numbers
- 05:40 Dirichlet’s Theorem
- 08:28 example 4.21
- 17:05 summary of section 4.4
The notes are attached for this section are here Section 4.4
Section 4.5 Perfect Numbers pages 195-98
Video content
- 01:17 largest prime
- 02:30 Lucas Lehmer test
- 04:14 proper factor
- 06:15 definition of a perfect number
- 08:21 abundant and deficient number
- 10:58 perfect number with Mersenne prime as a factor
- 14:22 largest perfect number
Section 4.5 Perfect Numbers page 198-200
Video content
- 00:23 sum of geometric series
- 01:24 list of divisors
- 11:06 collecting all the proper factors
- 13:46 converse of the theorem
Section 4.5.4 The sigma function pages 200-205
Video content
- 00:37 definition of the sigma function, σ(n)
- 06:03 sigma of a perfect number
- 07:19 definition of a multiplicative function
- 16:10 evaluating σ(945)
- 20:28 summary of section 4.5
Here are the notes for section 4.5: Section 4.5
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: