The course grades are:
A+ ... 3
A ... 4
A- ... 3
B+ ... 2
B ... 4
B- ... 3
C+ ... 4
C ... 7
C- ... 2
D ... 1
I hope you have a restful break and a good year in 2008.
Bruce Reznick
The final will be in our usual room on Monday evening at 7pm. One of the best students in the class has offered to be "extra help" for any study groups in preparing for the exam. If you are a group or an individual who would like to work with him, please let me know and I'll put you in touch.
The second test will be in class on Wed. 12/5. It will cover, in
general, the material since the last test, so that would be HW 6
through 10, although you well might need to use modular arithmetic
or the Chinese Remainder Theorem. To answer specific questions,
you will not need to use the theoretical results which were
instrumental in proving quadratic reciprocity and the existence of
primitive roots, although they are good mathematics and may well show
up in other courses. I refer specifically to Lemmas 4.7 and 4.10,
Theorem 5.7 and Proposition 5.8. I don't remember homework questions
on these.
You should know that (a/p) = a^( (p-1)/2 ) mod p, the formulas for (-1/p)
and (2/p) and the order of a^k mod m, given the order of a mod m, and
of course the sort of things that showed up on the homework.
>
Here are the Homework 10 Solutions and comments
Homework 10 questions In class Friday, a question was asked for a hint on #10. I'd say that you should just look at the equation mod 3 and mod 4. I did 6.4 through 6.8 in class, and this is supplemental to the material we're covering. It will not be on an exam.
Homework Ten, due W 11/28. The last homework of the semester.
This always happens this time of year; I slip up on postings, except for the homeworks itself. Here are two blocks of scanned sets of notes: Homework Solutions 6,7,8,9 and Extra HW comments and extra notes. This should catch us up through Break.
Homework 9 questions A student writes: On question 4 where it asks to find the number of solutions of the congruence x^3 = x^2 mod 50, we know we can find the number of solutions by looking at ax^t = b mod p, however when we subtract x^2 to the other side, we end up with b = 0. We aren't sure exactly what to do with the hint of factoring to x^2(x-1). Can you provide one more nudge in the right direction? Thanks.
My reply: The best nudge I can provide is the hint that you could have done this problem before Chapter 5. Step back and look at it directly. The Chinese Remainder Theorem is always useful. And the number of solutions means the number of incongruent solutions.
Out of order: Homework Nine, due F 11/9
Email sent to everyone in the class: I just received an unusual request from someone who works in a group that does their homework together: " ... I understand we haven't been asking questions in class, but after taking a serious look at the homework we have developed some more specific questions. We were hoping we could spend some time on Friday reviewing this material. We also feel like we could get a lot more done if given the weekend to work on the assignment after we have asked some of these questions in class. If that doesn't work, we're still more concerned about our comprehension than about our homework scores. I suppose this is just a heads up that we'd like to review on Friday and a request for an extension to Monday. Thanks for your time." Accordingly, I will delay Homework 8's due date until Monday. I will look forward to answering lots of questions in class tomorrow! Homework 9 will still be due on Fri. Nov. 9, however. Out of order: Homework Eight, now due M 11/5 (see above)
Homework 7 questions
A student writes: I am struggling on homework 7 with the quadratic
equations. For #1 (strayer 10-d) and #5, I have used the process from
Wednesday's class but have reached a point where I don't know what to do next.
For #1, I get to a congruent to u^2 mod m. [a,m redacted]. Since
these numbers are not perfect squares (unless I have made some
errors), how do I go about finding u? Any suggestions would be helpful.
My reply: Here, you just have to look at squares mod p to find the
square root. For example,
if u^2 = 12 mod 13, you take successive squares: 1, 4, 9, 16, 25, etc mod 13 and
then reduce: 1, 4, 9, 3, 12, until you see that 5^2 = 12 mod 13, and
you also know
that (-5) = 8 mod 13 has the same property (8^2 = 64 = 12 mod 13.) Or, you could
look at the numbers that are 12 mod 13 and wait until you see a
square: 12, 25, 38,
51, 64,
Out of order: Homework Seven, due F 10/26.
Out of order: Homework Six, due M 10/22. Test 1 will be in class on Monday, October 15. It will cover the material from the first 5 homeworks.
W 10/10, F 10/12 -- Some review, some new material. The test will be based on the first five homeworks. This includes some stuff not in the book, but only on handouts. Specific items mentioned include the definition of nu_p(n) and De Polignac's formula. We are in the middle of Chapter 4 in quadratic reciprocity, and the next topic, on W 10/17, will be the proof of Gauss' Lemma, the calculation of (2/p) and reciprocity itself. Once this is proved, there will be lots of examples. The next homework will be due F 10/19 and will be passed on on Monday. It will also be on the web then. Here is Homework Five Retrospective, the only handout for the week.
M 10/8 -- Not too many questions. We started on quadratic reciprocity, which will not be on the first test. Here is the Homework Block, consisting of handwritten solutions to HW 2,3,4,5 and additional comments on HW 2,3,4. And here is the Notes Block, consisting of handouts since the middle of September. I think that everything distributed in class should now be on this page. Let me know if I've missed anything. I'll try not to fall so far behind again.
Catchup: W 9/26, F9/28, M 10/1, W 10/3, F 10/5. Until the exam, all new material presented will be secondary to answering questions on the upcoming test. I will be bringing all handwritten handouts to class, in case you're missing one.
Questions on hw 5.
I'm asking for you
to find 10 different numbers n with the property that gcd(a,n) = 1
implies a^4 = 1 mod
n. One such n would be 5, by Fermat's Theorem.
On #7:
Free tip on problem 5, where the numbers might not be relatively prime
to the base in the congruence problem: When you spend too much time
with a hammer, everything looks like a nail.
There are lots of ways to get information about congruences *without*
using Euler's Theorem or Fermat's Theorem. Just look at the numbers
directly.
A student writes, on HW5: I had a question about problem 47 in the
book. I'm not sure where to
start. I began by multiplying the quantity sigma(n)/n in terms of
its
prime factors to see if there was a pattern that I could identify as
leading to 1/d, but no luck so far. Am I on the right track? Can you
offer a hint? Thanks.
My reply: You could get there that way, by writing n = p1^a1...pr^ar
and looking at
sigma(n)/n in terms of this product, or you could do something like
looking at sigma(12)/12 carefully and you might find a pattern. The
idea
here isn't very complicated, and I don't want to give it away!
Out of order: Homework
Five, due F 10/5:
A student asks: I was just wondering what suggestions you have for
question #6 in HW4. I thought I could possibly set it up similarly to
problem #4 in HW3 which gave us the last two digits.
My reply: what's being looked for is a solution for x = 783^{783} mod 100 where 0
\le x \le 99. This is similar to several problems on HW 3.
A student asks: I am looking for some insight on homework 4, problem
#5. With Fermat's, I see how 3^352 ties in with 353, yet I am
confused by the problem when I see 3^350.
My reply: What is the relationship between 3^350 and 3^352?
M 9/24 -- More on the Euler phi function. We talked about solving phi(n) = 6, 8 and 10, and covered material from sections 3.1 and 3.2. There was a handout based on the parts of Friday's class that weren't in the book. The homework out on Friday (#5, due Oct. 5) will be the last one on which the first exam is based. No date for the test has been set.
W 9/19, F 9/21 -- We essentially finished chapter two, went over many examples in class and some additional material, which will be covered in a handout on M 9/24. The second homework was returned on W, along with some additional comments, and the third homework was collected on Friday, along with solutions. When I get a chance, I will scan the hand-written material; here is the nicely-typed Homework Four, due F 9/28:
HW3 questions
A student asks: for number 4 it doesn't specify a method, so I assume
we can find the
integers by any method? same question for number 5
My reply: In general, any correct method is acceptable, some are easier.
A student asks: Fermat's Little Theorem can only be used on natural
> numbers so n should be natural numbers as opposed to integers right?
My reply: In Fermat's little theorem, gcd(a,p) = 1, but a does not have to be a
positive integer. However, if a = -b and b > 0, since a prime p > 2 is odd,
a^(p-1) = (-b)^(p-1) = (-1)^(p-1)* a^(p-1), and p-1 is even so (-1)^(p-1) =
1, and it doesn't matter.
A student asks: I have been working on the Math 453 homework. Number
7 says not to use
induction. I feel that number 2 (Strayer 57b) is similar to this problem
#7, and for #2 I had initially thought of using induction. So my question
is: should induction be avoided in both problems?
My reply: Maybe I should be more careful as I say this. Both problems
are more easily
dealt with without induction, but by using the material in section 2.5. I
suspect some people will try to prove by induction anyway, but it's more
work, and in a sense, less insightful. The method I have in mind would work
with polynomials of very large degree to which you would not want to apply
induction.
An alert student observes that in HW3, problem 4, the answer depends
on whether n is positive or not; I intended n > 0, but if you do it
both ways, that's ok too. (The point is that -44 for example, ends in
44, but is actually congruent to -56 mod 100.)
A student asks:
I have a question about problem #2 on the homework, which comes from
section 2.5 in the book, number 51 (b), (d). I am confused about how
to setup/start the problem. A hint is given to use Fermat's little
theorem and example 11. The problem gives n and m, but I am not sure
how these are supposed to be arranged to look like example 11 does.
My reply: Let me do a small variation of 51 a. Suppose n = 32^67 and m
= 13. Fermat's
Little Theorem says that a^12 = 1 mod 13 if gcd(a,13) = 1.
(i) 32 = 6 mod 13 (32 = 2*13 + 6), so the first simplification is that
32^67 = 6^67 mod 13
(ii) 67 = 12*5 + 7, so 6^(67) = (6^12)^5 * 6^7 = 1^5 * 6^7 = 6^7 mod 13.
(iii) Now you just take them one at a time 6^2 = 36 = 10 mod 13, so 6^3 =
6*36 = 6*10 = 60 = 8 mod 13, 6^4 = 6 * 6^3 = 6 * 8 = 48 = 9 mod 13. You can
keep going, or you can see that 6^7 = 6^4 * 6^3 = 9 * 8 = 72 = 7 mod 13, by
the previous calculations.
M 9/17 -- HW 2 came back from the grader and will be available in class on Wednesday. We talked about congruences, reviewed Wilson's Theorem, and then Fermat's Little Theorem and Euler's Theorem. Many applications on Wednesday.
F 9/14 -- I distributed Homework Three, due F 9/21. I also distributed as yet unlinked solutions to Homework Two, and a set of bonus notes on inverses mod p. We talked a little bit about the Chinese Remainder Theorem and zipped through Wilson's Theorem.
A student writes: what do you mean by "square" and "cube" in problem
6
My reply: an integer is a square if it can be written in the form n^2
for some integer n; it is a cube if it can be written in the form n^3.
W 9/12 -- Homework 1 returned, with Additional Comments. Lots of the Chinese Remainder Theorem, with many worked problems. Homework 2 is due on Friday.
M 9/10 -- The phone and email list (unlinked) was distributed. We finished discussion of ax = b mod m, with more examples. We looked at the equations a = b mod m and a = b mod n when m divides n and we started to do the Chinese Remainder Theorem. Bring questions to class! Useful links include MathWorld as an online math encyclopedia and MacTutor as a resource for the history of mathematics.
F 9/7 -- I distributed Homework Two, due F 9/14. The first homework will be returned after I get it from the grader. The mathematics covered was the solution to the recurrence ax = b mod m, following and amplifying section 2.2 of the book. There will be more of this on Monday.
W 9/5 -- HW 1 collected and Homework One Solutions distributed. About half the class was a review of the assignment, and then we moved on to Ch. 2 on congruences. The email/phone voluntary sign-up list was distributed. I'll pass it around again on Friday and then distribute it on Monday.
Questions on homework 1
A student writes: I am completely lost on how to do problem 3 (strayer
71) in homework 1.
My reply: Three comments:
(i) Problem 3 is #70 in Streyer, not #71
(ii) The key to this problem is to take a prime p and look at v_p of the
various objects in the problem. We had a key result that a | b if and only
if, for all p, v_p(a) is less than or equal to v_p(b). This will be useful.
(iii) Proving a mathematical statement requires a proof. Disproving a
mathematical statement can be achieved with a single counterexample. To say
that the theorem "P ==> Q" is false, it is enough to find a case in which P is
satisfied but Q is not. You do not have to try to prove that "P ==> not Q",
unless you are asked.
A student writes: I have a general question about proofs that would
help those of us "from
north of Green Street" (among others) that may not have taken MATH347.
...how can we just operate on this assumption 5|n^5-n without proving
it separately? I think it has something to do with the somewhat
recursive nature of the proof by induction, but I simply cannot wrap my head
around it. Any help would be sincerely appreciated. I think you said you will
post the reply on the web or wait for class to give a verbal explanation. In
my opinion, a more thorough explanation could be delivered in less time
using a blackboard (pictures, arrows, etc...).
My reply: OK, here's the way induction works, and I will not make any
specific
reference to any specific problem. With induction you need two things:
(i) A base case, eg for n = 0 (step on the ladder)
(ii) A mechanism for going from "it is true for n" to "it is true for
n+1". Note, the whole point of induction is that you don't have to
prove
it for n, just be able to (climb up one rung)
So what happens is this. You know it is true for n=0 by (i), and so by
(ii), it is true for n = 0+1 = 1. But now you can feed this back into
(ii): it is true for n = 1, so it is true for n = 1+1 = 2, and so on.
From the mathematician's point of view: it's true for all n, because
if it
weren't, there'd be a smallest value of n for which it is false, but
that
smallest value isn't n=0, by (i), and if the smallest value is n and n
>0, then it has to be true for n-1 (smaller than n). But this
contradicts
(ii), because if it is true for n-1, then it is true for n-1+1 = n.
From the engineer's point of view: it's true for n=0 by (i), and (ii)
sets up an infinite loop, so it's true in turn for n=1,2,3,4,..., and so
for all n.
I get a strong feeling there are a lot of
unasked questions in this class, and it's my job to answer them,
whether you want to ask them or not!
F 8/31 -- We mostly finished chapter 1. I spent more time on v_p(n) including a Handout on v_p(n) and v_p(n!). Homework 1 is due when we get back on Wednesday 9/5 and Homework 2 will be assigned on Friday 9/7.
W 8/29 -- The Fundamental Theorem of Arithmetic; namely, unique
factorization of integers > 1 into primes. We're in the middle of
section 1.5. I distributed
Homework
One, due W 9/5. I also gave
a
Handout on the Euclidean Algorithm, as applied to 2007 and 453 ,
and a copy of the frontpage of this
website: The Prime Pages.
Today's new notation was v_p(n), for a prime p and integer n. It
denotes the exact power of p which divides n. For example, 24 =
2^3*3^1, so v_2(24) = 3, v_3(24) = 1, v_5(24) = v_7(24) = ... = 0.
Another notation for v_p(n) = a is that p^a || n.
I've changed my mind about the second homework. It
will be assigned on F 9/7 and due on F 9/14. See, it pays to read the
webpage in advance of class.
M 8/27 -- Greatest common divisors. Some notation that's not in the book: For an integer m, mZ = {mn: n in Z} is the set of multiples of m. E.g. 2Z = (-2)Z = {...,-4,-2,0,2,4,...}. For an integer m, D(m) is the set of positive divisors of m; e.g. D(12) = {1,2,3,4,6,12}. I will write gcd(a,b) where the book writes (a,b), and similarly for the gcd of more than two. The first homework will be distributed on Wednesday and will be due W 9/5. The second homework will be on the web on Labor Day and will be due M 9/10.
F 8/24 -- We covered the second section of the book, on prime numbers. There were many historical asides not covered in the text, and not easy to reproduce here. However, solving the Prime Number Theorem appears to lead to a very long life. One handout: How to Solve It guide. The first homework assignment will be distributed on Monday.
W 8/22 -- First day of class. Introduction to the integers and divisibility. Notation not in the book: for the greatest integer function, instead of [x], we only use the lower half of the brackets. And the fractional part of x, {x}, is defined to be x - [x] and always lies in the interval [0,1). Examples: [4.53] = 4, [7] = 7, [-4.53] = -5, {4.53} = .53, {7} = 0, {-4.53} = (-4.53) - (-5) = .47. Handout: Course Organization