Number Theory :

The Queen of
Mathematics

Robin Wilson

Open University and Oxford,

and Gresham College, London
 Some prime figures
Euclid
Fermat

Euler Gauss

Gauss: Mathematics is the queen of the sciences

and number theory is the queen of mathematics
 What is number theory?
Number theory is the branch of mathematics
that’s primarily concerned with
our counting numbers, 1, 2, 3, . . . .
Particularly important are prime numbers,
the ‘building blocks’ of our number system,
whose only factors are themselves and 1:
prime: 11, 13, 17, 19
non-prime: 15 = 3 × 5, 18 = 2 × 9 = 2 × 3 × 3,
91 = 7 × 13, 323 = 17 × 19
2047? 30,031? 4,294,967,297 ?
 Some questions
• Is 4,294,967,297 prime?
• Are any of the numbers 11, 111, 1111, 11111, . . .
perfect squares?
• In which years does February have five Sundays?
• How many right-angled triangles with whole-number
sides have a side of length 29?
• Can one construct a regular polygon with 100 sides
if measuring is forbidden?
• How many shuffles are needed to restore the order
of the cards in a pack with two Jokers?
• How do prime numbers help to keep our credit cards
secure?
 Four topics
Prime numbers
Euclid’s theorem; Dirichlet’s theorem; Mersenne primes;
Fermat primes; a problem in geometry
Perfect squares
results on squares; right-angled triangles; two results of Fermat
Clock arithmetic
modular arithmetic; calendar problems
Fermat & Euler’s theorems
counting necklaces, shuffling cards; protecting your credit cards
 Prime
numbers
Every number
can be written
in only one way
as a product of
primes.

60 = 2 × 2 × 3 × 5 (or 2 × 5 × 3 × 2, etc.)
But 1 is not a considered a prime:
6 = 2×3 = 2×3×1 = 2×3×1×1 ...
 Euclid’s theorem
(Elements, Book IX, Prop 20)
The list of primes goes on for ever
 Euclid’s theorem
The list of primes goes on for ever
 Euclid’s theorem
The list of primes goes on for ever
For suppose that the ONLY primes are
p1, p2, p3, . . . , pn, and consider the number
N = (p1 × p2 × p3 × . . . × pn) + 1.
Then N cannot be divided by any of these primes.
So N must be a new prime, or a product of new primes.
This contradicts the fact that we could list them all.
Examples:
• If the only known primes were 2, 3, 5 and 7,
then N = (2 × 3 × 5 × 7) + 1 = 211 (a new prime)
• If the only known primes were 2, 3, 5, 7, 11, 13,
then N = (2 × 3 × 5 × 7 × 11 × 13) + 1
= 30,031 = 59 × 509 (two new primes)
 Generalising Euclid’s result
Using Euclid’s method, we can prove that:
There are infinitely many primes of the form 4n + 3:
3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, . . .
We can also prove that:
There are infinitely many primes of the form 4n + 1:
5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, . . . ,
. . . but not of the form 4n + 2, because these are all
divisible by 2.
 Dirichlet’s theorem (1837)
So we can prove that:
There are infinitely many primes of the form 4n + 3:
and also that:
There are infinitely many primes of the form 4n + 1:
but not of the form 4n + 2.
Dirichlet’s theorem: If a and b have no factors in common,
then there are infinitely many primes of the form an + b.
For example, when a = 10 and b = 9:
there are infinitely many primes of the form 10n + 9
– that is, there are infinitely many primes ending with 9
[19, 29, 59, 79, 89, 109, 139, . . .]
 Mersenne primes
Mersenne numbers are numbers of the form 2n – 1.
Some Mersenne numbers are prime:
22 – 1 = 3, 23 – 1 = 7, 25 – 1 = 31, 27 – 1 = 127, . . .
Others are not:
24 – 1 = 15, 26 – 1 = 63, 28 – 1 = 255, 29 – 1 = 511, . . .

Is it true that 2n – 1 is prime if and only if n is prime?

If n is not prime, then nor is 2n – 1.
But if n is prime, must 2n – 1 be prime?
NO: if n = 11, then 211 – 1 = 2047 = 23 × 89.
All recently found primes are Mersenne primes.
51 Mersenne primes are known: the latest (2018) is
282,589,933 – 1 with almost 25 million digits.
 Perfect numbers
