An Inquiry Based Learning
Course in Number Theory

Welcome to the Math 311 course website! Before we get started, I thought I should explain the unusual setup of this course. We're going to be learning number theory through Inquiry Based Learning (IBL), sometimes called the Modified Moore Method. Why are we doing this? Well, researchers have a lot of positive things to say about IBL; things you learn in an IBL course stick in your brain for longer, and the meta-skills you acquire in an IBL course will actually help you do better in future math classes -- even if they aren't number theory!

The day-to-day activities of this course might feel strange and unfamiliar at first, but I'll do my best to keep us all on the right track. I'll be documenting our daily activities and successes on the Course Log, and I'll use this as a place to keep everyone in the loop on due dates. I'm looking forward to a great semester!

On Wednesday 08.29.18 I'm going to ask you to come to class with a short (250-500 word) reflection on the essay A Mathematician's Lament by Paul Lockhart. We will also take some time on Wednesday to discuss your reactions to the essay.

Today we prove three theorems about congruence.

• Theorem 1.6 For integer a,b,c,d and a natural number n, if a≡b mod n and c≡d mod n, then a+c≡b+d mod n.
• Theorem 1.7 For integer a,b,c,d and a natural number n, if a≡b mod n and c ≡d mod n, then a-c≡b-d mod n.
• Theorem 1.8 For integer a,b and natural numbers n,m if a≡b mod n and then ma≡mb mod mn.

On Wednesday 09.05.18 I'd like you to come to class prepared to hand in proofs and/or counterexamples and explanations for the following two conjectures.

• Conj. For integer a,b,c,d and a natural number n, if a≡b mod n and c≡d mod n, then ac≡bd mod n.
• Conj. For integer a,b,c,d and a natural number n, if a≡b mod n and c ≡d mod n, then a/c≡b/d mod n.

Also remember your first homework assignment will be due on Friday 09.07.18.

I really enjoyed reading and hearing your reflections on the Paul Lockhart essay. I've pulled out a few tidbits from your individual essays that I enjoyed. One of you said

"Specific problems in math will not be remembered by students…learning is not about remembering; it's about the process of learning…"

and another one of you said

"…this article made me love math even more that I did before reading it, and it made me realize why I love it so much."

Today we proved the following theorem:

• Theorem 1.5 For a natural number n, congruence modulo n is reflexive, symmetric, and transitive.

And don't forget, your first homework assignment will be due on Friday 09.07.18. The problems are quite challenging, so it's best you get started early.

Today we learned definitions for divides and congruent modulo n. There will be a terminology section on the midterm and final, so it's a good idea to keep a list of terms and definitions. Using these definitions we made some conjectures and proved the following theorems:

• Theorem 1.1 For integers a, b, and c, if a divides b and a divides c, then a divides b+c.
• Theorem 1.2 For integers a, b, and c, if a divides b and a divides c, then a divides b-c.
• Theorem 1.3 For integers a, b, and c, if a divides b and a divides c, then a divides bc.
• Theorem 1.4 For integers a, b, and c, if a divides b and b divides c, then a divides c.

I'll be keeping a running document with all of our theorems as they are established, you might want to do the same. For the midterm and final, I will print a copy of this list for each of you to use during the exam.

Great work today! For next time, please come prepared with your short (250-500) word reflection on A Mathematician's Lament. If you wish, you can begin to start thinking about the Homework 1 problems which are due on Friday 09.07.18.

Today we discussed the notion of common divisors and greatest common divisor and we proved the following two theorems:

• Theorem 1.11 For integers a,b,n,r and k, if a=nb+r, k | a and k | b, then k | r.
• Theorem 1.12 For integers a,b,n and r, if a=nb+r then gcd(a,b)=gcd(b,r).

We used these theorems to develop (and sort of prove) the Euclidean Algorithm for finding the greatest common divisors of two numbers. You have no homework this weekend, so relax and enjoy.

Euclid, Mid 4th century BC

Your first homework is due on Friday 09.07.18. I removed two of the problems from the homework, please see the updated homework 1 to make sure you do the correct problems.

