|
Elementary Number Theory Fall 2005 Homework |
 |
 |
|
Elementary Number Theory Fall 2005 Homework |
|
|
| Week | Homework |
| 8/24-26 |
(1) Prove that if the positive integer a divides 1, then a=1. (2) Let a and b be positive integers. Prove that if n|(a-1) and n|(b-1), then n|(ab-1).
(3) For each pair of integers, use the Euclidean Algorithm to find the greatest common divisor. (4) Prove that gcd(n, n+1) = 1 for all integers n. |
| 8/29-9/2 |
(1) Prove that gcd(a,b,c) = (gcd(a,b),c). (2) Let m and n be positive integers. Prove that, if (m,n) = mx+ny, then xy is nonpositive. (3) Prove that if a|c and b|c, then [a,b]|c. (4) One might be tempted to generalize Theorem 2.9 as [a,b,c] = abc/(a,b,c). Is this valid? Explain. |
| 9/5-9 |
(1) Let a, n be positive integers, a>1. Prove that a-1 divides an-1. (2) Let m, n be positive integers. Prove that 2m divides n if and only if 2m divides the number formed by the last m digits of n. (3) Prove that for any positive integers n, 3 divides 22n+1+1. (4) Let a, n be integers > 1. Prove that, if an-1 is prime, then a=2 and n is prime. |
| 9/12-16 |
(1) Find all primes between 220 & 250. (2) Suppose n is an integer > 8. Prove that if n-2 and n+2 are both prime then 3|n. (3) Prove that if p and q are distinct primes such that pq|n2, then pq|n. (4) Prove that if p is prime and 0 < k < p, then p divides the binomial coefficient (p choose k). |
| 9/19-23 |
(1) For integers n1, n2, ..., nk, prove that there exists an integer n such that (4n1+1) (4n2+1) ... (4nk+1) = 4n+1 . (2) Find k such that 3k || 100! .
(3) Reduce each of the following congruences as much as possible by cancellation.
(4) Determine which of the following relations on the positive integers is an equivalence relation. Justify your conclusion. |
| 9/26-30 |
(1) Use congruences to verify each of the following divisibility statements. (a) 13 | (1456+1); (b) 17 | (18554+1); (c) 233 | (229-1); (d) 223 | (237-1); (e) 431 | (243-1); (f) 167 | (283-1).
(2) Find all solutions of each of the following linear congruences. (3) If m and n are natural numbers, prove that m2n = 1 (mod m+1) . (4) If a1a2...ar = 2 (mod 4), prove that there exists j (between 1 and r) such that aj = 2 (mod 4) and ak is odd for all k different from j. |
| 10/3-7 |
(1) Find all positive integer solutions to each of the following equations. (a) 2x + 5y = 47; (b) 7x + 4y = 59; (c) 8x + 5y = 46; (d) 4x + 9y = 50; (e) 13x + 10y = 499; (f) 12x + 17y = 299.
(2) Solve each of the following systems of simultaneous congruences. (3) Prove that if p is prime and (a,p) = 1, then the congruence ax = b (mod p) has the solution x = ap-2b (mod p). (4) Prove that if p and q are primes and q|(ap-1), then q|(a-1) or p|(q-1). |
| 10/10-14 |
(1) Solve the following congruences for x. (a) x113 = 347 (mod 463); (b) x91 = 17 (mod 122); (c) x329 = 452 (mod 1147); (2) Try to solve the congruence x2 = 23 (mod 1279). What goes wrong? More generally, explain why we can't use our methods to compute "square roots" modulo a prime. (3) A composite number m is called a Carmichael number if the congruence am-1 = 1 (mod m) is true for all a that are relatively prime to m. Verify that 561 is a Carmichael number. (4) Prove that if n is composite and n > 4, then (n-1)! = 0 (mod n). |
| 10/17-21 |
(1) Let fn = 22^n + 1 be the n'th Fermat number. Prove that if m>n then fm = 2 (mod fn). (2) Evaluate tau(n) and sigma(n) for 40 <= n <= 50. (3) Prove that tau(n) is odd if and only if n is a square. (4) If sigma(n) is prime, prove that n = q^k for some prime q and some positive integer k. |
| 10/24-28 |
(1) Evaluate mu(n) and phi(n) for each of the following values of n. (a) 42 (b) 79 (c) 1000 (d) 945 (e) 91 (f) 144 (2) Prove that sumd|n mu(d) tau(n/d) = 1. (3) Prove that sumd|n sigma(d) mu(n/d) = n. (4) Let M(n) = n and g(n) = M-1(n). Find g(p), g(p2), and g(pk) for k>2, where p is prime. Prove that g(n) = mu(n) M(n). |
| 10/31-11/4 |
(1) For each integer 0 < t < 20 for which gcd(t,20) = 1, find the order of t (mod 20). (2) Find all primitive roots modulo 19. (3) Suppose gcd(m,n) = gcd(a,m) = gcd(a,n) = 1. Prove that ordmn(a) = lcm ( ordm(a) , ordn(a) ).
(4) Compute the gcd of the following pairs of polynomials mod 7. |
| 11/7-11 |
(1) For each integer 1 < t < 23, determine if there are any primitive roots modulo t. (2) Prove that if p is an odd prime and g is a primitive root (mod p), then g(p-1)/2 = -1 (mod p). (3) Find all the quadratic residues and nonresidues (mod p) for p = 13, 17, and 19. (4) Prove that if p is an odd prime, then every primitive root (mod p) is a quadratic nonresidue (mod p). |
| 11/14-18 |
(1) Let p be an odd prime. Prove that if p does not divide a, then a(p-1)/2 = 1 or -1 (mod p).
(2) Prove the following for any real number x: (3) Given positive integers a and b, form the line segment in R2 joining the origin to the point (a,b). Show that the number of integer points (i.e., points in Z2) on this line segment is gcd(a,b)+1. Generalize to a line segment joining the point (a,b) to (c,d), for given integers a, b, c, d.
(4) Evaluate the following Legendre symbols: |
| 11/21-23 |
(1) Prove that if p and q are odd primes and q = 2p+1, then (p/q) = (-1/p).
(2) Evaluate each of the following Jacobi symbols. (3) Evaluate (5/77). Does the congruence x2 = 5 (mod 77) have solutions? (4) Evaluate (3/133). Does the congruence x2 = 3 (mod 133) have solutions? |
| 11/28-12/2 |
(1) Compute a partial-fraction expansion of f(x) = x/(1-x-x2). (2) Define the Lucas numbers Ln through L1 = 1, L2 = 3, and Ln = Ln-1 + Ln-2 for n>2. Prove that Ln = Fn+1 + Fn-1. Deduce from this a closed formula for Ln.
(3) Find the finite continued-fraction representation with integer terms for each of the following:. (4) Prove that the rational number whose continued-fraction expansion representation consists of n 2's is Pn+1/Pn, where Pn is the n'th Pell number, defined by P0 = 0, P1 = 1, and Pn = 2 Pn-1 + Pn-2 for n>1. |
"Data! Data! Data!", he cried, impatiently. "I can't make bricks without clay."
Sherlock Holmes (by Sir Arthur Conan Doyle, 1859-1930)
