Transcript Euclidean Number theory - York College of Pennsylvania

Euclidean Number theory
From the Algorithm to the Basic
Theory of Numbers
The Life of Euclid
• Born in Alexandria around 300 B.C.
• Studied under Plato and taught in the
Museum
• Little known about his life
• Well kept records with team of
mathematicians
• Wrote “The Elements”
It’s not all geometry!
• The Elements made up 13 books mostly on
geometry and algebra
• Logical sequence made the elements useful
• Books 7-9 dealt with number theory
• The opening of a new way of looking at
math
• The Euclidean Algorithm is introduced in
book seven
The Euclidean Algorithm
• Used to find the g.c.d of two numbers
• Method: divide the larger of the two positive
integers by the smaller one, then divide the divisor
by the remainder. Continue this process, of
dividing the last divisor by the last remainder,
until the division is exact. The final divisor is the
sought g.c.d. of the two original positive integers.
Find the g.c.d of 63 and 24.
63  24  2 _ R15
24  15  1 _ R 9
15  9  1 _ R 6
9  6  1 _ R3
63 2
•So the g.c.d. of 63 and 24 is 3!
Just the beginning of number
theory
• Euclid dives into the
concept of prime
numbers
• Introduction of
relatively prime
numbers
• Modern mathematics
is still trying to
discover more about
primes
• Theory proofs all
based on previously
proven information
Problems from Eves
• 5.2 a.) Prove, using Problem Study 5.1 (f)*,
that if p is a prime and divides the product
of uv, then either p divides u or p divides v.
• *5.1 (f) states that 2 integers a and b are
relatively prime if and only if there exist
integers p and q such that pa+qb=1
Assume p does not divide u:
•
•
•
•
•
•
Then p and u are relatively prime
So pa+ub=1
pav+ubv=v (multiply through by v)
px=uv (since p divides uv, some x exists such that px=uv)
pav+bpx=v
p(av+bx)=v
Since p(av+bx)=v:
• av+bx is an integer (since integers are
closed under addition and multiplication)
• So av+bx can be written as some integer h.
• ph=v
• Therefore p must divide v!
Fundamental theorem of
Arithmetic
• Every integer greater than one can be
uniquely factored into a product of primes
• Each number, if not prime can be written as
the product of 2 other numbers
• If these are not prime then they are written
as the product of 2 numbers.
• This cannot continue forever
Infinite number of Primes
• Euclid states that Prime numbers are more
than any assigned multitude of prime
numbers.
• “An infinite number of primes exist”
• proven geometrically
A
B
G
C
F
E
A,B, and C are the assigned primes
D
DE is least number measured by all three
Then EF is either prime, or it is not prime
If prime, there is another prime found
If not prime, then this line must be measured by some
prime number G, and this is a new prime.
Why is G different from the
others?
• G is not similar to A,B, or C because if it
were, then G would measure DE and DF,
and it would be absurd for G to measure the
segment and it’s remainder.
• (Proof given by John Fauvel)
Euclid got it all started.
Happy Holidays