Today we learned the Well Ordering Axiom for the natural numbers and the an important new theorem called The Division Algorithm. In addition we proved the following two theorems (the first one you actually did for homework):

• Theorem 1.9 For integer a,b,c,d and a natural number n, if a≡b mod n and c≡d mod n, then ac≡bd mod n.
• Theorem 1.10 For integer a,b and a natural number n, a≡b mod n if and only if a and b have the same remainder when divided by n.

In case you are wondering, the homework will be graded according to the following scheme:

• 10 points Perfect. Valid reasoning, follows all guidelines for writing, no errors of any kind.
• 9 points Valid reasoning, follows all guidelines for writing, but minor error (note singular) in writing.
• 7 points Significant mathematical progress has been made towards a proof but either the argument has one major error or it is not properly written.
• 5 points Some significant mathematical progress has been made towards a valid proof but there are key errors present in the mathematics or major issues with the written presentation.
• 3 points Evidence of having at least one good idea and making an effort to write a formal proof.
• 0 points Essentially no progress has been made towards a valid

Today we talked about proofs involving the Fundamental Theorem of Arithmetic, such as

• Theorem 2.2 For natural numbers a and b, if a²|b² then a|b.

We worked on proofs of the following two theorems which use similar principles to the one above.

• Theorem 2.3 For integers a,b,and n, if a|n, b|n, and gcd(a,b)=1 then ab|n.
• Theorem 2.4 For p prime and integers a and b, if p|ab then p|a or p|b.

On Monday 09.17.18 you will submit proofs of Theorems 2.3 and 2.4 above, and also remember that Homework 2 will be due on Friday 09.21.18. have a nice weekend!

Today we started our second chapter all about primes numbers. We defined the terms prime and composite and learned some good methods for finding primes, and the following theorem:

• Theorem 2.1 A natural number $n$ is prime if and only if for all p<√n, p does not divide n.
• Fundamental Theorem of Arithmetic Every natural number greater than 1 is either a prime number or it can be expressed uniquely as a product of primes.

Remember that Homework 2 will be due on Friday 09.21.18.

Today we discussed some applications of the Euclidean algorithm. In particular we showed how the raw material generated in the Euclidean algorithm can be used to solve diophantine equations, and then we showed how this method can be used to prove the following theorem and its corollary:

• Theorem 1.13 For integers a,b and d, the diophantine equation ax+by=d has a solution (with x and y integers) if and only if gcd(a,b)|d.
• Corollary For integers a and b the diophantine equation ax+by=1 has a solution (with x and y integers) if and only if gcd(a,b)=1.

Then we finished class by observing that when a diophantine equation has one solution, we can actually find infinitely many solutions. That is described in the following theorem which you will be asked to prove in Homework 2:

• Theorem 1.14 For integers a,b if x' and y' are integral solutions to the diophantine equation ax+by=d, then all solutions are given by x=x'+(b/gcd(a,b))t and y=y'-(a/gcd(a,b))t where t is an integer.

Homework 2 will be due on Friday 09.21.18.

Today we learned the definitions of the canonical residue system modulo n and a complete residue system modulo n, and we saw the connection between linear congruences and linear diophantine equations with the following theorems:

• Theorem 3.2 For an integer a and natural number n, there is a unique integer t in {0,1,...,n-1} such that a ≡ t mod n.
• Theorem 3.3 For integers a,b,n with n>0, ax ≡ b mod n has a solution if and only if there exist integers x and y such that ax+ny=b.
• Theorem 3.4 For integers a,b,n with n>0, ax ≡ b mod n has a solution if and only if gcd(a,n)|b.
• Theorem 3.5 For integers a,b,n with n>0, if x' is a solution to ax ≡ b mod n, then all solutions are given by x'+(n/gcd(a,n))m mod n where m=0,1,...,gcd(a,n)-1.

You have no homework this weekend, but keep in mind that our first exam will be on Friday 10.12.18.

Today we talked about the importance of congruence arithmetic for solving higher order problems and had the following theorem without proof:

