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?