Number Theory

Number Theory

This page is dedicated to Shaheed Bhai Mohar Singh Ji.


Photo of classroom activity


hardy-ramanujan1

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 9171

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 9171)×Mp


Introductory Chapter

Kurt Godel 1906-78

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

Introductory I.1 Exercise I.1 Complete solutions to Exercises I.1

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:

Section I.2.1 Tautology 12-14

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

I.2.4 Introduction to proof

Video content

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

I.2.5 Divisibility proofs

Video content

  • 00:10 definition of a|b
  • 02:16 proof of a|and b|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 positive odd integers

I.4.2 Divisibility Example

Video content

  • 01:30 why use mathematical induction

I.4.3 Factorization Example

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

I.5.2 Types of sets

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:

Section I.6 Inequalities

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

I.6.7 Polynomials

Video content

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

I.6.7 Binomial Expansion

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 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

Della Avery


Chapter 1 A Survey of Divisibility

Section 1.1

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

Section 1.1.3 GCD

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

Section 1.3 pages 18-24

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

The Die Hard 3 Water Jug Solution | Blogs From Geekdom

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.jpg

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 - Wikiquote

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

Exercises 3.1 question 16

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 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

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 752x (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

Section 5.1 pages 209 -211

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

Exercises 6.2 question 14

Exercises 6.3 question 8

Exercises 6.3 question 14

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

Exercises 7.2 question 13

Exercises 7.1 question 1(h)

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.

Samir Butt

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

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.


gian-carl-rota

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.