Lecture 19 We continued looking at Book VII, Book VIII and Book IX. To be precise we started with the Euclidean Division Algorithm and how to compute the greatest common divisor of two given numbers. Read carefully the commentaries of: Proposition 1 Proposition 2. We computed carefully computed the gcd of 3796 and 1387. Well....it turns out that it is 73. We used the Euclidian Algorithm to find it, and to prove that it is a divisor of both numbers and that actually it is the greatest divisor. It is actually possible to write the gcd as a combination of the two given numbers. That is, we can find numbers a and b such that 73 = a*3796 + b*1387. How can we do it? ... The Euclidian Algorithm allows to give the answer ... which is ... a = ? ... and ... b = ?? ... ;-) We then moved on and we commented the following propositions: Proposition 30 Proposition 31 Proposition 32 (we proved Proposition 20...in a modern language, though!) Finally, we arrived (in Book IX) to Proposition 14, which Victor Katz reads as a version of the Fundamental Theorem of Arithmetic, that is "every number can be uniquely factored into product of primes." We then ended the lecture with Euclid's famous proof about the infinitude of prime numbers: Prime numbers are more than any assigned multitude of prime numbers, which is proved in Proposition 20. To illustrate the 2 cases discussed in the proof (which we did!), we considered two examples: when N=2*3*5+1(=31) and when N=3*5*7+1(=106). Comment: Prime numbers are at the base of our encription systems for all secure transactions that we do over the Internet. Do you know for instance how RSA works? If not, this is a good idea for a topic for your final project. It boils down to Fermat's Little Theorem. Click on the above links to go directly to the proofs and commentaries of the results.