# Math 124: Virtual Office Hours

This is a list of questions that students have asked me, along with my responses. If you have a question, send email to [email protected].

• Question/Answer:
> 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.


• Question/Answer:
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


• Question/Answer:
> 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.


• Question/Answer:
> 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 and  lattice, 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);
>
> 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);
> RSeriesPrinting := 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 := map RealField() | 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.

`