• Theorem 3.1 For a polynomial f(x)=a_kx^k+a_k-1x^k-1+...+a₁x+a₀, if a ≡ b mod n then f(a) ≡f(b) mod n.

We will continue this discussion on Friday, and you will be handing in Homework 2.

Today we finished our discussion of primes and proved the following lemma and subsequent theorem:

• Lemma For any natural number n, gcd(n,n+1)=1.
• Theorem 2.5 There are infinitely many primes.

We also learned about arithmetic progressions and saw a few results without proofs for Dirichlet's Theorem on Primes in Arithmetic Progressions, Green and Tao's Theorem, The Twin Prime Conjecture and The Goldbach Conjecture. If you are curious, here is a link to the video I mentioned in class today about Yitang Zhang and the Twin Prime Conjecture. It's really good.

Today we started the conversation about multiplication in the context of congruences and what it means for the powers to cycle modulo n. We proved the following two theorems:

• Theorem 1.15 For integers a,b,c and natural number n if ac ≡ bc mod n and gcd(c,n)=1 then a ≡ b mod n.
• Theorem 4.1. For natural numbers a and n there exists natural numbers i and j with i ≠ j such that aⁱ ≡ a^j mod n.

And I've asked you to write up the following proof to hand in on Monday:

• Theorem 4.2 For natural numbers a and n if gcd(a,n)=1 then there exists a natural number k such that a^k ≡ 1 mod n.

I won't be here on Friday, so there will be no class. I mentioned a possible reading assignment, but since you already have one proof due on Monday and Homework 3 due on Friday 10.05.18, I'll save that reading for another weekend.

Today we further discussed solving linear congruences and learned the Chinese Remainder Theorem. Homework 3 will be due on Friday 10.05.18.

If you want to read a super article about all that drama with the abc conjecture, I suggest you try this one in Quanta; it's really down to earth and easy to read. And stay tuned for more about the Riemann Hypothesis.

It looks like I forgot to update the website on Wednesday, so let me recap what we did the last two class meetings. We defined a few new terms: Euler Φ-function, inverse modulo p. And we proved the following theorems:

• Fermat's Little Theorem For p primes, and gcd(a,p)=1, a^p-1 ≡ 1 mod p.
• Euler's Theorem For integers a and n, with n>0 and gcd(a,n)=1, a^Φ(n) ≡ 1 mod n.