A number N is perfect if it’s the sum of all its proper factors.
6 is perfect because 6 = 1 + 2 + 3,
28 is perfect because 28 = 1 + 2 + 4 + 7 + 14,
The next two perfect numbers are 496 and 8128,
and then there are no more until 33,550,366.
Now 6 = 2 × 3 = 21 × (22 – 1); 28 = 4 × 7 = 22 × (23 – 1);
496 = 16 × 31 = 24 × (25 – 1); 8128 = 64 × 127 = 26 × (27 – 1);
33,550,336 = 4096 × 8191 = 212 × (213 – 1)
Euclid: if 2n – 1 is prime, then N = 2n–1 x (2n – 1) is perfect.
Does this give us all perfect numbers?
Euler: It gives us all even perfect numbers
but no-one knows whether there are any odd perfect numbers.
 Fermat primes
Let F(n) = 2N + 1, where N = 2n
Conjecture: F(n) is prime for all n
F(0) = 21 + 1 = 3
F(1) = 22 + 1 = 5
F(2) = 24 + 1 = 17
F(3) = 28 + 1 = 257
F(4) = 216 + 1 = 65,537
But is F(5) = 232 + 1 = 4,294,967,297 prime?
 Fermat primes
Let F(n) = 2N + 1, where N = 2n
Conjecture: F(n) is prime for all n
F(0) = 3, F(1) = 5, F(2) = 17, F(3) = 257,
F(4) = 65,537.
But is F(5) = 232 + 1 = 4,294,967,297 prime?
Euler: No, it is 641 × 6,700,417
Moreover, no other Fermat primes
have ever been found . . .
Constructing
triangles

Constructing an equilateral triangle

Given the line AB, draw the circle
with centre A and radius AB,
and the circle with centre B and radius BA.
These circles meet at the point C.
Draw the lines AC and BC.
Then ABC is an equilateral triangle.
 Constructing
hexagons

Constructing a regular hexagon

Draw a circle with centre O and radius OA.
With the point of the compasses at A and radius
OA, mark the point B on the circle.
Repeat to get the points C, D, E, F .
Then ABCDEF is a regular hexagon.
 Which polygons can we draw?
We can draw regular polygons with n sides
when n = 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, . . .
but not when n = 7, 9, 11, 13, 14, 18, 19, . . .
Gauss then drew n = 17, and proved:
One can draw a regular polygon
with n sides if and only if n is
a power of 2 × unequal Fermat primes.
[3, 5, 17, 257, 65537]
Yes: 30 = 2 × 3 × 5, 32 = 25, 34 = 2 × 17, 40 = 23 × 5, . . .
No: 35 = 5 × 7, 36 = 22 × 32, 37, . . . , 100 = 22 × 52.
So we cannot draw a regular polygon with 100 sides.
 Perfect squares
12 = 1, 22 = 4, 32 = 9, 42 = 16,
52 = 25, 62 = 36, 72 = 49, 82 = 64,
92 = 81, 102 = 100
No squares end in 2, 3, 7 or 8.

Adding the first few odd numbers

always gives a square
(1 , 1+3, 1+3+5, . . . )
 Perfect squares
Every square has the form 4n or 4n + 1.
N even: N = 2k, so N2 = 4 × k2.
N odd: N = 2k + 1, so N2 = 4 × k(k+1) + 1.
So 11, 111, 1111, 11111, . . . aren’t
squares, as they have the form 4n + 3.

Moreover, if N is odd,
then N2 has the form 8n + 1.
 Right-angled triangles
Pythagoras: If the sides
are a, b, c, then
a2 + b2 = c2

Examples: 32 + 42 = 52; 52 + 122 = 132; 152 + 82 = 172

Can we find all examples with whole-number sides?
We’ll ignore scalings: 302 + 402 = 502; 62 + 82 = 102
so we assume that a, b, c have no factors in common.
Answer: a = x2 – y2, b = 2xy, c = x2 + y2,
where x > y, x and y have no common factors,
and one is even and the other odd.
 Listing all right-angled triangles
a = x2 – y2, b = 2xy, c = x2 + y2,
where x > y, x and y have no common factors,
and one is even and the other odd.
Examples: x = 2, y = 1: a = 3, b = 4, c = 5: 32 + 42 = 52
x = 3, y = 2: a = 5, b = 12, c = 13: 52 + 122 = 132
x = 5, y = 2: a = 21, b = 20, c = 29: 212 + 202 = 292
 Right-angled triangles with a side of
