Transcript Chapter 10: Euler`s Number Theory

Chapter 10: Euler’s
Number Theory
Matt Sarty and Kimberly Cox
World History
1700: World Population reaches 700 million.
Beginning of the Industrial Revolution
1701: Anders Celsius devises the centigrade
temperature scale
1707: United Kingdom of Great Britain formed joining
England, Wales and Scotland by a parliamentary act
of union
World History
1729: Bach wrote St. Matthew Passion and Newton’s
Principia was translated from Latin into English
1735: Carolus Linnaeus divided all living organisms
into two categories: plants and animals
1740-1746: Frederick the II (The Great) was king of
Prussia. Had poor relationship with Euler- Ultimately
Euler’s reason for returning to St. Petersburg Russia.
World History
1756: Beginning of the Seven Year War in which
Britain and Prussia defeat France, Austria, Russia and
Spain
1759: Haydn composes his Symphony no. 1 and British
capture Quebec from the French.
1760:George III becomes King of Britain. Benjamin
Franklin invents Bifocal glasses
World History
1783: Joseph and Jacques Montgolfier demonstrate
the first hot air balloon in a ten minute
demonstration
1799: Naploean Bonapart discovers Rosetta Stone.
Alessandro Volta invents the battery
Christian Goldbach
1690-1764: Was a Prussian
Mathematician who also studied law
and was a leading force in fueling
Euler’s interest in number theory.
Most well known for Goldbach’s
conjecture
Goldbach loved number theory and
introduced Euler to a lot of Fermat’s
unproven statements.
Leonard Euler
1707-1783: born in Basel Switzerland.
Father Paul Euler studied theology at the University of Basel and
attended Jakob Bernoulli’s lectures there. As a result, Paul taught
Leonard simple mathematics at a young age. (More of younger
years explained in the previous presentation.)
Large portion of work in number theory was getting proof of
Fermat’s statements, filling four volumes of his Opera Omnia
with this work. (Had Euler done nothing else, this work would
have placed him among the world’s greatest mathematicians.)
Euler’s Number Theory
Amicable pair: the sum of all proper divisors of the first
number equals the second number while the sum of all
proper divisors of the second equals the first.
Greeks were aware of the amicable pair 220 and 284. No
other pair was known to the Western world until Fermat
discovered the pair 17,296 and 18,416 in 1636. In 1638
Descartes discovered a third pair.
Between 1747 and 1750 Euler was able to discover 58 other
pairs, increasing the amicable pairs known by almost
2000%
Little Fermat Theorem
Euler approached the proof to this theorem in a series of four
steps. (Each led to the next.)
Theorem 1: If p is prime and a is any whole number then (a + 1)p
– (ap + 1) is evenly divisble by 3.
Theorem 2: If p is a prime and if ap – a is evenly divisble by p
then so is (a + 1)p – (a+1).
Theorem 3:If p is a prime and a is any whole number, then p
divides evenly into ap – a.
Little Fermat Theorem: If p is a prime and a is a whole number
which does not have p as a factor, then p divides evenly into ap-11.
This theorem is used today to justify the RSA public key
encryption method of cryptography.
Great Theorem: Euler’s
Refutation of Fermat’s
Conjecture
Fermat’s Conjecture stated that given any whole
number n, the equation 2 2  1 will always produce
a prime. This conjecture works for n=1,2,3,4 but Euler
proved this equation false for n=5, that is he factored
4,294,967,297, the value for n=5.
n
In order to prove this Euler used numerous smaller
proofs that we
will look at next in order to prove
Fermat’s conjecture wrong.
Euler’s Great Proof
Theorem A: Suppose a is an even number and p is a
prime that is not a factor of a but that does divide
evenly into a+1. then for some whole number k,
p= 2k + 1.
Proof: If a is even, then a +1 is odd. Since we assumed
that p divides evenly into the odd number a+1, p itself
must be odd. Hence p -1 is even and so p-1=2k for
some whole number k. This means p=2k+1.
Euler’s Great Proof
Theorem B: Suppose a is an even number and p is a prime
that is not a factor of a but such that p does divide evenly
into a2 + 1. Then for some whole number k, p = 4k + 1.
Proof: Since a is even, a2 is as well. Therefore by Theorem
A, any prime factor of a2 + 1, in particular the number p
must be odd. This means that p is one more than a
multiple of 2.
If we divide p by 4, since p is odd, it is either: p = 4k + 1 or p
= 4k + 3.
Euler wanted to rule out the case where p = 4k + 3 and did
so by proof through contradiction seen next.
Euler’s Great Proof
Suppose p = 4k + 3 for some whole number k. By
hypothesis, p is not a divisor of a, and by Little Fermat
theorem, p divides evenly into ap-1 – 1 = a(4k + 3) -1 – 1 = a4k + 2.
Now, we have assumed that p is a divisor of a2 + 1, and
therefore is a divisor of
(a2 + 1)(a4k – a4k – 2 + a4k- 4 -…+ a4 –a2 + 1) which simplifies to
a4k + 2 – 1. Therefore, p must be a divisor of the difference
(a4k+2 + 1) – (a4k + 2 – 1) = 2.
This is a contradiction since p is odd and cannot therefore
divide into 2 evenly. Thus, p does not equal 4k + 3 which
was assumed, and must be of the form 4k + 1.
Euler’s Great Proof
Theorem C: Suppose a is an even number and p is a prime that is
not a factor of a but such that p does divide evenly into a4 + 1. Then
for some whole number k, p = 8k + 1.
Proof: Note that a4 + 1 = (a2)2 + 1. Therefore, applying theorem B we
see that p is one more than a multiple of 4. Euler tried to see what
would happen is p is divided by 8 instead of 4. there are 8
possibilities:
p = 8k, p=8k + 1, p = 8k+2, p=8k + 3, p= 8k + 4, p=8k + 5, p = 8 k + 6, p=
8k + 7.
We know that p must be odd since p is a divisor of a4 + 1. Therefore p
cannot be of the form 8k, 8k + 2, 8k + 4, or 8k + 6. Also 8k + 3 =
4(2k) + 3 and so from theorem B, p can’t take this form. Also 8k + 7
= 8k + 4+ 3 = 4(2k + 1) + 3 and so the only possibilities are for p to be
of the form 8k + 1 or 8k + 5.
Euler’s Great Proof
Now, suppose p = 8k +5. Since p is not a divisor of a, by
Little Fermat p divides evenly into
ap-1 – 1 = a(8k + 5) -1 -1 = a(8k + 4) - 1.
Since p divides evenly into a4 + 1, it divides evenly into (a4
+ 1)(a8k – a8k -4 + a8k-8 – a8k -12 + …+ a8 – a4 + 1) which reduces
to a8k + 4 + 1.
If p is a factor of (a8k +4 + 1) and (a8k+4 – 1), then it must be a
factor of (a8k +4 + 1) - (a8k+4 – 1) = 2.
This is a contradiction since p is an odd prime therefore p
is not of the form 8k + 5 and must be of the form 8k +1.
Euler’s Great Proof
Theorem: 232 + 1 is not a prime.
Proof: Since a = 2 is even, the work above tells us that any prime
factor of 232 + 1 is of the form p = 64k + 1, with k a whole number.
Euler then checked each value for k individually to see if they
were prime and divided evenly into 232 + 1= 4, 294, 967, 297.
k = 1, 64k +1 = 65- not prime therefore need not be checked.
k=2, 64k + 1 = 129 = 3x43- not prime
k = 3, 64k + 1 = 193- a prime, but doesn’t divide into 232 + 1
k = 4, 64k +1 = 257, a prime, doesn’t divide into 232 + 1
k = 5, 64k + 1 = 321 = 3x 107, non-prime
Euler’s Great Proof
k =6, 64k + 1 = 385 = 5x7x11 non-prime
k= 7, 64k + 1 = 449, prime, doesn’t divide into 232 + 1
k = 8, 64k + 1 =513, non-prime
k = 9, 64k + 1= 577, prime but not a factor 232 + 1.
Euler found for k=10, 64k + 1 = 641, a prime that
divides into 232 + 1 = 4, 294, 967,297 = 641 x 6, 700, 417.
Q.E.D.
Carl Friedrich Gauss

Carl Friedrich Gauss
1777- 1855: German mathematician born in Brunswick.
At age of 6, the year Euler died.
Earliest significant mathematical achievement was the
discovery in 1796 that a regular sided polygon could be
constructed with compass and straightedge. (explained in
chapter 3)
Determined that if n was a prime number of the form
2 2  1 then a regular polygon of n sides is
constructable.( A significant connection between number
theory and geometric constructions of regular polygons.)
n
Carl Friedrich Gauss
Gauss showed great promise as a mathematician even in his
elementary school days.
He entered college at age 15, and entered Gottingen University
three years later.
1799: He received his doctorate from the University of
Helmstadt for providing the first reasonably complete proof of
the fundamental theorem of algebra.
1801: He published his numerical, theoretical masterpiece
Disquisitiones Arithmeticae.
“Mathematics is the queen of the sciences, and the theory of
numbers is the queen of mathematics.”
Sophie Germain
1776-1831: Her fascination with math began as a child by the
works she found in her father’s library.
She had to hide her studies from everyone including her family
and took to listening to university lectures outside of the
classroom door and borrowing notes from sympathetic male
students.
1816: She won a prize from the French Academy for her analysis
of the nature of vibrations in elastic plates. During this time she
disguised herself as a man under the pen-name Antoine Leblanc.
Under her pen-name she wrote to Gauss and he provided insight
into her work in mathematics at the time. In 1807 Gauss
discovered her true identity , but still praised her saying that
“her mathematical works gave him a thousand pleasures.”
Sophie continued to have a successful career even after her
identity was revealed, although she died before being awarded
an honorary doctorate from Gottingen.
Questions to Ponder
The author describes Gauss in very admirable terms,
going so far as to call him “the majestic Carl Friedrich
Gauss”, why do you think Dunham looks up to Gauss
more so perhaps than some of the other mentioned
mathematicians in this book and why isn’t he given
his own chapter in the book?
Do you feel that by Gauss’ acceptance of Sophie
Germain as a female mathematician he helped pave
the way for future female mathematicians?