Transcript 3_M2306_Hist_chapter3

Chapter 3
Greek Number Theory
•
•
•
•
•
•
The Role of Number Theory
Polygonal, Prime and Perfect Numbers
The Euclidean Algorithm
Pell’s Equation
The Chord and Tangent Method
Biographical Notes: Diophantus
3.1 The Role of Number Theory
• Greek mathematics
– systematic treatment of geometry (Euclid’s “Elements”
– no general methods in number theory
• Development of geometry facilitated development of
general methods in mathematics (e.g. axiomatic approach)
• Number theory: only a few deep results until 19th century
(contribution made by Diophantus, Fermat, Euler,
Lagrange and Gauss)
• Some famous problems of number theory have been
solved recently (e.g. Fermat’s Last Theorem). Solutions of
many others have not been found yet (e.g. Goldbach’s
conjecture)
• Nevertheless attempts to solve such problems are
beneficial for the progress in mathematics
3.2 Polygonal, Prime and Perfect Numbers
• Greeks tried to transfer geometric ideas to number
theory
• One of such attempts led to the appearance of
polygonal numbers
triangular
square
6
10
1
3
1
4
9
1
5
12
16
pentagonal
22
Results about polygonal numbers
• General formula:
Let X n,m denote mth n-agonal number. Then
X n,m = m[1+ (n-2)(m-1)/2]
• Every positive integer is the sum of four integer squares
(Lagrange’s Four-Square Theorem, 1770)
• Generalization (conjectured by Fermat in 1670): every
positive integer is the sum of n n-agonal numbers (proved
by Cauchy in 1813)
• Euler’s pentagonal theorem (1750):

 (1  x
n 1

n

)  1   (1) x
k
k 1
(3k 2  k ) / 2
x
(3k 2  k ) / 2

Prime numbers
• An (integer) number is called prime if it has no
rectangular representation
• Equivalently, a number p is called prime if it has
no divisors distinct from 1 and itself
• There are infinitely many primes. Proof (Euclid,
“Elements”):
– suppose we have only finite collection of primes:
p1,p2,…, pn
– let p = p1p2 … pn +1
– p is not divisible by
– hence p is prime and p > p1,p2,…, pn
– contradiction
Perfect numbers
• Definition (Pythagoreans): A number is called perfect if it is
equal to the sum of its divisors (including 1 but not including
itself)
• Examples: 6=1+2+3, 28=1+2+4+7+14
• Results:
– If 2n-1 is prime then 2n-1(2n - 1) is perfect (Euclid’s
“Elements”)
– every perfect number is of Euclid’s form (Euler, published
in 1849)
• Open problem: are there any odd perfect numbers?
• Remark: primes of the form 2n-1 are called Mersenne primes
(after Marin Mersenne (1588-1648))
• Open problem: are there infinitely many Mersenne primes?
(as a consequence: are there infinitely many perfect
numbers?)
3.3 The Euclidean Algorithm
• Euclid’s “Elements”
• The algorithm might be known earlier
• Is used to find the greatest common
divisor (gcd) of two positive integers
a and b
• Applications:
– Solution of linear Diophantine equation
– Proof of the Fundamental Theorem of
Arithmetic
Description of the Euclidean Algorithm
1.
a1 = max (a,b) – min (a,b)
b1 = min (a,b)
2.
(ai,bi) → (ai+1,bi+1):
ai+1 = max (ai,bi) – min (ai,bi)
bi+1 = min (ai,bi)
3.
Algorithm terminates when
an+1 = bn+1
and then
an+1 = bn+1 = gcd (an+1,bn+1) = gcd (an,bn) = … = gcd
(ai+1,bi+1) gcd (ai,bi)= …= gcd (a1,b1)= gcd (a,b)
Applications
• Linear Diophantine equations
– If gcd (a,b) = 1 then there are integers
x and y such that ax + by =1
– In general, there are integers x and y such that ax + by
= gcd (a,b)
– Moreover, ax + by = d has a solution if and only if
gcd (a,b) divides d
• The Fundamental Theorem of Arithmetic
– Lemma: If p is a prime number that divides ab then p
divides a or b
– the FTA: each positive integer has a unique
factorization into primes
3.4 Pell’s Equation
• Pell’s equation is the Diophantine equation
x2 – Dy2 = 1
• The best-known D. e. (after a2 + b2 = c2)
• Importance:
– solution of it is the main step in solution of general quadratic
D. e. in two variables
– key tool in Matiyasevich theorem on non-existence of the
general algorithm for solving D. e.
• The simplest case x2 – 2y2 = 1 was studied by
Pythagoreans in connection with 2: if x and y are large
solutions then x/y ≈ √2
Solution by Pythagoreans: recurrence relation
• x2 – 2y2 = 1
• trivial solution: x = x0 = 1, y = y0 = 0
• recurrence relation, generating larger
and larger solutions:
xn+1 = xn + 2yn , yn+1 = xn + yn
• then (xn)2 – 2(yn)2 = 1if n is even and
(xn)2 – 2(yn)2 = -1if n is odd
Anthyphairesis
≡ Euclidean algorithm
How did Pythagoreans
discoverapplied
theseto line
segments recurrence
and thereforerelations?
to pairs of non-integers
a and b
•
•
•
•
When the ratio a/b is rational the algorithm terminates
If a/b is irrational it continues forever
Apply this algorithm to a = 1 and b = √2
Represent a and b as the sides of a rectangle
x1=1
y1=√2
1
√2-1
1
√2-1
√2-1
1
1
y0=2-√2
x0=√2-1
Successive similar rectangles with sides (xn+1,yn+1) and (xn,yn)
so that xn+1=xn+2yn and yn+1=xn+yn
Remarks
• Note that (xn+1)2 – 2 (yn+1)2 = 0
• It turns out that the same relations generate solutions of
x2 – 2y2 = 1 or -1
• Similar procedure can be applied to 1 and √D to obtain
solutions of x2 – Dy2 = 1 (Indian mathematician
Brahmagupta, 7th century CE)
• To obtain recurrence we need the recurrence of similar
rectangles (proved by Lagrange in 1768)
• Continued fraction representation for √D
• Example (cattle problem of Archimedes 287-212 BCE):
x2 – 4729494y2 = 1
The smallest nontrivial solution have 206,545 digits (proved
in 1880)
3.5 The Chord and Tangent Method
• Generalization of Diophantus’ method to find all rational points on
the circle
• Consider any 2nd degree algebraic curve: p(x,y) = 0 where p is a
quadratic polynomial (in two variables) with integer coefficients
• Consider rational point x = r1, y = s1 such that p(r1,s1) = 0
• Consider a line y = mx+c with rational slope m through (r1,s1)
(chord)
• This line intersects curve in the second point which is the second
solution of equation p (x, mx+c) = 0
• Note: p(x,mx+c) = k(x-r1)(x-r2) = 0
• Thus we obtain the second rational point (r2,s2)
(where s2 = mr1 + c)
• All rational points on 2nd degree curve can be obtained in this way
If p(x,y) has degree 3…
• Consider an algebraic curve p(x,y) = 0 of degree 3
• Consider base rational point x = r1, y = s1 such that
p(r1,s1) = 0
• Consider a line y = mx+c through (r1,s1) which is tangent to
p(x,y) = 0 at (r1,s1)
• It has rational slope m
• This line intersects curve in the second point which is the
third solution of the equation p (x, mx+c) = 0
• Indeed: p(x,mx+c) = k(x-r1)2(x-r2) = 0 (r1 is a double root)
• Thus we obtain the second rational point (r2,s2)
(where s2 = mr1 + c), and so on
• This tangent method is due to Diophantus and was
understood by Fermat and Newton (17th century)
Does this method give us all rational
points on a cubic?
• In general, the answer is negative
• The slope is no longer arbitrary
• Theorem (conjectured by Poincaré (1901),
proved by Mordell (1922)) All rational points
can be generated by tangent and chord
constructions applied to finitely many points
• Open problem: is there an algorithm to find
this finite set of such rational points on each
cubic curve?
2.6 Biographical Notes: Diophantus
• Approximately between 150 and 350 CE
• Lived in Alexandria
• Greek mathematics was in decline
• The burning of the great library in Alexandria
(640 CE) destroyed all details of Diophantus’
life
• Only parts of Diophantus’ work survived (e.g.
“Arithmetic”)