(n).
1. There is a unique way to extend the sequence of Fibonacci numbers F0=0, F1=1, ..., to a sequence {Fi}, i < 0, so that the relation Fn+2=Fn+Fn+1 holds for all n in Z. For n in N, express F–n in terms of the 'standard' Fibonacci numbers {Fi}, i >= 0. Give justification for the expression.
2. Prove by induction that Fn >= n for all n >= 5.
3. The kth harmonic number, denoted Hk, is the sum 1 + (1/2) + ... + (1/k). So, e.g., H1=1, H2=3/2, and H3=11/6. Prove by induction that the sum of the first n harmonic numbers is (n+1)(Hn+1–1).
4. Euclid's proof that there exist infinitely many primes yields
an algorithm for constructing an infinite list of primes.
At each stage of the algorithm, one takes the current list of primes,
multiplies them together, adds 1, and factors.
The prime factors are then added to the list.
Starting with {2}, one gets 2+1=3, which is already prime, so now the list
reads {2, 3}.
After one more iteration, the list becomes {2, 3, 7}.
(a) Work out two more iterations of the algorithm.
(b) Notice that the prime 5 got skipped after the second iteration of
the algorithm.
Do any of the next few iterations produce the prime 5?
Try to explain what contributes to the appearance, or non-appearance,
of 5 in the list, in successive applications of the algorithm.
5. Prove by induction that for every n, the binomial coefficient
| / | 2n-1 | \ |
| \ | k | / |
1. Do problems 10 (b) and (c) on p. 20 of the textbook (show that the sum of the entries in the nth row of Pascal's triangle is 2n, and the alternating sum of the entries is 0).
2. In the game of bridge (a card game), players bid at a contract, and if successful at play, they get a score in accordance with the amount that they bid. A certain kind of a bid, called a No Trump bid, results in an award of 40+30k points, where k is an integer in the range 0 <= k <= 6. Characterize the totals one can get by adding up the scores from successful No Trump contracts.
3. If a, b, and c are positive integers, such that no pair among them is relatively prime, must it be true that there exists an integer d > 1 such that d divides each of a, b, and c? Give a proof or a counterexample.
4. Solve the following systems of congruences (== denotes "congruent to")
(a) x == 1 (mod 8),
3x == 7 (mod 13).
(b) x == 7 (mod 25),
x == 22 (mod 35).
5. If a and b are relatively prime, and ab is a perfect square, show that a and b are both perfect squares.
6. If a and b are positive integers, with a > b, let us say that a is close to b if the Euclidean algorithm applied to a and b terminates after 2 or fewer applications of the division algorithm. Suppose we are told that b is a one-digit integer, such that more than half of the two-digit integers are close to b. What are the possible values of b?
1. (a) Let k >= 2 and a1,...,ak >= 2 be integers.
Prove that a1a2...ak >=
a1 + a2 + ... + ak, with equality if
and only if k = 2 and a1 = a2 = 2.
(Hint: use induction on k.)
(b) Let us define a function f(n) for n >= 2 as follows.
By the Fundamental Theorem of Arithmetic, there is a unique
(up to reordering) expression of the form
n = p1p2...pk,
for some k, with each pi prime.
Then we define f(n) to be p1 + p2 + ... + pk.
By part (a), the sequence n, f(n), f(f(n)), f(f(f(n))), ... is decreasing
for a while and eventually constant: ..., s, s, s, ....
Show that for any starting value n >= 2, the constant s we obtain is
either prime or equal to 4.
2. A 50-digit number has only 0's and 1's as digits, with an equal number of 0's and 1's. What is the maximum number of 2's it can have in its prime factorization, and for which 50-digit number(s) is this maximum attained?
3. For this problem, you need to assume the statement of Dirichlet's Theorem (p. 40): if gcd(a,b) = 1, then there are infinitely many primes p == a (mod b). Now let us say that a prime p is k-isolated if p–i and p+i are composite for all i such that 1 <= i <= k. Prove that for any k, there exist infinitely many k-isolated primes.
4. Solve:
(a) 2x780 + x613 == 1 (mod 3).
(b) x1002357982 + 2x25 == 3 (mod 5).
5. In the sieve of Eratosthenes, show that the first number slashed by any prime p is the number p2 (assume we are performing the sieve on at least the first p2 positive integers).
6. What are the possible values of x1634, mod 4903? (Hint: 3 × 1634 + 1 = 4903, and 4903 is prime.)
7. Read Proposition 2.15 (p. 44), which says that any nonconstant polynomial with integer coefficients takes on infinitely many composite values. Generalize this as follows: Prove that if f(x) is any nonconstant polynomial with rational coefficients, such that f(n) is an integer for every integer n, then f(n) is composite for infinitely many integers n.
Note: the Euler phi function applied to a number n is
denoted (n).
1. For what values of n is
(n) odd?
Justify your answer.
2. Is the function
((n)) multiplicative?
(Multiplicativity was mentioned only briefly in class, but you
can find the definition on p. 59 of the book.)
If yes, give a proof.
If no, produce a pair of relatively prime integers m and n such that
((mn)) is not equal to ((m))((n)).
3. Let p be a prime which is == 3 (mod 4). Show that if c is any integer such that the equation x2 == c (mod p) has no solutions, then the equation x2 == –c (mod p) must have a solution.
4. Show that the Diophantine equation
x2 + y2 = 3
has solutions in real numbers, as well as solutions mod p for every prime p, yet fails to have any solutions mod the square of some prime. (Hint: treat the cases p == 1 (mod 4) and p == 3 (mod 4) separately, and for the latter, use the previous problem.)
Note: the Euler phi function is
denoted (n),
and the functions Pr(n), µ(n),
(n), and
(n) are
the arithmetic functions introduced in class and also described on p. 57 of
the book.
For problems 4 and 5, it should be helpful to know that 2 is a primitive root modulo the following primes: 3, 5, 11, 13, 19, 29, 37.
1. Do problem 7 on p. 58.
2. Find a simple expression for the following arithmetic function:
P0 * µ *
*
.
3. Which of the following numbers will have the largest ratio
(n)/n? the smallest ratio?
| N1 = 210, | |
| N2 = 2·3·5·7·11·13·17·19·23·29, | |
| N3 = the product of 10 distinct 50-digit primes. |
4. For each of the following primes p, determine all solutions to the equation
x6 == 1 (mod p).
(a) p = 19.
(b) p = 29.
(c) p = 239.
5. Find at least one solution to each of the following equations.
(a) x2 == 10 (mod 13).
(b) x5 == 8 (mod 37).
(c) x8 == 11 (mod 19).
6. We have seen that x2 + 1 == 0 (mod p) has a solution when p = 2 or p == 1 (mod 4), and not when p == 3 (mod 4). Use the factorization v3 – 1 = (v – 1)(v2 + v + 1) to find a similar characterization for when x2 + 3 == 0 (mod p) has a solution. (Hint: treat the cases p = 2 and p = 3 separately, and then find a general argument for p > 3 which involves the value of p mod 3.)
1. Find all solutions to:
(a) x2 – 2x – 7 == 0 (mod 17).
(b) 2x2 – 3x + 7 == 0 (mod 47).
2. Do problem 15 on p. 89.
3. What is the smallest prime p >= 11 for which none of 2, 3, 5, or 7 is a quadratic residue?
4. Explain why problem 3 has no solution if:
(a) The "5" is changed to 4.
(b) The "7" is changed to 6.
5. Compute, using quadratic reciprocity:
| (a) |
| . | (b) |
| . |
6. Using quadratic reciprocity, find a characterization of primes p for which x2 == 11 has a solution mod p.
1. Show that the set of odd primes for which x2 == 2 (mod p) has a solution (we determined this in class, or look in the book, p. 88) is the same as the set of odd primes for which 2x2 == 1 (mod p) has a solution.
2. Find all right triangles with integer side lengths, with hypotenuse of length 85.
3. Show there exist infinitely many right triangles with integer side lengths, whose hypotenuse is one unit longer than one of the legs.
4. Write out the multiplication table for residue classes of
Gaussian integers x + iy mod 3 (there are 9 such residue classes).
Use this table to deduce:
(i) there exists a primitive root for Gaussian integers mod 3;
(ii) the property 3 | zw implies 3 | z or 3 | w holds, where z and w
are Gaussian integers.
5. Exactly one of the following two equations has integer solutions.
Identify the equation, and find at least one integer solution.
(i) 5x2 + 11y2 = 23z2,
(ii) 5x2 + 11y2 = 31z2.
1. Use the Prime Number Theorem (p. 218) to prove the following asymptotic improvement to Bertrand's Postulate: If c is any real number greater than 1, then there exists a lower bound N (which depends on c) such that for every natural number n > N there is at least one prime p with n < p < c·n.
2. Show there exist natural numbers n with
(n)/n < 1/1000.
3. The function which sends n to n! is the restriction to the positive integers of a continuous function called the Gamma function. The Gamma function is defined for real v > 0 by the following formula:
| ||
 (v) = |
 |
tv–1e–tdt. |
| 0 |
(n) =
(n–1)! for every natural number n (so there is a shift by one in the
relation between n! and
the Gamma function).
(3/2)
(that is, "(1/2)!").
(v+1) =
v·(v) first,
and then to deduce (a) from this; for (b), perform the variable
substitution t = s2, and reduce the expression to a
well-known integral.
4. Explain why each of the following would be a poor choice for
G and g (the set in which secret and public keys take their
values, and the generating element used to transform
secret key into public key) in the Diffie-Hellman Key Exchange protocol.
(a) G = Z/p, where p is a 250-digit prime; g = a
250-digit integer not divisible by p. The formula for
producing public key from secret key is k = s·g mod p.
(b) G = (Z/m)*, with m = 2829;
g = 5. The formula for public key is k = gs mod m.
(Here, G has 2828 elements, and the powers of g sweep out
exactly half, or about 9 × 10248, of the elements of G.)