length 29
a = x2 – y2, b = 2xy, c = x2 + y2
Example: x = 5, y = 2:
a = 21, b = 20, c = 29 : 212 + 202 = 292
How many right-angled triangles with whole-number
sides have a side of length 29?
Either 29 = x2 + y2, so x = 5, y = 2: a = 21, b = 20, c = 29
or 29 = x2 – y2 = (x + y) (x – y) = 29 × 1,
so x + y = 29, x – y = 1, giving x = 15, y = 14,
and a = 29, b = 420, c = 421 .
 Sums of squares
Which numbers can be written
as the sum of two squares?
Fermat’s 4n + 1 theorem:
Every prime number
of the form 4n + 1
(such as 5, 13, 17, 29, 41, . . .)
is the sum of two squares
(and in only one way).
5 = 22 + 12, 13 = 32 + 22, 17 = 42 + 12,
29 = 52 + 22, 41 = 52 + 42, . . .
Fermat’s ‘last theorem’
We’ve found a, b, c, so that
a2 + b2 = c2.
Can we find a, b, c, so that
a3 + b3 = c3 ?
or a4 + b4 = c4 ? or . . .
Fermat believed that:
For any n > 2, an + bn = cn
has no solutions.
Proved by Andrew Wiles,
1995.
Clock arithmetic
9 o’clock + 6 hrs = 3 o’clock: 9 + 6 ≡ 3 (mod 12)
10 o’clock + 7 hrs = 5 o’clock: 10 + 7 ≡ 5 (mod 12)
8 o’clock + 4 hrs = 12 o’clock: 8 + 4 ≡ 0 (mod 12).
a ≡ b (mod n) if a and b leave the same
remainder when divided by n :
that is, if a – b is divisible by n.
Thursday + four days = Monday
Saturday + three days = Tuesday
Sunday = 0; Monday = 1; Tuesday = 2;
Wednesday = 3; Thursday = 4; Friday = 5;
Saturday = 6. Working (mod 7), we have
4 + 4 ≡ 1 (mod 7); 6 + 3 ≡ 2 (mod 7)
 Finding
the day
of the
week
(C. L. Dodgson:
Lewis Carroll)
 Lewis Carroll’s method
Add the following four numbers:
Century number. Divide the first two digits of the year by 4,
subtract the remainder from 3, and double.
Year number. Divide the last two digits of the year by 12,
and add the quotient, the remainder,
and the number of times 4 divides into the remainder.
Month number. Carroll’s method gives:
Jan: 0 Feb: 3 Mar: 3 Apr 6 May: 1 Jun: 4 Jul: 6
Aug: 2 Sep: 5 Oct: 0 Nov: 3 Dec: 5
Day number: This is the day of the month.
[Finally, subtract 1 if the date falls in January or February
of a leap year.]
 Lewis Carroll’s method
Add the following numbers: 28 September 2020
Century number. Divide the first Century number
two year digits by 4, subtract the
remainder from 3, and double.
Divide 20 by 4: remainder 0;
subtract 0 from 3 to give 3,
Year number. Divide the last
two year digits by 12, and add
and double to give 6
the quotient, the remainder, Year number
and the number of times 4 Divide 20 by 12 giving 1,
divides into the remainder.
remainder 8; 4 divides 8
Month number. 2 times, giving 1 + 8 + 2 = 11
Jan: 0 Feb: 3 Mar: 3 Apr 6
May: 1 Jun: 4 Jul: 6 Aug: 2 Month number Sep = 5
Sep: 5 Oct: 0 Nov: 3 Dec: 5 Day number 28
Day number: This is the day of The sum is 6 + 11 + 5 + 28
the month.
= 50 ≡ 1 (mod 7) = Monday
 Five Sundays in February?
The five Sundays must be 1, 8, 15, 22, 29 February,
so the year must be a leap year.
Now 1 January 2001 was a Monday,
so 1 February 2001 was a Thursday,
1 February 2002 was a Friday (as 365 ≡ 1 (mod 7)),
1 February 2003 was a Saturday,
1 February 2004 was a Sunday.
Also, the cycle of days repeats every 28 years
as (28 × 365) + 7 ≡ 0 (mod 7), so the years are
2004, 2032, 2060, 2088.
 Fermat’s
‘little theorem’
For any number a and any prime number p,
ap – a is divisible by p
for example, 837 – 8 is divisible by 37

Another version (divide by a) is:

ap–1 – 1 is divisible by p
for example, 252 – 1 is divisible by 53,
or 252 ≡ 1 (mod 53)
 Counting necklaces
