Math 11200, Fall 2006
Studies in Mathematics- Number Theory
Office hours: Sunday 1:30-3:30 PM and Thursday 5:30-6:30 PM Math/Stat 202 (here's a map)
Tutorial 1: T/Th 9-10:20 AM, GB 411
Lesley,
Jessa,
Nick H.,
Tracy,
Alex, Troy, Natalie, James, Phil
Tutorial 2: T/Th 12-1:20 PM, GB411 (Note room change)
Lakotah,
Martin,
Petra,
Nick N.
Homework
Due Wednesday November 29th: (Official Version) (Last HW!)
1) Review Chapter 6 up to "Rings" and today's class notes. Also read the zero divisors section (Note: they define commutative ring differently in the Ring section here than they did earlier. We will keep the old definition, so disregard this difference). Pay special attention to the definition of "order of an element" and practice problem 6.10.
2) Chapter 6, Exercises 6.5, 6.9 (The first sentence should read: "Find all the generators of Z_20 under addition."), 6.21
3) Is U(9) under multiplication a cyclic group? Is U(12) under multiplication cyclic? In each case, if the group is cyclic, find all possible generators and find the order of these generators. Otherwise show (as in Practice problem 6.10) that the group is not cyclic. In both cases, what is the order of the group? How does the order of the group compare to the order of any generators?
Notes: Quiz tomorrow. Think about when you would like office hours for the final.
Due Monday November 27th: (Official Version)
1) Have a very Happy Thanksgiving!
2) Read/Review Chapter 6 up to "Rings." Review today's class notes before Monday.
Definition: The order of a group G is the number of elements in the set G.
3) Write out the multiplication tables for U(3), U(8), and U(9). State in each case what the order of each of these groups is.
Notes: NO OFFICE HOURS THURSDAY OR SUNDAY! (We'll have more next week in preparation for the final)
Due Wednesday November 22th: (Official Version)
1) Read 6.2 through Cyclic groups
2) Chapter 6, Exercise 6.11 (This really is a proof by well-definedness), 6.22bcdef (Finally an example of a non-abelian group!)
3) Let S be a set with a binary operation x (read times). Suppose S has a multiplicative identity 1 and (S, x) satisfies associativity. Prove if a and b in S have multiplicative inverses, then (axb) has a multiplicative inverse.
Notes: OFFICE HOURS CHANGE Tomorrow Tuesday 2-3 PM (Obviously none on Thursday!)
Due Monday November 20th: (Official Version)
1) Review 6.1 (work through the Practice Problems), Start reading 6.2
2) Chapter 6, Exercise 6.6
3) Prove Theorem 6.4(ii) (We did (i) in class on Wednesday). Remember to use the definition of A+B and AB when A and B are residue classes modulo m.
4) Do the first challenge problem below Theorem 6.4 (on p. 166 in my book). We showed that the residue class containing 0 is the additive identity in class. Write this up formally, and prove that the residue class of 1 is the multiplicative identity. Remember to use the definition of A+B and AB in your proofs.
5) (Don't need to write up) Convince yourself that One's Digit Arithmetic is the same as Residue Class Arithmetic modulo 10.
Notes: Office Hours Wednesday 6-8PM, Thursday (NOTE CHANGE!) 6:30-7:30 in my office, Rough Draft for EC due Monday.
Due Wednesday November 15th: (Official Version)
1) Read 6.1, Study for Midterm
2) Chapter 6, Exercises 6.1ab, 6.2abc, 6.3ab, 6.10 (Also explain what these n distinct residue classes are).
3) Show that n is congruent to 0 mod m if and only if m divides n. ("if and only if" is a mathematical way of saying the two statements are equivalent. You can think of it as saying each individual statement implies the other. To prove this statement, you should show that if n is congruent to 0 mod m then m divides n AND if m divides n then n is congruent to 0 mod m.)
Notes: Office Hours Wednesday 6-8PM, Thursday 5:30-6:30 in my office, Rough Draft for EC due next Monday.
Due Monday November 13th: (Official Version)
1) Read the first half of 6.1, Study for Midterm
2) Chapter 4 Exercise 4.17
(Note that there is a k such that mk=N, then use Thm. 4.3.),
3) Chapter 4 Exercise 4.23
(Show this by using Bezout's Thm. I.e., you want to show there exist m and n such that ma+nc=1. Then by Exercise 4.6 (which you already did), (a, c)=1. Do the same with b and c. To start off, note that by Bezout's theorem, there are u and v such that ua+vb=1. Use the definition of c|(a+b) to get what you want.)
4) Determine whether the following numbers are divisible by 3 (using our new divisibility test): 86, 555, 5555, 987654321, 123456789, 192837465
Random Notes: Office hours: Sunday 1:30-3:30, Test Nov. 17th, Start thinking about when you want OH next week. I'll post the review sheet sometime Saturday.
***
Due Friday November 10th: (Official Version)
1) Read 4.3. We'll be starting Chapter 6 as well on Friday.
2) Chapter 4 Exercises: 4.7d, 4.9, 4.10 (On 4.9 and 4.10, they mean use the Bezout Algorithm we developed. In 4.9, find m' and n' to satisfy 3m'+5n'=1. Then use m' and n' to find the m and n they suggest in the problem).
Notes on Exercise 4.7d. This question provides an alternate proof of Bezout's theorem. Let a, b>0. Then S(a, b) in the problem is a set which is closed under subtraction and consists of more than just 0. Thus, we can apply problem 4.5 (Why?). Use 4.5d to show that if d is the least element of S(a, b), d divides all elements of S(a, b) (You don't need to reprove theorem 4.5d, just use the statement). But you showed in 4.7b that a and b are elements of S(a, b). So d is a common divisor of a and b. To show d=(a, b), we will show (a, b) divides d (Why is this enough?). To do this, follow the instructions given in the last two sentences of the problem. In your write up, I want you to present this problem as a proof of Bezout's theorem. Explain all of the steps above in COMPLETE SENTENCES and explain as well why this is a proof of Bezout's Theorem.
Random Notes: Office hours: Thursday 5:30-6:30, Quiz tomorrow, Test Nov. 17th
***
Due Wednesday November 8th: (Official Version)
1) Review the Euclidean Algorithm. Read 4.2 (We'll finish it up on Wednesday), and begin reading 4.3.
2) Chapter 4 Exercises: 4.2, 4.3. 4.8 (4.8 is asking you to find the m and n as in Bezout's Theorem, see the example given in the problem, and my write up of the example we did in class. It would be best to do this problem concurrently with 4.3).
3) Let a, b be two positive numbers. Show that if d is a common divisor of a and b, then d divides (a, b). Hint: By Bezout's theorem, there exists m, n such that ma+nb=(a, b). (This is the added information you needed to prove exercise 3.16 about the gcd of three numbers. Notice how easy this proof becomes with Bezout's theorem.)
***
Due Monday November 6th: (Official Version)
1) Review 4.1 and read 4.2 (We'll be talking about/proving the Euclidean Algorithm on Monday).
2) Finish the postponed assignment.
3) Suppose a and b have the same remainder r when they are divided by n. Show that n divides (a-b).
4) If a | bc, must a | b or a | c? Give an example where this is not true. If a is 1, the statement holds. What if a is prime? Try to explain your answer briefly (but NO PROOF is necessary...I just want you to play with these questions a bit).
5)Notes: This weekend I will be posting an extra credit project. Check back if you are interested. I as usual have OH Sunday 1:30-3:30 PM
***
Due Friday November 3rd (Postponed): (Official Version)
1) Read 4.1 and 4.2 (We'll be proving Thm. 4.1 in class so definitely read it over before Friday).
2) Chapter 4, Exercises: 4.1, 4.5 (Definitely talk about this one in tutorial... use the statement of the division algorithm in part d), 4.6 (Hint: let d be a common divisor of a and b, show d divides 1), 4.7abc
3) Notes: My office hour tomorrow is 4:30-5:30 (an hour earlier than usual!)
***
Due Wednesday November 1st: (Official Version)
1) Start reading 4.1, and review theorems we proved in class from 3.2 and 3.3.
2) Chapter 3, Exercises: 3.1, 3.2g, 3.11, 3.16 (These last two will go somewhat like Theorem 3.7 part 2.)
3) Let x denote multiplication and sqrt(b) denote the square root of b. Prove if a x k = b then either a is less than or equal to sqrt(b) or k is less than or equal to sqrt(b). (Assume for a contradiction that a > sqrt(b) and k > sqrt(b). Then use the order axioms.) Conclude that if n is composite, then it has a divsor that is less than or equal to sqrt(n). This is a useful bound on how high you have to look for divisors to check if a number is prime.
***
Due Monday October 30th: (Final official version)
1) Read 3.2, 3.3 (especially up to p.102), go over Theorem 3.7 (We did the first part in class, and we'll do second part on Monday). Doing the reading before class is getting more important since the theorems we are proving are getting harder.
2) Chapter 3, Exercises: 3.7befghij, 3.12 (Hint: First write out the definition of GCD in this case. Then find a way to apply Thm. 3.3.), 2.20a (Hint: We want to show S=N, so our "bad set" will be B={x in N | x is NOT in S}. If we show B is empty, then S will equal N. Now, assume for a contradiction that B is NOT empty. Then apply Well ordering.)
***
Due Friday October 27th: (Final official version)
1) Read 3.2, 3.3, go over Theorem 3.6 we did in class (It was tricky!)
2) Prove the lemma we used in class today, ie, let S be a commutative ring satisfying the order axioms, and let a, b, k be in S. If ak=b and a>0 and b>0, prove k>0. (Hint: Assume for a contradiction that k<0 or k=0. The case k=0 is easy. If k<0, use the flip theorems to reach a contradiction.)
3) Prove Thm. 3.5 in the book without using any of the divisibility theorems. (Just prove it from the definition of divisible.) This theorem says that if a divides b and c, then a divides any "general" sum of b and c.
4) Chapter 3, Exercises: 3.2ac (Do more of the problem if this does not seem easy), 3.10abcde (Prove the ones which are true, and give a counterexample for those that are false).
***
Due Wednesday October 25th: (Final official version)
1) Read 3.1, 3.2
2) Prove the sum of the first n odd numbers T(n) equals nxn (ie, n squared). We did most of it in class, but fix my errors from last week in the computations. Make sure you understand why this proof makes sense (since it can be a bit mysterious at first).
3) Let S(n) be the sum of the first n positive numbers. For example, S(5)=1+2+3+4+5. Prove using the well ordering principle that S(n)=0.5(n+1)n. Follow the same method you used for the above problem.
4) Read (or prove or your own!) Thm. 3.2 carefully. For homework, show (the similar theorem) that if a divides b and a divides c, then a divides (b-c) (This is Thm. 3.3 in the book).
5) Chapter 3, Exercises: 3.7) acd.
***
Due Wednesday October 18th: (Final official version)
1) Make sure you have read all of Chapter 2, and begin studying for the midterm.
2) Chapter 2, Exercises: 2.12 (Remember the rationals satisfy the order axioms, and you can use any theorems we proved), 2.14, 2.16acd, 2.18
***
Due Monday October 16th: (Final official version)
1) Finish reading chapter 2.
2) Chapter 2, Exercise: 2.6, 2.11ac (Prove these just using the axioms, don't cite any "order" theorems from the order part of the chapter and see definition of subtraction p. 78), 2.15ab, 2.17
3) Suppose (S, +, x) is a commutative ring (x is for "times"). Prove that if a is a zero divisor, then a has no multiplicative inverse. The easiest way to prove this is to do a "proof by contradiction." Proof by contradiction will be your third proof technique to have in your back pocket. First read the proof that 0 has no multiplicative inverse in the book. This is also a proof by contradiction in that you assume the opposite of what you want to prove, ie that 0 DOES have an inverse, and you reason using that assumption until you reach a contradiction. For this problem, also ASSUME a has a multiplicative inverse, and reason until you have a contradiction. How can you use the assumption that a is a zero divisor to do a proof similar to the proof that 0 has no inverse?
***
Due Friday October 13th: (Final official version)
1) Read up to "Well-ordering" on p. 83
2) Chapter 2, Exercise: 2.1, 2.2, 2.7 (For part (b), look for all pairs of ordered pairs (a, b) and (c, d) such that 1) neither pair is (0, 0) and 2) (a, b) times (c,d) equals (0, 0). We'll talk more about zero divisors on Wednesday)
3) Prove -(-a)=a for any a in S where (S, +) is an abelian group.
4) Let U be the set of elements in {0, 1, 2, ..., 9} which have multiplicative inverses under one's digit multiplication. What is U? Prove U with the operation of one's digit multiplication is an abelian group. (Crazy!)
***
Due Wednesday October 11th:
1) Keep reading chapter 2 (through p.79)
2) Chapter 1, Exercises: 1.30, 1.40, 1.41, Chapter 2, Exercise: 2.3
3) Prove (either directly or using the cancellation theorem we proved today) that if (S, +) is an abelian group, then the inverses are unique. In other words, show for every a in S, there is exactly one additive inverse -a. Hint: look over the proof we did to show the identity was unique. We will use this fact in class on Wednesday, so be sure to understand the problem and its solution.
4) Why is ({even, odd}, +, x) a field? You can explain why it satisfies A1, M1, A2, M2, but list out the idenities, and the additive and multiplicative inverses and show it is distributive.
***
Due Monday October 9th:
1) Read up to p. 75 (Office Hours anyone? 1:30-3:30 Sunday)
2) Chapter 1, Exercises: 1.15a (Show literally every single step), 1.20 (just the "If so, are there inverses?" part that you haven't done yet), 1.21cde (Now with the inverse question in e), 1.23b, 1.24def
3) Show (very formally) that (a # b) # c = a # (b # c) for all a, b, c in {0, 1, 2, 3, ..., 9} where # is one's digit arithmetic. In other words, write out using the definitions very carefully what each side is and then explain why the two sides are equal.
4) (Don't have to turn in) Make sure you can do 1.13 (but don't write it up). Also think about 1.32 (this question could be used to help do number 3 above).
***
Due Friday October 6th:
1) Finish reading all of Chapter 1 (Those practice problems in the reading are great.) Especially work on understanding parity sum and multiplication and ones digit arithmetic.
2) Chapter 1, Exercises: 1.17ac, 1.18, 1.20 (don't do the "If so, are there inverses?" part), 1.21abe (again without the inverses question in e), 1.24abc
***
Due Wednesday October 4th:
1) Read up to 1.4 (Yes you should really do the reading!)
2) Chapter 1, Exercises: 1.10, 1.11, 1.16, 1.23 a
3) Show that the function f from {Side sum 9 triangle game solutions} to {Side Sum 12 triangle game solutions} which takes T to its dual T' is one to one and onto. Thus there are exactly six Side Sum 12 triangle game solutions since there are exactly six Side Sum 9 solutions.
***
Due Monday October 2nd:
1) Read up to 1.3
2) Chapter 1 Exercises: 1.7, 1.8, 1.9, 1.12 (See page 35 for 1.12. We won't spend time on this in class, but it's straightforward.)
3) Let A={1, 2, 3} and B={b, c}. Give an example of a function f from A to B which is one to one OR explain why one cannot exist. Give an example of a function from A to B which is onto. Must all functions from A to B be onto? Explain your answer.
4) Find four functions f, g, h, j from N (the natural numbers) to N so that f is not one to one and not onto, g is not one to one but is onto, h is one to one but not onto, and j is one to one and onto. (For example, j(n)=n works, but you can't use this example). Thus, being one to one does not imply anything about being onto and vice versa.
***
Due Friday September 29th (All of the below plus this):
1) Read Chapter 0 through 1.1 (up to "Math Words")
2) Chapter 1 Exercises: 1.2, 1.4 (Talk about unions and intersections in tutorial.)
3) Chapter 0 Exercise 0.3
***
Due Friday September 29th (more will be added on Wednesday):
1) Read Chapter 0
2) Chapter 0 Exercises: 0.5, 0.8, 0.9
3) Argue why there are exactly six solutions to the triangle game with side sum 11 and that these solutions come from taking one solution and applying the symmetries of a triangle (Do an argument like we made for the side sum 9 solutions in class).
4) Suppose we defined the dual triangle T' to a given triangle T to be the triangle with value 7-x at each node where x was the corresponding value in T (See p. 21 in the book for examples). Show that if T is a solution to the triangle game then the dual triangle T' is too (remember to check all side sums are equal). If the side sum for T is 9, what is the side sum for the dual triangle T'? What if the side sum for T is 10? Finally, what is the "double dual" to a triangle, ie what is (T')'? Remember to explain why your answers are true.