Next Friday, 10.12.18, we will have our midterm, it will include terminology, computational problems, and one proof. Also (since I think it's a good time for something uplifting) for Monday, please read this article Mathematics for Human Flourishing and write a paragraph or two describing your impressions. We will have a brief discussion of the article in class in Monday.

Today we learned the definition of order modulo n and proved an important theorem about order

• Theorem 4.3 For natural numbers a and n, with gcd(a,n)=1 and ord_n(a)=k, then a^m≡ 1 mod n if and only if k | m.

Recall that Homework 3 due on Friday, also you should begin to have on your radar our Midterm, which will be next Friday, 10.12.18.

First, as promised here is the complete proof of the conjecture we were discussing about the Euler Φ-function on Monday.

To finish up this section we have two final theorems. The one proved above, and one that we only kinda sorta half proved on Friday, but that's ok, I'll take it!

• Theorem 4.4 For a prime p and natural number m, Φ(p^m)=p^m-p^m-1
• Wilson's Theorem For a natural number n, (n-1)! ≡ -1 mod n if and only if n is prime.

The exam will be on Friday 10.12.18. I've decided to do a take-home portion of the exam. You may use your notes from class and I'll hand out this theorem list on Friday, but those are the only permissible resources (other than your own infinitely powerful brain).

This week we started our tour of cryptography with a discussion of caesar ciphers and polyalphabetic caesar ciphers. Eventually we will develop a stronger version of cryptography using the theorems we proved today:

• Theorem 5.1 If p and q are primes and W is a natural number less than p,q then W^(p-1)(q-1) ≡ 1 mod pq.
• Theorem 5.2 If p and q are primes and W is a natural number less than p,q then W^1+(p-1)(q-1) ≡ W mod pq.
• Theorem 5.3 If p and q are primes and E is a natural number relatively prime to (p-1)(q-1), then there exist natural numbers D and y such that ED=1+y(p-1)(q-1).
• Theorem 5.4 If p and q are primes and W is a natural number less than p,q and ED=1+y(p-1)(q-1) then W^ED ≡ W mod pq.

We will continue to talk about cryptography for the next week and Homework 4 will be due on Friday 10.26.18.

Today we learned the definition of primitive root modulo p and the following theorems about higher order congruences:

• Theorem 6.1 Suppose p is prime, ord_p(a)=d and gcd(i,d)=1, then ord_p(aⁱ)=d.
• Lagrange's Theorem If p is prime and f(x) is a degree n polynomial then f(x) ≡ 1 mod p has at most n incongruent solutions modulo p.

You have no homework over the weekend, but if you haven't done so yet, please start thinking about what topic you'd like for your end of semester research project.

Wonderful job on the scavenger hunt today, and congratulations to the winners!

Homework 4 will be due on Friday 10.26.18.

On Wednesday please come on time and meet me at my office, 422 College Hall.

Today we proved a few more lemmas in preparation for the big one:

• Theorem 6.4 For any natural number n, ΣΦ(d)=n where the sum is take over the divisors d of n.

For Monday 11.05.18 please bring a written proof of Theorem 6.4. Also, remember that there is a seminar at 2:00 on Monday afternoon in College Hall 446.

Today we proved a few more theorems about primitive roots:

• Theorem 6.2 For a prime p and a natural number n, there are at most Φ(d) many incongruent integers modulo p that have order d modulo p.
• Theorem 6.3 For a prime p and a primitive root g, the set {0,g,...,g^p-1} is a complete residue system modulo p.

On Friday 11.09.18 Homework 5 will be due.

This week we finally proved the big conjecture we were working towards.

• Theorem 6.5 Every prime p has a primitive root.

We also started thinking about higher order congruences and we started by exploring when an expression like

should have a solution, and what a good strategy is for finding the solution.

On Wednesday 11.14.18 there will be a seminar talk on Cryptography by Dr. Ben Kane who is visiting from the University of Hong Kong. The talk is in College Hall 446, 2:00-2:50. If you are unable to attend, let me know. Also, Homework 6 will be due on Friday 11.30.18.

After the Thanksgiving break we will start the research presentations. If you have a strong preference for your time slot let me know, otherwise I will post the schedule of talks here before break.

This week we finished our exploration of primitive roots with the following theorem:

• Theorem 6.6 For natural numbers k, b and an integer n, with gcd(k,Φ(n))=1 and gcd(b,n)=1, then the congruence

  x^k ≡ b mod n

  has a unique solution modulo n given by

  x≡ b^u mod n

  where u is a solution to the diophantine equation ku+Φ(n)v=1.

Homework 6 (your last homework set of the semester!) is due on Friday 11.30.18.

The schedule and order of research presentations will be as follows:

• Monday 11.26.18: Paige, Elizabeth
• Wednesday 11.28.18: Sean, Kaitlyn
• Friday 11.30.18: Matt, Marie
• Monday 12.03.18: Kristin, Mikayla
• Wedesnday 12.05.19: Vincent, Brittany

Please remember your talk should be somewhere between 20-25 minutes, but not any longer. You can do a Power Point or you can write on the white board if you prefer (or both!), and you should prepare some sort of handout material. For guidance on preparing your talk, check the presentation grading rubric and let me know if you have any questions.

Have a very happy Thanksgiving!

We've made it to the end of the semester! Our final exam will be broken into two pieces:

• An in-class portion with terminology and computational problems on Monday 12.10.18.
• A take-home proof based portion due to me by 10:30 AM on Tuesday 12.18.18.

For the in-class portion I will be handing out this Theorem List, you can also use that on the take home part (along with any notes from class). On Friday 12.07.18 we will do some review problems for the in-class portion, and I will hand out the take-home portion. Please come to class prepared with any questions...about anything!