Math 58 – Elementary Number Theory

November 16, 2006

 

What’s on the Exam?  #2

 

First-page header

 

Name_____________________________

Math 58 – Elementary Number Theory

November 16, 2006

 

Exam 2 – Due at start of class Tuesday, November 21

 

Take this exam at a time and place of your choosing.  Time limit: 4 hours from start to finish.    You may use a calculator but not a computer.  You may use any paper reference that was prepared (a) by anyone before class time on November 16 or (b) by you at any time.  You may consult the course web site but no other web or electronic resources.  Write your answers on this paper, your own paper, or both.  It isn’t necessary to turn in scratch paper.  There are  11  numbered questions on  5  pages.

Show your work.  (It may sometimes be necessary for full credit, and it’s always necessary for part credit.)

Return this exam in class or to my office by 11:20am on Tuesday, November 21.

 

Exam covers…

 

            Everything covered on the first exam

            Everything covered in class or in homework

            Text sections: 

                        5.5  (just the ISBN system)

                        6.1  (Wilson’s Theorem, Fermat’s Little Theorem)

                        6.3  (Euler’s Theorem, af(n)=1 (mod n) when (a,n)=1)

                        7.1, 7.2, 7.3 (through p. 259), 7.4

                                    (especially exercises 37-42, p. 247, and note preceding 37)

                        8.4  (RSA, not Rabin)

                        9.1, 9.2 (as treated in class)

                        11.1, 11.2

                        13.1, 13.2 (superficially), 13.3 (but not Waring)

            Also:

                        Multiplicative functions and convolution (= Dirichlet product)

                                    as covered in class and homework;

                        Gaussian integers (Ch. 14) as covered in class and homework, including

                                    the dose added to the web ca. 11/13/06

 

            Since you have access to the text, I wouldn’t be above asking about other sections.

 

 

                       

                       

 

 

 

Be able to compute…

 

            t(n), f(n), s(n)  for positive integers n; know formulas for these functions

                        that would work for values of n too large to compute the values directly

                        from the definitions

 

            (f * g) (n),  if you know how to compute  f(n),  g(n)

 

            , the Legendre symbol, whenever a is an integer and p is an odd prime.

           

            m(n) for positive n  (the Mobius function)

 

Multiplicative functions:

 

            Understand the functions I, 1, N, t, f, s, m, at least

                        (1(n) = 1 always, N(n) = n always, I(n) = 0 except I(1) = 1)

 

            I is an identity for *

 

            Each function f has an inverse g such that f*g = g*f = I  (that is, if f(1) is not 0)

 

            m  is the inverse for  1

 

            When are functions (a) multiplicative or (b) completely multiplicative?

 

            If f and g are multiplicative, so is f*g and so are the inverses of f and g.

            If f and g are completely multiplicative, then f*g need not be completely multiplicative.

 

            1 * 1 = t,    N * 1 = s,   f * 1 = N,   N * N = Nt

 

            Mobius inversion:   f * 1 = F  Û  F * m = f

 

Lagrange:  A polynomial of degree n with coefficients in Zp* can have at most n roots in Zp*.

 

Proof that  Zp*  has a generator (primitive root):  For d | (p-1),  let  f(d) = number of elements

            of Zp* that have order d, and F(d) = number of elements that satisfy xd=1 (mod p).  Then

            it turns out that F(d) = d whenever d | (p-1).  Also f*1=F, so F*m=f.  When computing

            f(p-1), F is the same as N, so f(p-1) = (F*m)(p-1) = (N*m)(p-1) = f(p-1) which isn’t

            zero, so there’s an element of order p-1, and it’s a generator.

 

 

 

 

 

 

 

Quadratic residues (with respect to odd primes p):

 

            QR times QR = QR

            QR times NR = NR

            NR times NR = QR

 

            1, 4, 9, are always QRs

            -1 is QR if p = 1 ( mod 4 )

            2 is QR  if p = ±1 ( mod 8 )

           

            Quadratic residues are never generators.

 

            Euler’s criterion:  a is a QR Û a((p-1)/2) = 1 (mod p)

                        (It has to be +1 or –1, and +1 marks the QR’s)

 

            Gauss’s criterion:  a is a QR Û if you multiply a by each of the integers

                                    1, 2, …, (p-1)/2,

                        then an EVEN number of the results are (mod p) among the integers

                                    (p-1)/2 + 1, …, (p-1).

 

            Eisenstein’s lemma (p. 420-421, mishandled in class):

                        Assuming p is an odd prime and x is odd, then x is a QR Û

                                         is EVEN.

 

 

            Quadratic reciprocity:  If p and q are odd primes, then

 

                                    p is a QR mod q   Û   q is a QR mod p         (that is, )

                       

                        UNLESS p and q are both congruent to 3 mod 4, in which case

           

                                    p is a QR mod q   Û   q is a NR mod p         (that is, )

 

 

            Proof:  Of the EVEN lattice points inside the box bounded by the axes and the lines

                        x=p and y=q, the number below the diagonal is

                                     which, by Eisentein, controls .

                        The number above the diagonal is

                                     which, by Eisentein, controls .

                        Whether these have the same parity depends on whether there are an even

                        number of even lattice points in the box.

 

 

Diophantine equations: 

 

            Given a, b, c, find all (x, y) such that ax + by = c.

           

            For Pythagorean triples, that is, triples  (x, y, z)   such that  x2 + y2 = z2,

                        distinguish between primitive and non-primitive triples;

                        be able to look for triples mod m for convenient values of m;

                        know that the primitives are of the form (m2-n2, 2mn, m2+n2) for

                                    certain (m, n).

 

            Which positive integers can be written as sums of two squares?

                        (Ones whose prime factorizations don’t include primes of the

                        form 4k+3 with odd exponents)

 

            In how many ways?

 

            Which positive integers can be written as sums of three squares?

                        (Ones not of the form (power of 4)´(number = 7 mod 8))

 

            Which positive integers can be written as sums of four squares?

                        (All of them)

 

            Know all of the solutions to  xn + yn = zn  for x, y, z, n positive integers and n ≥ 3.

                        (Section 13.2)

 

            When is a positive integer n simultaneously a square, a triangular number, and

                        a centered hexagonal number?

 

Gaussian integers:  Be comfortable with the results in the homework, including the dose added to

            the web about 11/13/06.  In particular:  know what the primes are in this system, and

            know that any Gaussian integer can be written “uniquely” as a product of primes.

 

(end)