Homework 1, due at 4:00 PM on Wednesday August 31: Page 51, exercises 1, 2, 5, 6
Homework 2, due at 4:00 PM on Friday September 2: Page 52, exercises 7, 8, 9, 10
Homework 3, due at 4:00 PM on Wednesday September 7: Page 52, exercises 11, 12, 13, and the following: Show that if (a,b)=1, then (a-b, a+b) = 1 or 2. Exactly when is the value 2?
Homework 4, due at 4:00 PM on Friday September 9: Page 52, exercises 14, 15, 17, 21
Homework 5, due at 4:00 PM on Monday September 12: Page 53, exercises 22, 24, 25ab, and the following: Show that there are not infinitely many triples {n, n+2, n+4}, all of whose entries are prime..
Homework 6, due at 4:00 PM on Wednesday September 14: Page 53, exercises 26, 27, 28, and the following: Prove that if (a, b) = d, then phi(ab) = d*phi(a)*phi(b)/phi(d).
Homework 7, due at 4:00 PM on Friday September 16: 1. Find all the primitive roots of 25. 2. Prove that n^(13)-n is divisible by 2, 3, 5, 7, and 13 for any integer n. 3. Show that 1057 is not prime using Fermat's theorem. 4. Show that for all a and b and for p prime, a^p + b^p is congruent to (a+b)^p mod p. Generalize to arbitrarily many terms. Take a = b = ... = 1 to obtain an additional proof of Fermat's theorem.
Homework 8, due at 4:00 PM on Monday September 19: 1. Show that if n>1, then the sum of the positive integers less than n and relatively prime to n is n*phi(n)/2. (Hint: If m works, so does n-m.) 2. Use Fermat's theorem to show that for every a with (a, 561)=1, it is true that a^(560) is congruent to 1 modulo 561. (You may use the fact that if an integer is congruent to 1 modulo several different primes, it is congruent to 1 modulo the product of those primes.) 3. Prove that if an integer is congruent to 2 modulo 3 then it must have a prime factor congruent to 2 modulo 3. 4. Prove that phi(m) is even for all m>2.
Homework 9, due at 4:00 PM on Wednesday September 21: 1. Find all solutions of the congruences a) 20x ≡ 4 mod 30, b) 20x ≡ 30 mod 4, c) 57x ≡ 87 mod 105, d) 64x ≡ 83 mod 105. 2. Find the smallest positive integer giving remainders 1, 2, 3, 4, and 5 when divided by 3, 5, 7, 9, and 11, respectively. 3. Determine whether the congruences 5x ≡ 1 mod 6 and 4x ≡13 mod 15 have a common solution; if so, find it. 4. Prove that for each positive integer k there are infinitely many blocks of k or more consecutive integers, with none of these integers prime.
Homework 10, due at 4:00 PM on Friday September 23: 1. Solve the congruence x^3 - 9x^2 + 23x - 15 ≡ 0 mod 143. 2. Suppose that the polynomial f(x) with integer coefficients has degree n. Show that if the values f(a) for n+1 consecutive integers a are all divisible by p, then p divides f(a) for all integers a. 3. Reduce the following congruences to equivalent congruences of degree less than 7: x^11 + x^8 + 5 ≡ 0 mod 7, x^20 + x^13 + x^7 + x ≡ 2 mod 7. 4. Solve x^2 + 5x + 24 ≡ 0 mod 36.
Homework 11, due at 4:00 PM on Monday September 26: 1. Show that the product of the quadratic residues of p is congruent to 1 or -1 mod p, depending on whether p ≡ 1 or -1 mod 4. (Hint: Use a primitive root.) 2. Suppose that a prime p does not divide a. Show that if p ≡ 1 mod 4, then both or neither of a and -a are quadratic residues mod p, while if p ≡ 3 mod 4, then exactly one is a residue. 3. Show that if p does not divide m, then the sum of (ma/p) for all a from 1 to p is equal to 0. 4. Show that if p ≡ 3 mod 4, then the solutions of x^2 ≡ a mod p, if it is solvable, are x ≡ a^((p+1)/4) and x ≡ -a^((p+1)/4).
Homework 12, due at 4:00 PM on Wednesday September 28: 1. Decide whether the congruences x^2 ≡ 2455 mod 4933 and x^2 ≡ 245 mod 27496 are solvable. 2. Show that if n is a value assumed by the polynomial x^2 - ay^2 for some integers x, y, then for every prime divisor p of n, either p divides x or (a/p) = 1. 3. Evaluate (751/919) and (31706/43789). 4. Find solutions to the congruence x^2 ≡ 7 mod 787. (You may want to use problem 4 from last time.)
Homework 13, due at 4:00 PM on Friday September 30: 1. Problem 3.3. 2. Prove that for Jacobi symbols, (P1/Q)(P2/Q) = (P1*P2/Q). 3. Classify the odd primes p such that 3 is a quadratic residue modulo p. 4. For which primes p do there exist integers x and y with (x,p)=1, (y,p)=1, such that x^2 + y^2 = 0 mod p?
There will be no homework due on Monday October 3, due to the midterm exam in the Testing Center that day. There will be no class on Monday October 3, due to the exam.
Homework 14, due at 4:00 PM on Friday October 7: 1. Problem 3.1. 2. Let f(n) be a multiplicative function on the positive integers, so that f(mn) = f(m)f(n) if (m,n) = 1. Suppose that the series given by the sum ∑ f(n) over all positive integers n converges absolutely. Show that this series is equal to the product ∏ ∑ f(p^k), where the product is over all primes p and the sum is over all nonnegative integers k. 3. If in addition f(n) satisfies f(mn) = f(m) f(n) for all m and n, show that f(p) is not equal to 1 for any prime p and that ∑ f(n) = ∏ (1-f(p))^(-1). 4. Using the bounds for pi(x) in this section, how large does x need to be to guarantee that there are 10 primes less than or equal to x? Repeat for 100, 10^3, 10^4, 10^5 primes.
Homework 15, due at 4:00 PM on Monday October 10: 1. Problem 3.4. 2. Show that σ(n), the sum of the positive divisors of n, satisfies σ(ab) = σ(a)σ(b) when (a,b)=1. 3. Show that σ(p^e) = (p^(e+1)-1)/(p-1). 4. Use problems 2 and 3 to show that if N is an odd perfect number, then it has exactly one prime divisor appearing to an odd power in its prime factorization.
Homework 16, due at 4:00 PM on Wednesday October 12: 1. Problem 3.7. 2. Problem 3.8. (Use induction on m.) 3. Prove that any two consecutive terms of the Fibonacci sequence are relatively prime. 4. Show that the number of ways to cover a 1-by-n rectangle with 1-by-1 squares and 1-by-2 dominoes is the (n+1)st Fibonacci number f_(n+1).
Homework 17, due at 4:00 PM on Friday October 14: 1. Problem 3.5. 2. Problem 3.9. 3. Use problem 4 from last time to prove that f_1 + f_3 + ... + f_(2n+1) = f_(2n+2), by counting the number of ways to cover a 1-by-2n+1 board with squares and dominoes in two ways. (Separate tilings by the location of the last square.) 4. Give a similar combinatorial proof of Lemma 3.1.4.5(c) by counting the number of ways to cover a 1-by-n board in two ways. (Separate tilings by counting the number of dominoes.)
Homework 18, due at 4:00 PM on Monday October 17: 1. Problem 3.11. 2. Let k and a be positive integers with a at least 2. Show that k divides phi(a^k - 1). (Hint: Think about the multiplicative group of Z modulo a^k-1.) 3. Show that if the prime p divides phi(m) but does not divide m, then there is at least one prime factor q of m such that q is congruent to 1 modulo p. 4. Let p be prime. Use the previous two problems to show that there are infinitely many primes that are congruent to 1 modulo p.
Homework 19, due at 4:00 PM on Wednesday October 19: 1. Problem 3.12. 2. Find all Pythagorean triples whose terms form an arithmetic progression. Repeat for a geometric progression. 3. Show that in any Pythagorean triple (a, b, c), at least one of a, b is divisible by 3 and at least one of a, b, c is divisible by 5. 4. What is the discriminant of the quadratic form x^2 - 2xy + y^2? Which integers can be represented by this form?
Homework 20, due at 4:00 PM on Friday October 21: 1. Problem 3.15a. 2. Show that the identity at the bottom of page 91 is a consequence of the formula for multiplying the complex numbers (a+bi) and (c+di) together. 3. Problem 3.13. (Hint: Use Dirichlet's approximation theorem from class.) 4. Show that a prime for which -2 is a quadratic residue can be represented as x^2 + 2y^2.
Homework 21, due at 4:00 PM on Monday October 24: 1. Recall that quaternions are of the form (a, b, c, d) = a + b*I + c*J + d*K, where I*I = J*J = K*K = -1, I*J = K, J*K = I, K*I = J, J*I = -K, K*J = -I, I*K = -J. Define the conjugate of a quaternion (a, b, c, d) as (a, -b, -c, -d), and define the norm of (a, b, c, d) as a^2 + b^2 + c^2 + d^2. Show that the norm of a product of quaternions is equal to the product of the norms. 2. Recall that a modular form f(z) maps the upper half plane H into the complex numbers and satisfies f((az+b)/(cz+d)) = (cz+d)^k f(z) for all integer matrices ((a, b), (c, d)) of determinant 1. Show that the weight k of any modular form must be even. 3. Show that a constant multiple of a modular form of weight k is a modular form of weight k, that the sum of two modular forms of weight k is a modular form of weight k, and that the product of two modular forms of weights j and k is a modular form of weight j+k. 4. Let σ_k(n) be the sum of the kth powers of the positive divisors of n. Recall that for even k greater than 2, E_k(z) = 1 - 2k/B_k*∑σ_(k-1)(n) q^n is a modular form of weight k. Using the fact that the space of modular forms of weight 8 is one-dimensional, show that σ_7(n) = σ_3(n) + 120 ∑ σ_3(i) σ_3(n-i), where the sum is from i=1 to i=(n-1).
Homework 22, due at 4:00 PM on Wednesday October 26: 1. Problem 3.6. 2. Expand √3 and √2/2 as infinite continued fractions. 3. Find the first eight continued fraction approximations to pi. 4. Find the interval on the real line whose points have continued fraction expansion beginning (2; 1, 2, 1, 1, 4, 1, 1, ...).
Homework 23, due at 4:00 PM on Friday October 28: 1. Prove parts (1) and (2) of Lemma 3.3.3. 2. Problem 3.19. 3. Problem 3.20. 4. Prove that for an odd integer m, the function sending the integer n to the value of the Jacobi symbol (n/m) is a Dirichlet character.
Homework 24, due at 4:00 PM on Monday October 31: 1. Problem 3.34. 2. Evaluate ∑ μ(j!), where the sum is from j=1 to infinity. 3. Use Theorem 2.4.3.2 and the inversion formula to show that φ(n) = n ∑ (μ(d)/d), where the sum is over all positive d dividing n. What does this give for φ(p^a) for a prime p? 4. Show that for any positive integer n, σ(n) = ∑φ(d) τ(n/d), where the sum is over all positive d dividing n. Hint: Theorem 3.6.1.
Homework 25, due at 4:00 PM on Wednesday November 2: 1. Problem 3.23. 2. Problem 3.24. 3. Problem 3.25. 4. Problem 3.26. (Recall that twin primes are primes that differ by 2. See section 3.4.)
Homework 26, due at 4:00 PM on Friday November 4: 1. Problem 3.21. 2. Problem 3.22. 3. Explicitly write down all of the Dirichlet characters modulo 8 and modulo 10. (For example, for a character χ modulo 8, note the values of χ(0), χ(1), ... χ(7). You will want to use what you know about the structure of the group of units modulo 8 and modulo 10 to determine all of the possibilities.) 4. Dirichlet's theorem implies the following statement: If h and k > 0 are any two integers with (h, k) = 1, then there exists at least one prime number of the form kn+h. Prove that this statement also implies Dirichlet's theorem.
Homework 27, due at 4:00 PM on Monday November 7: 1. Problem 4.2. 2. Problem 4.4. 3. Problem 4.6. 4. Problem 4.7.
Homework 28, due at 4:00 PM on Wednesday November 9: 1. Problem 4.9. 2. Problem 4.11. 3. Problem 4.12. 4. Problem 4.13.
Homework 29, due at 4:00 PM on Friday November 11: 1. Problem 4.14. 2. Problem 4.17. 3. Show that O(o(g(x))) and o(O(g(x))) = o(g(x)). 4. Show that the integral ∫1/t^2 dt, where the integral is from x to infinity, is O(1/x). Show that ∑ 1/n^2, where the sum is over all n > x, is O(1/x).
There will be no homework due on Monday November 14, due to the midterm exam in the Testing Center that day. There will be no class on Monday November 14, due to the exam.
Homework 30, due at 4:00 PM on Friday November 18: 1. Problem 5.1. 2. Problem 5.2. 3. Problem 5.3. 4. Problem 5.4.
Homework 31, due at 4:00 PM on Monday November 21: 1. Problem 5.7. 2. Problem 5.8. 3. Problem 5.9. 4. Suppose that n is prime and k is not 0 or n. Show that the binomial coefficient given by n above k is congruent to 0 mod n. Show that (x-a)^n is equal to x^n - a in the polynomial ring Z_n[x].
Homework 32, due at 4:00 PM on Monday November 28: 1. Problem 5.12. 2. Problem 5.14. 3. Test 118901521 for primality using the Fermat test for several values of a. Is 118901521 prime? 4. Show that any Euler pseudoprime to the base b must also be a pseudoprime to the base b.
Homework 33, due at 4:00 PM on Tuesday November 29: 1. Problem 5.15. 2. Problem 5.16. 3. Test 104173 for primality using the Solovay-Strassen test. Use enough values of b to be 99 percent sure that it is prime. 4. Test 38200901201 for primality using the Miller-Rabin test with b = 2. Then test using b = 3. Explain your results.
Homework 34, due at 4:00 PM on Wednesday November 30: 1. Use the Lucas-Lehmer algorithm with p=31 to show that 2147483647 is prime. Note that the algorithm on page 230 has a typo; the mod 2^(p-1) on the fourth line from the bottom should read mod (2^p)-1. 2. Problem 5.19. 3. Decrypt the affine cipher HFQWQWCELLYCH, given that the first two letters are TH. 4. Show that problem 5.23 cannot be done, even if a is not 1 and b is not 0. (Hint: What happens to even or odd numbers?)
Homework 35, due at 4:00 PM on Friday December 2: 1. Problem 5.17. (Note that the message a does not need to be relatively prime to p*q.) 2. In an RSA system, the public key of a given user is e = 31, n = 3599. What is the private key of this user? 3. The ciphertext 5859 was obtained from the RSA algorithm using n = 11413 and e = 7467. Using the factorization 11413 = 101*113, find the (numerical) plaintext. 4. Suppose two users Alice and Bob have the same RSA modulus n and suppose that their encryption exponents e_A and e_B are relatively prime. Charles wants to send the message m to Alice and Bob, so he encrypts to get c_A ≡ m^(e_A) and c_B ≡ m^(e_B). Show how an attacker Eve can find the message m if she intercepts c_A and c_B.
Homework 36, due at 4:00 PM on Monday December 5: 1. Stein problem 6.2. 2. Stein problem 6.3. 3. Show that if a point P on an elliptic curve E over the real numbers has order 3, so that P+P+P = 0, then P is a point of inflection for the graph of E. 4. Let Q be the point (2, 3) on the curve E: y^2 = x^3 + 1. Show that 6Q = 0.
Homework 37, due at 4:00 PM on Wednesday December 7: 1. Factor 618240007109027021 using Pollard's p-1 method. 2. Let E be the curve y^2 = x^3 + 4x + 4 containing the point P = (1, 3). Working mod 2773, try to compute 3P and explain how this allows you to factor 2773. 3. Choose three elliptic curves and compute the number of points on each curve modulo 11. How far is this from the expected number of points? 4. Factor n=35 by the elliptic curve method by using the elliptic curve y^2 = x^3 + 5x + 8 and the point P = (1, 28).