> For the cusp form associated to an elliptic curve, what is the > coefficient of q? Good question -- It is 1. > in question 5, I've got every case but n a power of 2. should we develop > the argument on parametrization of pythagorean triples to deal with this > case? Oops. I meant to assume the exponent is odd... The case when n is a power of 2 is more complicated, and boils down to proving Fermat's Last Theorem for exponent 4, i.e., showing that x^4 + y^4 = z^4 has no nontrivial solutions. I think Fermat first proved this by his "method of infinite descent". Feel free to assume FLT for n=4.
Jayce, I thought about the rank question you asked in class, which is quite interesting, and came up with the following answer. Theorem: Let a be an integer and let E(a) be the elliptic curve defined by y^2 = x^3 + ax + 1. Then E(a) has positive rank if and only if a =/= 0,-2. Proof. First we observe using "descent" (implemented in MAGMA via the Rank command) that if a=0 or -2 then E(a) has rank 0. More precisely, when a=0, E(a)(Q) = Z/3 and when a=-2, E(a)(Q)=Z/4. Suppose for the rest of the proof that a =/= 0,-2. We will now show that the point P=[0,1] in E(a)(Q) has infinite order. If f(x) = x^3+ax+1 is reducible, then it has a rational root. Any rational root is an algebraic integer hence a usual integer. If f(x) = g(x)*(x-r) with g monic with integer coefficients and r an integer, then r = 1 or -1, since the constant coefficient of f is 1. If r=1 is a root, then a=-2, and if r=-1 is a root, then a=0. Thus since a=/=0,-2, we see that f(x) is irreducible. Any point of order 2 in E(a)(Q) has x-coordinate a root of f(x), so there are no elements of order 2 in E(a)(Q). For any choice of a there is a well-defined homomorphism E(a)(Q) --------------> E(a)(Z/13). The homomorphism sends a point (x:y:z) to its reduction modulo 13. This works for any a since x^3+ax+1 has distinct roots modulo 13 for any a (just check for a=0,..,12). The following table lists the order of the image of P=(0,1) in E(a)(Z/13) for each choice of a. a order of P mod 13 ---------------- 0 3 1 6 2 8 3 6 4 19 5 8 6 8 7 4 8 4 9 6 10 19 11 4 12 19 ---------------- If P is a torsion point, then the order of P mod 13 is a DIVISOR of the order of P, since it is the order of the image of P under a group homomorphism. In fact, it is a nontrivial theorem (proved using "formal groups") that the order of P mod 13 must equal the order of P -- we will only use this in case a = 0 (mod 13). Since E(a)(Q) has no elements of order 2, we immediately rule out the possibility that a = 1,2,3,5,6,7,8,9,11 (mod 13). The theorem of Mazur that I stated in class implies that E(a)(Q) has no elements of order 19, so we also rule out a = 4,10,12 (mod 13). The only remaining possibility is a=0 (mod 13) and P is a 3-torsion point. We now show directly that if P=(0,1) is a 3-torsion point, then a=0. If 3P = 0, then P + 2P = 0, so 2P = inverse of P = (0,-1). On the other hand, using the formula for 2P from the lecture notes, we see that 2P = (a^2/4, (-(a^2/4)-2)/2). Setting this equal to (0,-1), we see that a=0, as claimed. Thus our assumption that P has finite order is false, so P has infinite order and E(a)(Q) thus has positive rank. -- William
> I'm having some trouble with 2b. I don't understand what Invariants > returns and I couldn't find a good explanation in the documentation. I'm > guessing if I knew what it returned I would be able to see how it applies > to the problem, so can you give me a quick explanation? If G is a finite abelian group, then the fundamental theorem of abelian groups asserts that G can be written as a product of cyclic groups of orders d1,...,dr where d1 | d2 | ... | dr. The command "Invariants(G)" returns the integers d1, ..., dr. Thus G is isomorphic to Z/d1 x ... x Z/dr, where d1,...,dr are the invariants of G.
> When we're finding the principle divisor associated with (x+1)/(y-1), is > the order of (x+1) at (1,0) just the multiplicity of the intersection of > the elliptic curve with the line x=1? Similarly for y? Can we say that in > our proof, if it's true? Yes this is true, and you can just say that in your proof. > Also, I'm having trouble with 4a. I've gotten to showing that, if > f(x)+yg(x)= (r(x)+ys(x))/d(x), then d(x) divides (r(x)+y(s(x)))^k, where k > is a integral power determined by the polynomial for f(x)+yg(x). I don't > know where to go from here. I don't know how you're approaching the problem or how you've encountered a k. Since it is getting late, and this problem is harder than I thought, I'll sketch an extended hint. Feel free to fill this out as your solution. Suppose a = f(x) + yg(x) is an element of C(x)[y]/(y^2-x^3-ax-b) that is integral over C[x][y]/(y^2-x^3-ax-b). Then there is a monic polynomial F(T)=T^2+alpha*T+beta in C[x][T] such that F(a) = 0. Writing this condition out, using that y^2 = x^3+ax+b, and equating coefficients, shows that 2*f*g+alpha*g = 0 and (x^3+ax+b)*g^2 + alpha*f + beta + f^2 = 0. From the first equation, either 2*f+alpha = 0 or g = 0. We consider each case. If g = 0, then a = f(x) and alpha*f + beta + f^2 = 0. Thus f*(alpha+f) = -beta is a polynomial. If f had a pole, then since alpha is a polynomial, alpha + f would also have that pole, so f*(alpha+f) would as well, a contradiction. If g =/= 0, then 2*f + alpha = 0, so f=-1/2*alpha is a polynomial. Also, from the second equation above, (x^3+ax+b)g^2 is a polynomial. Thus the only possible poles of g^2 are the zeros of x^3+ax+b. But by assumption x^3+ax+b has distinct roots, so g^2 can't have any poles, since they all occur with multiplicity at least 2. Done. Notice that the last part of the above proof would fail if a=b=0, which is good because the result is false then.- Question/Answer:
> How do you induce a point onto an elliptic curve that's in an extension of > Q? I tried to change bases to QuadraticField(3), but I can't induce a > point E![1,Sqrt(3)]. When you write "Sqrt(3)" MAGMA has no idea you want one of the two square roots in QuadraticField(3). There are dozens of interpretations of Sqrt(3), and it chooses one, i.e., a floating point number. Here's an example of how to do it right: > K:= QuadraticField(3); > a := K.1; > a^2; 3 > E := EllipticCurve([K|0,3]); > P := E![0,a]; > P; (0 : a : 1) > E; Elliptic Curve defined by y^2 = x^3 + 3 over K > P + P; (0 : -a : 1) > 3*P; (0 : 1 : 0)- Question/Answer:
On Saturday 09 November 2002 08:44 pm, you wrote: > If you have a lattice in C, and draw a circle centered at the origin, I > know it's true that you can find a constants k, m, depending on the > lattice, such that the number of lattice points contained in a circle of > area A is >kA andlattice, or at least the lattice of Gaussian integers? I'm trying to use > this fact to do 2b on the last problem set. I don't really know anything systematic about this, but here's an argument that I just made up that gives an m for the Gaussian integers: The problem is to find upper and lower bounds on the number of integer points in the disc of radius r. The area of this disc is A = pi*r^2. An upper bound on the number of integer points in the disc of radius r is the number of integer points in the square "of radius r". For simplicity, assume r is an integer; then there are (2*r+1)^2 = 4r^2 + 4*r + 1 points, which is a little too big. If we don't count the points on the boundary of the square, we get (2r+1)^2 - 2*(2*r+1)-2*(2*r-1) = 4*r^2 - 4*r + 1. Since the circle of radius r contains only 4 points on the boundary of the square of radius r, we see that for r>=3, (# points in disc of radius r) <= 4*r^2 - 4*r + 5 <= 5*r^2 Thus you can take m = 5/pi, in your notation. It's trivial to find a lower bound k, i.e., k=0, so you must have forgotten to say what property you want k to have. William - Question/Answer:
This is a bug report I just sent to MAGMA: Hi, I'm trying to use the binary quadratic forms package in MAGMA for my number theory course. It has some serious problems! Here are some IsEquivalent's documentation says: True if the quadratic forms f and g reduce to the same form and false otherwise. If true and the discriminant is negative, then the transformation matrix is also returned. An error is returned if the forms are not of the same discriminant. However, here is an example where IsEquivalent totally lies: > Q := QuadraticForms(23*4); > f := Q![-23,0,1]; f; <-23,0,1> > Discriminant(f); 92 > g := Q![-1,0,23]; > IsEquivalent(f,g); true > Reduction(f); <1,8,-7> > Reduction(g); <-1,8,7> > IsEquivalent(f,g); true The two forms f and g are definitely *NOT* equivalent by any 2x2 integer change of basis with det = +/- 1, yet IsEquivalent says they are. Also, IsEquivalent won't return a change of basis matrix when d is positive. Why not? Also, > #ClassGroup(Q); 1 This is incorrect, since the class group should have order 2. (The class group of the corresponding number field has number 1, and the strict or narrow class group of that number field has class number 2.) I don't like this paragraph at all, from the introduction to quadratic forms in the handbook: The structures of quadratic forms of a given discriminant D correspond to ordered bases of ideals in an order in a quadratic number field, defined up to scaling by the rationals. A form is primitive if the coefficients a, b, and c are coprime. For negative discriminants the primitive reduced forms in this structure are in bijection with the class group of projective or invertible ideals. For positive discriminants, the reduced orbits of forms are used for this purpose. .... I think the first sentence is false; isn't it necessary to pass to equivalences classes of quadratic forms and strict equivalence classes of ideals before obtaining a bijection? (Even then, there's no bijection when the discriminant is negative, unless we restrict to positive definite forms.) The sentence "For negative discriminants the primitive reduced forms in this structure are in bijection with the class group of projective or invertible ideals." contains two mistakes. First, one must restrict to either positive definite or negative definite forms; second, it should say either "the SET of primitive reduced forms" or "with the ELEMENTS of the class group". I have no idea what the next sentence, "For positive discriminants, the reduced orbits of forms are used for this purpose." means? It just seems very vague.- Question/Answer:
On Friday 08 November 2002 03:50 am, you wrote: > I'm having some trouble using MAGMA for 6c. First comment: You could definitely do this problem without using a computer, if you assume the unproved propositions I stated on Wednesday. It's not difficult to compute the correspondence between quadratic forms and ideals by hand. > in Pic(O). The problem is that I can't represent an Ideal in MAGMA. > I've been looking at the Ideal functions, and the only constructor that > seems to make any sense is > > ideal< O | a_1, a_2, ... , a_m > : RngOrd, RngElt, ..., RngElt -> > RngOrdFracIdl > > But I've been trying to figure out how to use it for a half hour now and > it won't quite work. Do you know how to use this functionality? Here's an example: > K := QuadraticField(-23); > CharacteristicPolynomial(a); x^2 + 23 > O := MaximalOrder(K); > I := 7*O + a*O; > I; Principal Ideal of O Generator: 1 > I := 4*O + (3+3*a)*O; > I; Ideal of O Two element generators: 4 6*$.2 > I := ideal; > I; Ideal of O Two element generators: 4 6*$.2 I should have done some of these in class before your assignment was due. I will try to fit some examples in today, since I'll probably ask similar questions on the take-home final. - Question/Answer:
> What does it mean when MAGMA has a dollar sign in its return? For > > example: > > Q := BinaryQuadraticForms(-23); > > x := ReducedForms(Q); > > Ideal(Q!x[1]); > > Ideal > Two element generators: > 1 > 4*$.2 - 3 It wants to write the second generator of the ideal in terms of something (e.g., sqrt(d)), but you've never told it what to call that something. So it calls it "$.2", which means the second generator. But don't worry, you can name the generator. Watch: > O := Order(I); > I; Ideal of O Two element generators: 1 4*a - 3 Of course, this is of no use if you don't know what a is! Fortunately, > O; Maximal Order of Quadratic Field with defining polynomial $.1^2 + 23 over the Rational Field This means that a satisfies a^2 + 23, i.e., a is sqrt(-23).- Question/Answer:
On Tuesday 29 October 2002 07:38 pm, you wrote: > Do we have to use MAGMA to compute this continued fraction? No. You only have to use MAGMA if I explicitly ask you to.- Question/Answer:
> is the problem correct that asks to show > > |\alpha - p_k/q_k| < q_k^2 > > for all k > 0? It's correct, but like you say, it's not terribly impressive. > Seems like that's not a particularly impressive result. Maybe 1/q_k^2? You're right, I meant 1/q_k^2, which is what is needed for solving the second part of the problem. Thanks!- Question/Answer:
> I'm a little confused about part 4 of number 4. Are +-sqrt(41) rational > numbers? If so, how do we go about finding the other two rational square > roots? sqrt(41) is irrational: 6.403124237432848686488217674 (Or use the same proof that sqrt(2) is irrational.) Suppose x^2 = 41 (mod 100). Could you find all x with 0<=x<=99 with that property?- Question/Answer:
On Tuesday 22 October 2002 11:37 pm, you wrote: > I'm coding up a function to find the coefficient of q^289. First I tried > seeing how sweet MAGMA really is by just doing a brute force construction > of the polynomial--it ran out of memory after about 65 iterations (we need > 288 or 289). So then I added a while loop inside my for loop that strips > off leading coefficients times x to the power Degree(f) while Degree(f) is > greater than 289. Now the problem is speed. I started running it a few > minutes ago, and I'm at the 60th iteration. I feel like it will end in a > reasonable amount of time (an hour or so) because the higher iterations > should take roughly the same amount of time since they have roughly the > same number of terms and we strip off roughly the same number of terms > greater than degree 289. but this seems a little too computationally > expensive. What does the "Use the &+[ ] construction." hint in the VOH > mean? Maybe it will make things faster? Should the computation of the > coefficient take nearly this much time? No, since I can do it with MAGMA in less than a second. You would probably see a significant speed up if you use the "sweet" built-in MAGMA feature that does what your inner loop is doing. Watch: > R:= PowerSeriesRing(RationalField()); > f := 1-q + O(q^10); // Note the BIG OH. > time f^389; 1 - 389*q + 75466*q^2 - 9735114*q^3 + 939438501*q^4 - 72336764577*q^5 + 4629552932928*q^6 - 253302681901632*q^7 + 12095203060802928*q^8 - 512030262907323952*q^9 + O(q^10) Time: 0.000 If this isn't enough of a hint, let me know. > expensive. What does the "Use the &+[ ] construction." hint in the VOH > mean? I should have written &*, probably. Here's an illustrative example: > &*[n : n in [1..10]]; 3628800 Given a sequence, if you stick "&*" in front, MAGMA multiplies the elements of the sequence together. It can be faster than using a for loop, because MAGMA has lots of built in optimized algorithms implemented in C for multiplying together elements of a sequence.- Question/Answer:
> > > I can't find commands for forming infinite products or > > > evaluating their coefficients. > > > > You can (and should) do the problem using only finite products and > > polynomials. > I don't know how to do finite products either. You could: (1) Use a for loop. (2) Use the &*[ ] construction. Example: > a := 1; > for n in [2..10] do > a := a*n; > end for; > a; 3628800 > The factorization command works, but it's only giving me precision up to > O(5^20). You can set the precision using the command R:=pAdicRing(5,35), say. Here's an example: > R := pAdicRing(5,35); > S:= PolynomialRing(R); > Factorization(x^2+1); [ , ] > Log(1086271514781596803014557)/Log(5); 34.38765360760558431062441197 - Question/Answer:
> Sorry to bother you again. On question 3, I wrote some MAGMA code that > basically attacks the question by brute force, i.e. it loops through all > integers, tests each for primality. If prime, it tests all possible > (x,y,z) ordered 3-tuples to see if any match the equation. Clearly this > is not the way to approach it, since I've been running my program for an > hour and it hasn't returned. So I interrupted it. I can't seem to find > anything in the documentation that would fit this problem any better > than the brute force method. Should I just scrap MAGMA for this problem > and prove it analytically? YES. It's a "trick question", in that it's easy to answer by pure thought without using a computer. Hint: Look for a prime power p^r where the equation doesn't have a solution mod p^r.- Question/Answer:
> When I try to type R'SeriesPrinting := true; in MAGMA, I get an error > message. Is there a typo in there? This is hard to answer if you don't include the error message. In any case, here's an actual MAGMA session: > R := pAdicRing(7); > R`SeriesPrinting := true; > R; 7-adic Ring- Question/Answer:
> I've been struggling with the MAGMA bits of the homework. I got the first > three eventually, but I have no idea how to do part (d) without leaving the > computer on all night checking integers from 1 to 5^30. Is there some > subtle thing about MAGMA I should know? Its roots programs require one to > be working in a field, so things are a bit iffy here. You should be able to do it almost instantly using pAdicField(5).- Question/Answer:
> On 4, we have to define 1/2 modulo 10 in order to compute 13/2, right? But > 1/2 modulo 10 doesn't exist, so I must be missing something. There's a trick. Suppose a = 1/2. Since v_{10}(a) = -1, you have a = d_{-1}*1/10 + d_0 + d_1*10 + d_2*10^2 + ... The goal is to find the d_i. Do this by multiplying both sides of the equation by 10: 5= a*10 = d_{-1} + d_0*10 + d_1*10^2 + d_2*10^3 + ... Now to find d_{-1} reduce both sides modulo 10, etc.- Question/Answer:
> Sorry to flood your index, but I've been reading through the "Adic > numbers" notes, and I think I understand it all, but I just don't see > how to compute the expansion of a fraction. In the notes, I see how you > got the expansion for 1! - 2! + 3! Etc., but they it jumps right to > saying "reducing 1/7 modulo larger and larger powers of 10, we see that > 1/7 = ...857142857143 in Q10". I really don't see where this is coming > from. I think it's because I don't understand what it means to reduce a > fraction modulo a power of 10. (I ask this with reference to question 4 > on the hw). 1/7 modulo 10 means the inverse of 7 modulo 10. In MAGMA, > Integers(10)!(1/7); 3 I hope this answers your question. When I talked about this process in Math 55, I mentioned that you have sum_{i>=0} d_i 10^i = 1/7 so to find d_0, just reduce both sides modulo 10. > Also, about question 4, we're supposed to compute the first 5 digits of > the 10-adic expansions of 13/2, 1/389, 17/19, and the 4 square roots of > 41. So we're computing 7 total expansions, right? Just wanted to be > clear on that. Yes.- Question/Answer:
> I've been all over the MAGMA documentation, but I can't find any way to > construct a simple finite group. I want to use the intrinsic function: > > IsCyclic(G): GrpFin -> BoolElt > > But I can't find any way to construct a GrpFin object. For example, how > would I construct the group of integers modulo 17 with addition? CyclicGroup(17); But for problem 2(b), you might want to use UnitGroup(ResidueClassRing(n)), since it asks whether (Z/n)^* is cyclic as opposed to (Z/n,+). Note that (Z/n,+) is ALWAYS cyclic. > Also, can we use MAGMA for question 3 (and all the other questions)? YES.- Question/Answer:
> Perhaps I'm missing something here, but on the very first problem we've > defined the Jacobi symbol where m is odd, and then in part (a) we're asked > to compute (7 | 5!), but 5! is not odd, which is odd. Is there something I > should know? It's a mistake. Please replace 5! by the odd part of 5!, i.e., the largest odd divisor of 5!, i.e., 15.- Question/Answer:
> For the second modulus on #5, you want us to use the polynomial-ring > algorithm, right? I keep on messing up somewhere...I can't seem to get > it to work. Yes, I want you to use the poly-ring algorithm. It might not work for your first choice of random z. I just tried it with z=5, which works. If you just can't find the square root, make up a square root and continue with the rest of the problem (the CRT part) instead of giving up.- Question/Answer:
> I'm working on number 3 on the midterm and I have a question on interpretation. Clearly > the question fixes p. Does it fix g and m? My interpretation is that it > doesn't fix either. Is this correct? No. Fix *all* of p, g, and m. Then, give the number of solutions as a function of p, g, and m. For fixed p, g, and m, how many solutions x are there?- Question/Answer:
> How do I find the roots of a polynomial using MAGMA? Here's an example: > R:= PolynomialRing(ComplexField()); > f := x^3 + x + 1; > Roots(f); [ <-0.68232780382801932736948373971104825686, 1>, <0.34116390191400966368474186985552412841 - 1.1615413999972519360879176872471740747*i, 1>, <0.34116390191400966368474186985552412841 + 1.1615413999972519360879176872471740747*i, 1> ] - Question/Answer:
> On the RSA lecture notes, page 4, it says: > > So we know both pq = n and p+q = n+1 - phi(n). Thus we know the > polynomial: > > X^2 - (p+q)x + pq = (x-p)(x-q). > > Now I understand how this polynomial can be solved for p and q, and I > understand how p+q = n+1 - phi(n). But I don't understand how you got > the polynomial. Where did the X come from? I'm not sure how to answer this. Try this: If we know a and b, then we can consider f = x^2 + a*x + b. That's all I am saying. The polynomial is introduced as a TOOL to help you find p and.q. You don't really really need it here, since I bet you can easily prove directly that if you know p+q and pq, then you can find p and q. You get a system of two equations: p + q = a p*q = b where you know a and b. Then you substitute around and arrive at p and q. In the homework problem that involves p, q, and r, you'll end up with three equations and it's more difficult to substitute. However, you can assume that finding roots of a polynomial is easy. (Using, e.g., Newton's method.)- Question/Answer:
> A few things I'm not quite sure I understand: > > 1) How does the quadratic formula work in Z/p? It doesn't really seem > like division is defined mod p, so how do you divide by 2a? Division is defined mod p. Given a in Z/p with a=/=0 there is a unique b in Z/p such that ab = 1. You can find b using the extended Euclidean algorithm by finding x and y such that ax + py = 1, and noting that b=x works. As long as p=/=2 (and it isn't) this works. > 2) Your square root algorithm where p is congruent to 1 mod 4. In the > example in the text (section 6.5), it says that (1 + 24x)^194 = -1. I'm > not sure what that means at all. I'm not quite sure how you raise a > polynomial to a power and get back an integer. Then it goes on to say > that the coefficient of x in the power is 0, so we try again. Also, it > then says (1+51x)^194 = 239x. Again, I'm not quite sure how this works. Do the exponentiation as you would with a polynomial, but whenever you see x^2 replace it by a. For example, if you're working modulo 389 and a = 69, (1+51x)^2 = (1+51x)*(1+51x) = 1 + 102x + 51^2*x^2 = 1 + 102*x + 51^2*69 = 141 + 102*x (all mod 389 and x^2 -69). To do this sort of thing efficiently, see the MAGMA log from class that day: http://modular.fas.harvard.edu/edu/Fall2002/124/mlogs/10-04-02.mlog > 3) Finally, for question 4 (finding a factorization algorithm for n = > pqr), do you want a deterministic or randomized algorithm? Deterministic. I don't know how hard that problem will be for you guys since I came up with it myself sort of working in reverse. Make sure you understand the algorithm for factoring n=pq given n and phi(n) from the RSA part of the lecture notes. You'll use a similar method, but one degree higher.- Question: Actually 2 questions about MAGMA: 1. Is there a way for us to compile MAGMA code into executable files? 2. (related to 1) Is there a way to write MAGMA code into a file and read it in to the interpreter (much like you would do with LISP or Python)? I find it easier to write short programs and read them in than to type commands one at a time into the interpreter.
Answer: The answer to 1 is "no".Regarding 2,
Yes. Method 1: Suppose your program is nikita.m. To run it type magma < nikita.m at a command line. Method 2: From within magma, type > load "nikita.m"; If the input file has lots of ">"'s at the beginning of the line, you have to delete them, or type the following into MAGMA: > SetIgnorePrompt(true); > Thanks a lot for hooking us up with the MECCAH accounts, I've been poking > around and looking at the log files, and it's extremely powerful. You're welcome. Let me know if you do anything interesting on MECCAH...- Question: I'm working on question 6 (numerical evidence for or against the assertion equivalent to the Riemann hypothesis). I wrote a C program which prints out values of the LHS and RHS of the inequality. It approximates Li(x) using left sums. I iterate 100,000 values of x (integers from 3 to 100,000), and I always get the LHS is (a lot) greater than the RHS. In fact, it's not even close. And when I check certain values on a calculator, my data is confirmed. Why is this happening, is it problems in my code?
Answer:
- I noticed that there is a minor typo in the definition of Li(x) in the notes. I wrote Li(x) = integral from 2 to x of 1/log(x) dx. I should write "integral from 2 to x of 1/log(t) dt." However, anyone who saw the integral would know what I meant, since the first version doesn't make sense, so I doubt this is your problem.
- Maybe you are using Log-base-10 instead of the natural logarithm. Pure mathematicians always write "log" to mean "natural logarithm", but applied mathematicians and CS people I guess don't do this. The statement is totally false if you use the wrong base for the logarithm.
MAGMA is amazingly pitiful at numerical integration, but here's a little MAGMA script that verifies the inequality for x = 4.
> f := mapRealField() | x :-> 1/Log(x)>; > Integral(f, 2,7); 3.711887985880113284447801559 > function Pi(x) return #[p : p in [2..Floor(x)] | IsPrime(p)]; end function; > Pi(4); 2 > Integral(f,2,4); 1.922421314921558093166159998 > Abs(Pi(4) - Integral(f,2,4)); 0.077578685078441906833840001990057459599 > Sqrt(4)*Log(4); 2.772588722239781237668928485 - Question: I'm still not sure I understand this definition. 18, 12 are in Z/20, and their gcd over the integers is 6. However, gcd(18,gcd(12,20))=2. Why is this a natural definition? Is the point that the new definition forces every element of the residue class to be divisible by the gcd?
Answer:Yes, exactly. The residue class of 12 contains 12, 32, 44, etc. The residue class of 18 contains -2, 38, 58, etc. The gcd of all the elements in all these residue classes is 2.- Question: On p. 5, are we proving that the given definition of the gcd doesn't depend on a~,b~ when the gcd is viewed modulo n?
Answer: Yes, now that we've chosen that convention.- Question: My question regards 6b on the homework. Unless I'm considering a different "natural map" Z/mn => Z/m \times Z/n, I don't think that the natural map is injective unless m and n are relatively prime. What do you think?
Answer: Good question. When you prove that phi is multiplicative, you will be in the situation where n and m are coprime. Multiplicative means, by definition, that if gcd(m,n) = 1, then phi(mn)=phi(m)phi(n). When gcd(m,n)=/=1, multiplicativity can fail. Feel free to comment on all this in your solution.- Question: On question 2, it says to find integers x,y such that 123x + 567y = 6. How can we be sure that these integers even exist? Doesn't the Euclidean algorithm give us integers x,y such that 123x + 567y = gcd(123, 567)? I thought that was the only case when it was guaranteed. GCD(123, 567) = 3, so I'm just making sure that there is in fact a way to do this question.
Answer: It's definitely possible, but I'm not going to tell you anything further until you think about it some more. If you still don't see what's happening in a few days, ask me again.- Question: I'm a rising junior considering math 124, and I'm wondering if it would be feasible to take math 124 without math 122. The only reason I'm wondering is that I'm a CS concentrator the meeting times and workload of 122 and 124 would prevent me from taking some cs courses I'm interested in. I'm through math 21b and I've also taken math 102 and have had elementary number theory in computer science 124. Would I be hurting myself if I enrolled in your course without concurrently enrolling in math 122? Do
Answer: How much do you know about groups, rings, and fields?
Just what I've learned in 102, where we i'd say 75% of the course was an intro to the three, with a focus on group theory (a good amount of time spent on matrix groups) and finite fields. So I know basic properties and have proven simple to maybe intermediate results (isomorphisms and such).
Your background seems sufficient. It should be possible for you to fill in any gaps as the semester progresses. If you haven't already, take a look at last year's course web page. The course will be similar this semester, but with more emphasis on elliptic curves (and probably crypto), and more interesting homework problems.