This is a course offered through the University of Toronto Department of Mathematics for mathematically interested and capable high school students, particularly those in grades 10 and 11. See the announcement for details, or you may browse week-by-week details that will be posted below. You may also contact the instructor, Peter M. Garfield.
The last meeting of this class was Wednesday, May 28th. Please check the MathNet home page for future SOAR courses.
We finished the course with a discussion of some open problems in number theory. Rather than go into the actual problems we covered, I will instead just refer you to the bibliography for some interesting web pages.
Thanks everyone for wonderful semester! If you didn't fill out the survey, please do so as soon as you can. Thanks.
There is no homework this week.
Today's group of the day is that most unusual group of points on an elliptic curve. We usually dealt with curves of the form y2=x3 + ax + b (although we sometimes allow an x2 term as well). The group operation is, roughly speaking, as follows: two add the points P and Q, draw the line through P and Q. This will intersect the curve at a third point, call it R. Then P+Q is the reflection of R across the x-axis. (This is incomplete, of course: what is P+P, for example?) The identity of this group is O, the point at infinity. After some practice graphing and adding points on the graphs, we very briefly discussed the possible applications to cryptography. See the bibliography for more detailed references.
We ended the day with a (brief!) overview of the proof of Fermat's Last Theorem. This theorem says that, when n>2, there are no positive integer solutions to the equation an+bn = cn. (This is in stark contrast to the n=2 case which began the course.) This theorem ends up as a corollary of the Taniyama-Shimura conjecture: all elliptic curves are modular. (We didn't actually discuss what it means for such a curve to be modular.) On the other hand, if there is a counter-example an+bn = cn to Fermat's Last Theorem, Frey and Ribet proved that one can construct a non-modular elliptic curve, namely y2=x(x-an)(x+bn). Andrew Wiles then proved the Taniyama-Shimura conjecture for a class of curves that includes this example. That is, if Fermat's Last Theorem was false, the counter-example would produce a non-modular elliptic curve that Wiles's theorem says must be modular. Hence Fermat's Last Theorem must hold. See the bibliography for other, more expanded versions of the story.
PDF or web (no web yet this week, sorry) New version, May 27th, typo on 3(b)
Problem 3: PDF only
Continuing the saga of primality tests, we began with a review of the strong primality test (or Rabin-Miller test) and the Lucas test. We used the strong primality test to show that 2047 = 1 + 2·1023 is not prime, although it is a strong base 2 pseudoprime.
From there we turned to the Lucas-Lehmer test. The simpler version of this test says that the Mersenne number Mp = 2p-1 is prime precisely when Lp-2 = 0 mod Mp. Here Lk is the Lucas-Lehmer sequence defined by L0=4 and Lk+1=Lk2 - 2. (We discovered that, in fact, Lk=V2k+1 / 22k, where Vk is a sequence defined last time by Vk = αk + βk; see last week's definition of Uk.) We also stated a more generally applicable Lucas-Lehmer test, and used it to show that 163=2·34+1 and 487=2·35+1 are both prime.
Finally, we finished the day's discussion of primality tests with a new, efficient algorithm from Manindra Agarwal, Nitin Saxena, and Neeraj Kayal. The bibliography, below, includes a link a web page about their (still quite recent) result, including the preprint detailing the algorithm and its efficiency. I recommend at least scanning the paper. The discussion of this algorithm involved a little bit of discussion about the binomial theorem and Pascal's triangle; I've included some links to these below as well.
PDF or web (no web yet this week, sorry)
We began the day with primitive roots (see this week's homework for the definition and an example), which we used to define the index. This was all preliminary to a proof of a claim from last time: the Legendre symbol (a/p) = (-1)(p-1)/2. (Here p is prime and a is relatively prime to p.) We extended the Legendre symbol to the Jacobi symbol (a/n) where n is odd, but no longer prime. This was done by factoring n into a product of (not necessarily distinct) primes n=p1 p2··· pk and setting (a/n)=(a/p1)(a/ p2)··· (a/pk).
Taking an abrupt turn, we looked at generalized Fibonacci sequences. Assume F0 = 0, F0 = 0, and Fn = a Fn-1 - b Fn-2 for n > 1. (The usual Fibonacci sequence is a=1 and b=-1.) If D=a2-4b > 0, then this sequence is the same as Uk = (αk - βk)/(α - β), where α = (a+sqrt(D))/2 and β = (a-sqrt(D))/2 are the solutions of x2 - ax + b =0.
We combined these two topics in the Lucas test: assume n > 2 is odd, does not divide b, and (D/n) = -1. Then if n does not divide Un+1, then n is composite. On the other hand, a Lucas pseudoprime is a composite number that is not caught by this Lucas test.
PDF or web (no web yet this week, sorry)
Problem 2: PDF only
Problem 6: PDF only
We began class with games of Nim. The rules we used are simple: there are two players and some piles of sticks. (You can use any number of piles of any number of sticks. You don't need sticks, of course, you can use pennies, almost tasty fruity chewy candies, or anything else that's handy.) The players take turns removing as many sticks as they like from one pile per turn. The last player to take a stick wins. (Said another way: the first player not to be able to pick up a stick loses.) Check out the links below for some places to play on-line.
After dinner, we turned to the big question: how do we tell if a large number n is prime? Fermat's Little Theorem gives us one common property of primes: if n is prime, then bn = b mod n whenever gcd(b,n)=b. If a composite (that is, non-prime) number satisfies this equation, we call it a base b pseudoprime. We checked some numbers by hand and saw that 341 is a base 2 pseudoprime, 121 is a base 3 pseudoprime, 217 is a base 5 pseudoprime, and 373 is, in fact, simply prime. A number n that is a base b pseudoprime for every base b relatively prime to n is called a Carmichael number. There is only one such number (561) under 1,000, and fewer than 250,000 under 1016.
Finally, as a prelude to another test for primality, we defined the Legendre number (a/p) as +1 if we can solve x2=a mod p, and -1 if we cannot. It turns out that (a/p) = a(p-1)/2 mod p. (The notation (a/p) is a little unfortunate. This is not a fraction in the usual sense.) For example, since (2/127) = +1, we can solve x2=2 mod 127. On the other hand, since (3/127) = -1, we cannot solve x2=3 mod 127.
PDF or web (no web yet this week, sorry)
Problem 2: PDF only
Problem 7: PDF only
Today we defined a mathematical group and proceeded to see that we've been familiar with these abstract mathematical objects. The first examples we looked at were groups under addition. Specifically we looked at the integers under addition (Z,+), but the same logic applies to the rational numbers (Q,+), real numbers (R,+), and complex numbers (C,+) under addition.
We next looked at the same spaces under multiplication. The integers with multiplication are not a group, and we must remove zero from the others as zero has no multiplicative inverse. Thus our multiplicative groups are the rational (Q,×), real (R,×), and complex (C,×) numbers.
Next we turned to some newer (to us) groups. (Most people haven't seen the complex numbers, perhaps, but the integers, rationals, and reals are all familiar.) The first was the group (Zn,+) of integers modulo n under addition. The next was the group (Mn,×), where the operation was multiplication modulo n. In order to make this a group, we must restrict the set of integers relatively prime to n. That is,
| Mn = { k | 0 < k < n, gcd(k,n)=1 } . |
Finally we looked at some groups that were entirely new. We figured out the dihedral group Dn (the symmetries of a regular n-sided polygon) and the cyclic group Cn (only the rotational symmetries of the same regular n-sided polygon). (See the homework for some examples of Cn and Dn.) The big finish today was a look at the frieze groups of possible symmetries of infinite strips with translational symmetries. See the bibliography for some web sites with pictures.
Problem 1(a)(d): PDF only
Problem 3(c): PDF only
We spent the first part of today dealing with Farey series. We saw that, if p/q is the closest term in a Farey series to a number x with 0<x<1, then |x-p/q| < 1/q(n+1) < 1 /q2. We used this, in turn, to see that 22/7 is a pretty darn good estimate for pi (and that there isn't a better fraction for quite a few denominators).
The remainder of the day was spent testing divisibility of large numbers. We obtained divisibilty conditions for 2, 4 (and 2k by the same idea), 3 and 9, two different ones for 7, 11 (and 101 and 10001=73·137 by the same idea), and 999=27·37 (and 99999=99·41·271 by the same idea). We also investigated Fermat's method of factoring the product of two primes that are close in size. See the homework for applications of both of these.
Finally, you should see the homework for the two added questions. One of the added questions is not as stated in class, as I got it wrong. See below for details.
We spent some time today completing our proof that even perfect numbers are in one-to-one correspondence with Mersenne primes; see last week for some more comments about this. We also reviewed our construction of the RSA algorithm; see today's handout (corrected after class) for he details.
The RSA problems are now available.
The new topic for today was Farey series. The Farey series Fn is the list (series or sequence, really) of fractions a/b in increasing order, with a and b relatively prime, where a and b are integers from 0 to n (and b isn't zero, of course). For example, F3 is {0/1, 1/3, 1/2, 2/3, 1/1}. We proved some useful facts: first, if a/b < c/d are consecutive terms in Fn, then bc-ad=1. Moreover, the next term that appears between these two terms (in some future Farey series Fn+1, Fn+2, and so on) is the mediant (a+c)/(b+d). Implicit here is that a/b < (a+c)/(b+d) < c/d.
We'll return to Farey series next time. In the meantime, see the homework for some related problems.
Most of today was taken up discussing perfect numbers. We say that a number is perfect if it is the sum of all its proper divisors. Using some technical facts, we proved that an even number N is perfect exactly when N = 2 n-1 (2 n - 1) and 2 n - 1 is prime. Prime numbers of this form are called Mersenne primes; as of today only 39 are known. (See the bibliography, below, for some links.) It is not known if there are any odd perfect numbers.
This led to a discussion of Fermat numbers Fn = 22n + 1. We proved (using mathematical induction - again, see the links below) that Fn = F0 · F1 · · · · Fn-1 + 2. Two immediate consequences of this are that Fm and Fn are relatively prime, and that Fm divides Fn if n > m. (Note: I forgot to mention the hint / useful fact / way to solve problem two of the homework. Well, I mentioned it, but I didn't tell you what it was. Euler proved that any prime factor of Fn is of the form k · 2n+2+1 for some value of k. This makes question two much simpler.)
Finally, we began a discussion of the RSA encryption / decryption algorithm. We'll continue this discussion next time!
PDF or web Note that problem 3 has been postponed until next week, and that there is a hint for problem 2 in the text, above.
Problem 1(d)(e): PDF only
We spent the first part of today on modular multiplication. This produced a discussion of Mn, the set of positive integers less than n that are relatively prime to n. This naturally leads to Euler's phi function, which is a function that gives the number of elements of Mn. (See the homework for more on this.)
We also produced a couple of classical theorems out of these discussions. The first is the little Fermat theorem, which says that xp-1 = 1 mod p for any prime p and any integer x. This generalizes to Euler's theorem, which says xphi(n) = 1 mod n for any element x of Mn. (This means that this equivalence holds for any x relatively prime to n.) The last equivalence we proved was Wilson's theorem: (p-1)! = -1 mod p for any prime p.
We began the day with a proof that there are infinitely many primes. The proof uses the fact that N = p1p2...pn+1 is not divisible by the primes p1, p2, ..., pn, so any complete finite list misses a prime. On the other hand, we showed that N is not always prime (but you need to use the first six primes to discover this).
We moved on to resume our discussion of continued fractions from last week. We investigated repeated continued fractions and found some interesting patterns (see this week's homework, especially problem one). Then we sketched (very sketchily) a proof that truncating a simple continued fraction for an irrational number x produces a (fairly decent) rational approximation x. More sketchy details can be found in the homework (problems 2 and 3).
Finally, we turned to modular arithmetic. Soon we were simplifying quantities and solving equations, all modulo n. We managed to reach a simplified version of the Chinese Remainder Theorem; see the homework (problem four for more modulo arithmetic problems and problem five for Chinese Remainder Theorem problems). See also the web links below for some history.
Problem 2: PDF only
The first portion of today's class was devoted to a brief introduction to prime numbers. We used the Sieve of Eratosthenes to show we could construct all prime numbers, given enough time. We also discussed the unique factorization property of the integers and showed that ``primes'' in the set of numbers {4k+1} = {1,5,9,13,...} do not share this property. We also used the unique factorization property of the integers to show that the square root of two is irrational.
The bulk of today's class, however, was spent considering simple continued fractions. (See this week's homework for a specific definition and notation.) We showed that a number has a finite such continued fraction exactly when it is rational. We then moved on to the irrational numbers, or infinite simple continued fractions. After computing the simple continued fraction for various square roots, we discussed approximating irrationals by fractions. There was an attempt to come up with a vague notion of better or worse approximations; perhaps we'll cover this better (more precisely) in the future.
Problem 6(b): PDF only
The first part of this class was devoted to a discussion of the division algorithm, greatest common divisors (gcds), the Euclidean algorithm for computing a gcd. We used this algorithm in reverse to solve the Diophantine equation ax+by=c for integers x and y whenever c divides gcd(a,b). We finished this portion of the subject with a discussion of why this is precisely when we can solve for x and y.
The second portion of the class was devoted to a discussion of Pythagorean triples. These are triples of positive integers (a,b,c) that are the sides of a right triangle, so that a2+ab=c2. This is a primitive Pythagorean triple if a, b, and c have no common factor (that is, that gcd(a,b,c) = 1). We proved, by construction, that there are infinitely many such primitive triples. Note that our construction missed some triples; see the homework for a general form of (all) primitive Pythagorean triples.
A classic. Originally published in 1938, the fifth edition that I'm looking at is from 1979. This is such a popular book that there is an index on-line. It may be a bit over our heads, but it contains much of what we have done in the first seven weeks.
This text takes an unusual approach: it is a collection of problems, with solutions at the end of each chapter. This is my most frequently used reference through the first six or seven weeks, as it often has interesting questions that lead to an understanding of a theorem, rather than just a proof.
This is a wonderful, recent book that is intended as an introduction to a pure mathematics discipline for interested non-majors. As a recent text, however, it isn't cheap (over $100 Canadian). The author has a web page for the book.
Apparently it first arose as a problem posed by Sun Zi (probably third century) and solved in generality by Qin Jiushao (in the thirteenth century). There are other sites that mention this as well. Feel free to search.