For any number a and any prime p,
ap – a is divisible by p

How many different coloured necklaces

with p beads and a colours are there,
using at least two colours?
There are ap possible strings of beads,
RBRRY or ap – a when we exclude the 1-colour
= BRRYR ones (such as RRRRR).
= RRYRB So there are (ap – a)/p different ones,
= RYRBR and so ap – a is divisible by p.
= YRBRR
 How many shuffles are needed to restore
a pack of cards to its original order?

Now the card in position x → position 2x (mod 53),

and after n shuffles → position 2nx (mod 53).
So 2nx ≡ x (mod 53), giving 2n ≡ 1 (mod 53).
But, by Fermat’s theorem, 252 ≡ 1 (mod 53).
So the pack is restored after 52 shuffles.
[mod 53: 22 ≡ 4 , 24 ≡ 16, 213 ≡ 30, 226 ≡ 52]
 Shuffling a pack with two Jokers

We now have 54 cards, and in the same way we get

2n ≡ 1 (mod 55).
But 55 isn’t a prime number, so we can’t use Fermat’s
theorem to give us n = 54 shuffles.
But if 55 divides 2n – 1, then so do 5 & 11.
So 24 ≡ 1 (mod 5) and 210 ≡ 1 (mod 11).
So 220 ≡ 1 (mod 5) and 220 ≡ 1 (mod 11),
so 220 ≡ 1 (mod 55).
So the pack is restored after 20 shuffles.
 Euler’s theorem
If p does not divide a,
then ap–1 – 1 is divisible by p:
so ap–1 ≡ 1 (mod p).
But what can we say if p isn’t prime?
Euler’s theorem: aφ(n) ≡ 1 (mod n) ,
where φ(n) counts the numbers up to n
with no factors in common with n:
e.g. φ(10) = 4 [1, 3, 7, 9]; φ(12) = 4 [1, 5, 7, 11];
φ(p) = p – 1; φ(pq) = (p – 1) × (q – 1) :
e.g. 1073 = 29 × 37, so φ(1073) = 28 × 36 = 1008.
 RSA public key cryptography
Alice wishes to send a secret message to Bob.

Bob first selects two primes, p, q, calculates N = pq. N = 29 × 37 = 1073

and chooses e so that gcd (e, φ(N)) = 1. φ(N) = 1008, e = 11
He publicly announces e and N, but not p and q.
The numbers e and N are then the public key, known to all.
Alice now converts her message to numerical form and calls it M.
Knowing e and N, she calculates E ≡ Me (mod N) and sends it to Bob.

Using the fact that gcd (e, φ(N)) = 1, Bob calculates m and n for which
me + n φ(N) = 1, and so me ≡ 1 (mod φ(N)). 11m ≡ 1 (mod 1008)
Now, by Euler’s theorem, Mφ(N) ≡ 1 (mod N), so m = 275
so Em ≡ (Me)m = Mme = M1 −nφ(N) ≡ M (mod N).
Bob calculates Em (mod N) to retrieve Alice’s original message M.
M ≡ E275 (mod 1073)
 RSA public key cryptography
Alice wishes to send a secret message to Bob.
Bob first selects two primes, p, q, calculates N = pq.
N = 29 × 37 = 1073, φ(N) = 1008,
and chooses e so that gcd (e, φ(N)) = 1. e = 11
He then publicly announces e and N, but not p and q.
The numbers e and N are the public key, known to all.
Alice now converts her message to numerical form
and calls it M. Knowing e and N, she calculates
E ≡ Me (mod N) and sends it to Bob.
 RSA public key cryptography
Alice calculates E ≡ Me (mod N) and sends it to Bob.

Using the fact that gcd (e, φ(N)) = 1,

Bob calculates m and n for which
me + n φ(N) = 1, and so me ≡ 1 (mod φ(N)).
11m ≡ 1 (mod 1008), so m = 275
By Euler’s theorem, Mφ(N) ≡ 1 (mod N),
so Em ≡ (Me)m = Mme = M1 −nφ(N) ≡ M (mod N).
Bob calculates Em (mod N) to retrieve Alice’s
original message M. M ≡ E275 (mod 1073)
 Robin Wilson
NUMBER THEORY
A Very Short Introduction
(no. 636 in the series)

Published in May 2020 by

Oxford University Press

ISBN: 978-0-19-879809-5

Price: £8.99
[US $11.95]