MATH 261 Final, Fall 2001

ERIGAN CUNIVERSIT? LIBRARY OF REIRUI Math 261 — Fall 2001—2002 Final Exam, February 1, 2002 Remarks: This exam booklet is also your auswer sheet; please answer question 0 on this page, and answer questions 1-10 inside the booklet. (The questions are repeated on pages 1- 10.) You may continue your solutions on the backs of pages and on the extra blank sheets at the end. This is a long exam: do as inuch of it as you can, and budget your time wisely. Each of questions | 10 counts for 10 points. Make sure to communicate your ideas by explaining all of your steps clearly. Calculators are allowed. Good luck! Question 0. a) Your name: b) Your AUB ID#: Question 1. a) Find the prime factorization of N = 93933. b) How many (positive) divisors does N have? ¢) Show that N is not a sim of two squares. Question 2. a) Use the Euclidean algorithm to find the multiplicative inverse of 7 modulo 33. b) Find all solutions (a. y) ¢ Z/33Z x Z/33Z satisfying 7a +5y =0 (mod 33) LIBRARY AMERICAN CATeRe Tm { lla + 7y =3 (mod 33) ° OF BEIRUA Hint: use the first equation to climinate « from the second equation. Question 3. Factorize the Gaussian integer 420 + 240i into a product of powers of Gaussian primes (times a unit, if necessary). Question 4. How many solutions (modulo 2201) are there to the equation a!4=1 (mod 2201)? Hint: 2201 = 31 x 71, where 31 and 71 are prime. Use the Chinese remainder theorem. Question 5. a) Show that the quadratic form x? + xy + 3y° represents only positive integers. b) Show that the quadratic form 2? — 61, does not represent 23, by working modulo 61. Question 6. In this problem. +. > 1. Feel free to find one or both of the solutions to each part by inspection. a) Find two different solutions to the equation «? — Sy? = -1. b) Find two different solutions to the equation x? — Sy? = —4. Question 7. a) By trial and error, write each of 23 and 29 as a sui of four squares a+b? +c+a?, where a, bic, d € {0.1,2,3,...4. b) Use your answer to part a) to write 667 = 23 x 29 as a sum of four squares. Question 8. a) Calculate the number @ defined by the eventually periodic continued fraction 2+ AMERICAN UNIVERSITY G+ 1+ 6+ 1+ 6+ 1+ LIBRARY OF BEIRUT bh) Write down the first few convergents A,,/B,, for a, witil you reach a convergent for which you can prove that Question 9. a) Let p be any prime with p > 5. Show that the equation =O0 (mod p) has at least. one solution. b) Show that if furthermore p = 1 (anod 24), then the above equation has six solutions modulo p. : Question 10. This exercise will lead you through another proof of the fact that ifp =1 (mod 4), then p is a sum of two squares. a) Let p be any prime nuuber, and fix any « #0 (mod p). Using the pigeonhole principle, show that there exist two different pairs of integers (mn) and (m/,n’) satisfying O<aineniim' an < Sp, and maton Same ten’ (mod p). Cultural uote: Writing @ = a — mn! and b n’ ~ nm, the result of part a) implies that there exist integers a,b with 0 < Jal. jb] < /p and ar = 6 (aod p). This is called Thue’s lemma and you can use if in part b) below. b) In the case where p = | (nod 4), we further choose « such that az’ = —1 (mod p). Conclude that the @ and b of ‘Thuc’s lemma satisfy w+? =p. Hint: show first that a? +62 = (nod p). Then look at the size of a? + Bb.