:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Subject: HW #4 for Wednesday, 16Feb2000 To: (Number Theory Class) Hello NumberTheory Scholar-Apprentices As requested, I have moved the due-today to be due this coming Wednesday. Here is is: Please, on P.56, do the following. I suggest that you work on the Drill problems *before* doing the Hand-In problems. Dr: 2,5,6,8,10. HI: 11, 17. Also E-7 and E-8. (Only hand-in these 4 problems) --Best Wishes, "Prof. Jonathan" :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Subject: Homework, due Monday, 21Feb2000 (Class prob. added) Hello NumberTheory Scholar-Apprentices Here is a bit of HW for Monday. P.56: 34. ________________ E-11: Given coprime positive integers A and B, show that for EACH positive integer n there exists integer k such that A + kB is coprime to n. Can you give me an efficient algorithm to compute such a k? ________________ In class I stated the following, letting =N= mean "cong.mod.N". E-12: Generalize Wilson's thm as sketched below, and give a complete proof. General Wilson's Thm: Given an odd integer N >= 3, let J(N) denote the number of pairs, plus/minus x, which are solns to x^2 =N= 1. Then the product Prod(Phi(N)) is =N= to WHAT? --Best Wishes, "Prof. Jonathan" :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Subject: Helpful and easy Date: Fri, 18 Feb 2000 16:54:04 -0500 (EST) Hi Folks I am going to ask you to do the following "drill" work, but DO NOT hand it in. It is OK to write a computer program for this. Please continue the easy computation that we started in class. With p ranging over the first 20 odd-primes, let H = H(p) := [p-1]/2. Compute r(p) := < H! >_p that is, the mod-p residue of Factorial(H); write this residue as a value in [-H .. H]. Verify that, for p a "plus prime" (cong.mod4 to +1) that r(p) squared is =p= -1 . IN CONTRAST, verify that for p a "neg prime" (p =4= -1), that r(p) is either +1 or -1, and is thus a square root of 1, not of -1. Sincerely, -J.King :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Subject: Reading, over Spring Work-week Date: Fri, 3 Mar 2000 17:01:48 -0500 (EST) Hello NumberTheory Scholar-Apprentices Please read and think deeply over the following three topics: A: 2.3(CRT), 2.4, (skip 2.5), 2.6. We will indeed do 2.7 - 2.9, and now might be a good time to read them (optional). In any case, over the Work-week, please read B: 2.10 & 2.11 (Algebraic viewpoint). C: 3.1 (in particular, thm 3.2), 3.2 (Understand the STATEMENT of Quadratic Reciprocity, thm3.4, and skip the proof.) Read 3.2 and the definition of the Jacobi Symbol (defn 3.4 and thm 3.6). Compute the Jacobi Symbol for problem P.147#1. Cheers, Jonathan :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Subject: Comments on HW which is due Monday. Date: Fri, 17 Mar 2000 14:17:26 -0500 (EST) Hello NumberTheory Scholars HW problem P2 is mis-stated at the very end. It should be "...prove that \phi is a surjective ring-homomorphism". For the Coconuts problem, also due Monday, see if you can also give a solution, for a general N, where the pile is "divisible by five except that one is left over" N times, and the result is divisible by 5. Hint: Remember the "make it so" philosophy --you are not trapped by the problem statement. Rather than assume that after N applications, the pile is divisible by 5, why not instead assume that it has one more coconut than a multiple of 5. That is, why not simply assume that the operator can be applied [N+1] times, always staying within the integers? Notice this is slightly simpler than the original problem. Now rename N+1 to N. Notice that phrased this way, induction arguments are possible. Once you can solve this easier problem, no doubt you can analyze the original conundrum. Best Wishes, -Jonathan :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Subject: Reading for Monday. Date: Fri, 24 Mar 2000 17:01:04 -0500 (EST) Hello NumberTheory Scholars Please read and grok "Techniques of Numerical Calc", 2.4. In particular, please learn the clever Pollard rho method. It is for finding, probabilistically, prime factors of known-composite numbers. I do plan to program the Pollard method up, and you will be able to read the code. However, because I am eager to get to "The Jewel", the Quadratic Reciprocity thm, I will leave Pollard to you. ================ You may skip 2.5. ================ For Monday: Please read 2.6. I started Hensel's lemma today (not by that name) and -in the best of all worlds- would like you to know its proof by Monday. Examples 11 and 12 on P.88 are instructive. ================================================================ Reading Ahead: Naturally, 2.7 and 2.8. The beginning part of 2.8 is particularly important. --Best Wishes, "Prof. Jonathan" :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::