Wednesday, 5:00 - 8:00, SEO 600

Instructor: Louis H. Kauffman

Office: 533 SEO

Phone: (312) 996-3066

E-mail: kauffman@uic.edu

Web page: http://www.math.uic.edu/~kauffman

Office Hours: 3PM to 4PM on MWF.

This is a course on elementary number theory. We will begin by recalling basic arithmetic, looking at it all over again and seeing how it works.

See ContFrac. This is a calculator on the web that converts numbers to their continued fractions. Try it on sqrt(2), sqrt(3), e, pi and other favorite numbers.

See PrimeFactor. This is a calculator on the web that factors numbers.

See Fractions and Decimals . This is a great page on fractions and decimals including a calculator for converting fractions to decimals and finding the perionds.

See Fraction to Decimal Converter . This is a sequel to the page above with a specific fraction to decimal converter.

See Roots of Two. This is a Wiki about the relationship of the twelfth root of two and the musical scale.

See Ulam Spiral 1. This is a Wiki about the structure of the primes and the Ulam Spiral.

See Ulam Spiral 2. This is a demo about the structure of the primes and the Ulam Spiral.

See Ulam Spiral 3. This is a YouTube Video about the structure of the primes, Ulam Spiral and the prime 41.

See Pebble Pythagoras. This is a proof that the square root of two is irrational via dot patterns or as the author of this book say, by "pebbles".

See Vi Hart. This is a link to math videos by Vi Hart.

See Time Line. This is a time line for the history of past and present mathematics. It is by no means complete, but you can use it to locate topics and to find when some ideas and results happened.

Recommended Book: "What is Mathematics?", Oxford Univ. Press, by Richard Courant and Herbert Robbins. This book is available at the UIC bookstore and also via Amazon.

Recommended Book: "The Heart of Mathematics - An invitation to effective thinking." by Edward B. Burger and Michael Starbird. Published by John Wiley & Sons. Inc. This book is available via Amazon.

Course Notes 1.

Course Notes 2.

Course Notes 3.

Course Notes 4 : Knots and Numbers.

Course Notes 1,2,3,4 in one pdf file.

First Assignment: Read in "What is Mathematics" Section 1 - Calculation with Integers, Section 2 - The infinitude of the number system - mathematical induction -- Parts 1, 2 and 4. Read Part 1 about prime numbers in the Supplement to Chapter 1. For homework, we have the following problems: (a) See if you can find a "pattern proof" (as we did in class for 1 + 3 + 5 + ... + (2n-1) = n x n) for the formula 1^3 + 2^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2 = (T_n)^2. You can work at this on your own or do some web browsing. Try searching google with the phrase "squared triangular number" and see what you get. Squared Triangular Number. Or search on google image for "proofs without words" and then explore what you get. Proofs Without Words. (b) Is 13721731779 a prime number? What about 13721731777? (c) Figure out good tests to determine if a number is divisible by 4, 6 or 8. (d) List all the prime numbers that are less than 100. Explain what you would do if you were asked to find all the prime numbers less than 500. The problems in this assignment are due Wednesday, August 31,2016.

Second Assignment and Third Assignment: Read In "What is Mathematics" Section 2 of the Supplement, pages 31 to 38. For the second assigment, read pages 42 - 51 about the Euclidean Algorithm. Watch for a new version of the Course Notes. It has arrived! For homework, we have the following problems: (A) Find a rectangular sheet of paper and fold off squares to estimate the Length/Width ratio. Hand in your folded and marked rectangle and your continued fraction calculation for the estimate. Also measure your rectangle with a ruler and compare your continued fraction result with the ruler-measurement result. (B) Work out the decimal expansion and period for 1/13. Show your division work and also do it by "short division". (C) Read the Course Notes on 1^2 + 2^2 + ... + n^2 and explain these results and why they work in your own words. If you can find someone to explain them to that would be a good way to prepare for writing this part of the assignment. (D) Consider the numbers 10^n (mod 13) for n=1,2,3,.... Find the residues for each one as members of the hours on a thirteen hour clock {0,1,2,3,4,5,6,7,8,9,10,11,12}. On that clock we throw away multiples of 13, takeing them to be the same as zero.For example, 7^2 = 49 = 39 + 12 = 3 x 13 + 12, so 7^2 is congruent to 12 (mod 13) and the residue of 7^2 mod 13 is 12. (E) Work out the residues for 10^n (mod 11) (n=0,1,2,3,...) and use this information to devise a "digital root" that can tell you when a number is divisible by 11. (F) Here is another proof that there are infinitely many primes. Consider the numbers n! + 1 (n = 1,2,3,...). For a given value of n, n! + 1 is NOT divisible by any of the numbers 2,3,4,...,n (It leaves a remainder of 1.). Thus n!+1 must be divisible by some prime number bigger than n. This means that for every natural number n, there are primes bigger than n. This means that there must be infinitely many primes. Your problem is to make a table of the numbers n! + 1 for n=1,2,3,4,5,6 and factor each number into primes. Wilson showed (Wilson's Theorem) that if p is a prime number, then p divides (p-1)! + 1. Check this for p = 2,3,5,7,11. Wilson also showed that if p is NOT prime, then p does NOT divide (p-1)! + 1. Thus Wilson found an airtight test for primality. But it is not useful in practice since n! gets very large even for small values of n. The problems in this assignment are due Wednesday, September 14, 2016.

Fourth Assignment: Read In "What is Mathematics" Section 2 of the Supplement, pages 38 to 40. For homework please do the following problems. (A) In "What is Mathematics" on page 38, do problems (1) and (2). (B) Find the residue of 10^(1111111117) mod 11. (C) Find the remainder when 123456789 is divided by 11. (D) Find the residue of 10^(1377) mod 7. (E) Show that 7 is prime by verifying directly that 7 divides (1 + 6!). Look up Wilson's Theorem on the Wikipedia and read about it. (F) A non-zero number a is said to be a "quadratic residue" (mod p) if a == x^2 (mod p) for some x. Here we use == for congruence. For example, 2 == 9 == 3^2 (mod 7) so that 2 is a quadratic residue (mod 7). Find all the quadratic residues (mod 7) by squaring each number 1,2,3,4,5,6 and getting its residue class. Do the same for all residues (mod 2), (mod 3), (mod 5) and (mod 11). (G) In some modular number systems we can have two non-zero residues with a product that is zero. For example 2 x 3 == 6 == 0 (mod 6) but 2 and 3 are not zero (mod 6). Can this happen if the modulus is a prime number? Think about this question and give your reasons for your answer to the best of your ability! The problems in this assignment are due Wednesday, September 21, 2016.

Fifth Assignment: Read In "What is Mathematics" Section 2 of the Supplement, pages 38 to 40 and pages 42-47. These last pages are about the Euclidean algorithm. We will also have notes on the Euclidean algorithm and I will indicate when they are available. See also Euclid's Algorithm Wiki. In the Wiki read through it and see which parts are now understandable to you. We will discuss this in class. (A) Find by using the Euclidean algorithm the greatest common divisor g of 1071 and 462. Show all the details in your calculation. (B) Use the calculations in part (A) to find integers a and b so that 1071 a + 462 b = g where g is the greatest common divisor of 1071 and 462 that you have already found. (C) Express 1071/462 as a continued fraction. What does your answer have to do with part (A) of this problem set? (D) I assert that every natural number (1,2,3,...) can be written uniquely as a sum of DISTINCT powers of 2. For example 39 = 32 + 4 + 1 = 2^5 + 2^2 + 2^0. The method for doing this is to find the largest power of 2 that is less than or equal to the number, and then work with the difference in the same way. For example 1000 = 512 + 488 = 512 + 256 + 232 = 512 + 256 + 128 + 104 = 512 + 256 + 128 + 64 + 40 = 512 + 256 + 128 + 64 + 32 + 8 = 2^9 + 2^8 + 2^7 + 2^6 + 2^5 + 2^3. Find the unique expressions in terms of powers of 2 for the numbers from 1 to 50. (E) Express the first 30 even numbers greater than 2 as sums of two prime numbers. Goldbach's Conjecture states that every even number greater than 2 is the sum of two odd primes. For example 50 = 43 + 7. (F) There exists a natural number n such that both n and n+1 are prime numbers. Find all such n and justify your answer. (G) Prove that it is impossible to have three consecutive integers all of which are prime. (H) Give an explicit list of infinitely many natural numbers that are each not prime. (I) Write a short (not more than a page) imaginative story (it can be humorous, dramatic, whatever you like) that invokes or evokes the ideas about numbers that we have introduced in this course so far. The problems in this assignment are due Wednesday, September 28, 2016.

Sixth Assignment: (You can do parts (A) and (B) immediately. Part (C) will need the new version of the Course Notes. THEY ARE HERE! SEE COURSE NOTES 2 ABOVE. (A) View Ulam Spiral 3. and make your own Ulam spiral starting at 41. Work out for yourself why it is that the Northeast and Southwest corners of the spiral are labeled by the numbers N^2 - N + 41. Suppose that you were to start the spiral at the number 17. Draw it! What would the number sequence be for the Northeast and Southwest corners of this spiral? Are there a lot of prime numbers in this sequence? (B) Here is a remarkable algebraic identity: (x^2 - y^2)^2 + (2xy)^2 = (x^2 +y^2)^2. Verify this by multiplying out and adding up the algebra on the left hand side and showing that it equals the algebra on the right hand side. Now try some examples of this identity by choosing integer values for x and y. For example, if x = 2 and y = 1, then we have (2^2 - 1^2)^2 + (2)^2 = (2^2 + 1^2)^2 and this is same as 3^2 + 4^2 = 5^2. So you see that our identity produces triples of numbers A,B,C so that A^2 + B^2 = C^2. Since these would be integer sides of a right triangle, such triplets are called Pythagorean Triplets after the Pythagorean Theorem. Find values of x and y that produce the triplet 5, 12, 13. Find other triplets by trying other values of x and y. Look up the Wikipedia article on the Pythagorean Theorem and find some part of it that you find interesting. Report on that part that you found. (C) Find integers a and b so that 73 a + 51 b = 1. Do this by using the Euclidean algorithm and then by using the matrix method that we discussed in class. (Notes on the matrix method will be available shortly.) Remember that you can check the continued fraction for 73/51 from the calculator on our website. You should find that 73/51 = [1,2,3,7]. Calculate the fraction for [7,3,2,1] = 7 + 1/(3 + 1/(2 + 1/1)) = P/Q: that is find the values of P and Q. You should find that P = 73 and 51Q == 1 mod(73). Next week we will show that this always happens! The problems in this assignment are due Wednesday, October 5, 2016.

Seventh Assignment: Read carefully the proof of Fermat's Theorem (pages 37-38 in "What is Mathematics"). We will discuss the proof in the next class meeting. (A) Read the "pebble proof" that square root of two is irrational. Pebble Pythagoras. We will discuss this proof in class. The proof is based on the "Least Element Principle" for the natural numbers. The Least Element Principle states that ANY SUBSET OF THE NATURAL NUMBERS HAS A LEAST ELEMENT. While this may seem obvious, note that there are subsets of the rational numbers that do not have least elements, for example {1,1/2,1/3,1/4,1/5,...}. The least element principle is very powerful as we shall see. This problem asks you to read the pebble proof as best you can and provide YOUR OWN ILLUSTRATIONS FOR THE PROOF. (B) View some Vi Hart YouTube videos Vi Hart, Vi Hart Mobius. Choose one of these videos that you like and write a report on it, explaining the math in the video and doing some of the drawings or constructions yourself. (C) Recall that we have shown that if the continued fraction [a1,a2,...,an] = P/Q, then [an,...,a2,a1] = P/R where QR == (-1)^(n+1) mod P. Use the continued fraction calculator ContFrac. and determine an R for P = 1023 and Q = 137. Do this by finding the continued fraction for 1023/137. Then write the new continued fraction obtained by using the terms of the first continued fraction in reverse order, and use this to calculate R. Check that R and Q have the right product modulo 1023. Also, check that M(a1)M(a2)...M(an) = {{P,R},{Q,S}} for this example where {{P,R},{Q,S}} denotes a 2x2 matrix with FIRST ROW {P,R} and SECOND ROW {Q,S}. Check also that M(an)M(a[n-1])...M(a2)M(a1) = {{P,Q},{R,S}} as we have explained at the end of the last class. (Here is an example: [1,2,3] = 10/7 and [3,2,1] = 10/3. Note that 7 x 3 = 21 == 1 mod 10. Here you need to compute the matrix products M(1)M(2)M(3) and also M(3)M(2)M(1).) (D) Read the science fiction story by Isaac Asimov The Feeling of Power. As you will see, this story is about a world where people re-discover how to do arithmetic by hand. Comment on this story. Can you imagine having to rediscover how to do arithmetic. Imagine that you no longer know how to do long division or even addition by hand. Could you reinvent it. What would your invention be like? Can you devise some ways of your own to do arithmetic? The problems in this assignment are due Wednesday, October 12, 2016.

Eighth Assignment: Read carefully the proof of Fermat's Theorem (pages 37-38 in "What is Mathematics"). We will discuss the proof in the class. (A) Not only is Fermat's Theorem true, but the following fact is also true: Let p be a prime number and let R(p) = {1,2,...,p-1} be the non-zero residue classes modulo p. Then then there is a number g in the set {1,2,...,p-1} such that the residues of g^1, g^2, g^3, g^4,..., g^(p-1) are exactly the set R(p). For example, let p = 5. and let g = 2. Then (using congruence mod 5) g^1 == 2, g^2 == 4, g^3 == 3, g^4== 1. Thus we get {1,2,3,4} in the order {2,4,3,1} from the powers of g. This problem asks you to find such a g when p = 13. (B) We have remarked in class then if P/Q = [a1,a2,...,an] where n is odd, and the sequence of numbers {a1,a2,...,an} is symmetric in the sense that it is the same as the reverse order {an,...,a2,a1}, then Q^2 == 1 mod P. For example [2,3,2] = 16/7 and 7^2 = 49 == 1 mod 16 (since 3 x 16 = 48). Find all residues g in {1,2,3,4,5,6,7,8,9,10,11} modulo 12 such that g^2 == 1 mod 12. Find the continued fraction expansion for each fraction 12/g where g^2 == 1 mod 12. Which of these fractions are symmetric? (C) Let p be a prime number. Suppose that x is a residue mod p in the set {1,2,3,...,p-1} and that x^2 == 1 mod p. Then we have that x^2 -1 == 0 mod p (by subtracting 1 from both sides of the equation). Since x^2 - 1 = (x+1)(x-1), we have (x+1)(x-1) == 0 mod p. Explain that this means that p divides (x-1)(x+1) and use the result that "if p divides ab then p divides a or p divides b", to conclude that p divides (x-1) or p divides (x+1). Now remember that p is prime and that x is in the set {1,2,3,...,p-1}, and show that the only x that can satisfy one of the other of these conditions is x = 1 or x = (p-1). Illustrate your reasoning using the prime p = 13. (D) Read Matrices and Complex Numbers, and do ALL the exercises in these pages. (E) After you have done (D) note that (x+iy)^2 = (x^2 - y^2) + i(2xy). What does this have to do with our Pythagorean formula (x^2 - y^2)^2 + (2xy)^2 = (x^2 +y^2)^2 ? (F) Examine the Mathematical Time Line. Choose a mathematical topic that occurred after 1600 and look it up. In your looking you can start by using a link provided by TimeLine, but then read that article or look further into references in the article. Keep reading until you find something of interest to you. Report on what you found. The problems in this assignment are due Wednesday, October 19, 2016.

Ninth Assignment: Do the problems in Five Problems. The problems in this assignment are postponed to, November 2, 2016. The next assignment contains an extension of this problem set with three new problems to be handed in on November 2, 2016.

Tenth Assignment: Do the problems in Five Plus Three Problems. See also Course Notes 2. The problems in this assignment are due Wednesday, November 2, 2016.

Eleventh Assignment: Read Some Knot Theory. In this excerpt from Colin Adams' "The Knot Book", please do the following exercises: 1.1,1.3,1.4.1.5.1.6.1.7.1.9.1.10,1.11.1.12.1.21.1.22.1.24.1.27.1.28. You will find that this reading that the exercises are a review, from a slightly different point of view, of the knot theory that we have been doing for the last two weeks. I hope you find Adam's description fun and his exercises helpful! Note that he uses the three-coloring without directly identifying it as a*b = 2b -a mod 3. And in one of the exercises he asks you to work on the figure eight knot using 2b-a modulo 5 as we have done. For just the three-coloring it is useful to do it just with three symbols. You could use R, G and B for the three colors and then you have RG = B = GR and any two different colors combine to give a third color so we have GB = R and BR = G. Any color combines with itself to produce itself RR = R, GG = G, BB= B. (Here I am omitting to write the *. So it should really be R*B = G and so on) Please also do the following exercise about products of squares: Find positive integers E and F so that (3^2 + 4^2)(5^2 + 6^2) = E^2 + F^2. And please do the following reading in "What is Mathematics?": pages 479 - 486 (about the Riemann Zeta Function and the Prime number theorem. Do not worry if you find this hard reading. We will discuss some of it in class. Here are some other links that are relevant to this assignment. Tricolorability. Jozef Przytycki. Ben Webster. Knots and DNA. The problems in this assignment are due Wednesday, November 9, 2016.

Twelveth Assignment: Do the problems in Problemset. Use Number Theory Notes 3. For the Tower of Hanoi, you may wish to use Tower of Hanoi Demonstrator. Look at the knot game at Ayaka Shimizu's Game. Play the game! Read Ayaka Shimizu's Paper about the game. Write about your experience playing this game. Can you find a good strategy for winning? The problems in this assignment are due Wednesday, November 16,2016.

Thirteenth Assignment: See the end of this assignment for the problems. Please read (again!) the section on quadratic reciprocity in "What is Mathematics". This is pages 38 to 40. Please read about Mersenne Primes and Perfect Numbers in a document downloaded from the web. Here is a link to the game Reverse (also called Othello) that we have discussed in class. Reversi. Here is a link to the Khan Acadamey video lessons about RSA Codes. Please watch to the basic lessons on the RSA codes given there. RSA. Here is a link to two articles about DNA and Tangles and a link to a YouTube about DNA replication. Tangles and DNA - Kauffman and Lambropoulou. Tangles and DNA - Sumners. DNA Replication. You will find a lot of YouTube videos of this type. Look around! Do the problems in Problemset. Use Number Theory Notes 3. Use Some Knot Theory. Problems for this assignment are due on November 23, 2016.

Fourteenth Assignment: In this course, we have discussed a lot of different topics in mathematics, some that have "no lower age limit" and some that would be suitable for older children like ourselves. Make a list of as many "no lower age limit required" topics that you can think of (mathematical, but not limited to this course). Choose three such topics and describe how you would use them to arouse interest in mathematics in young learners. This assignment, is due on November 30, 2016.

BEYOND THIS POINT ARE MANY SUGGESTIONS FOR READING AND PROJECTS.