Math 58 - Number Theory

September 21, 2006

Homework 6 (due September 26):

Read Section 4.2. If you like, peek at 4.3.

Problems 1-3 involve a topic from Section 3.1 that we skipped over in class: Are there large gaps in the sequence of primes? Specifically, let k be a positive integer. Are there k consecutive composite numbers?

1. Here are k consecutive integers: (k+1)! + 2, (k+1)! + 3, …, (k+1)! + (k+1).

Show that they are all composite.

2. If k = 5, then the numbers given by problem 1 are 722, 723, 724, 725, 726. They are indeed all composite. But that list seems pretty wasteful, since we could have chosen much smaller numbers --- say, 24, 25, 26, 27, 28.

Find an improvement over the result in problem 1 by using the l.c.m. function

(lcm = least common multiple).

3. Actually, if we believe that the primes near x become less common as x gets larger, then we should expect that there are plenty of large gaps.

Before the prime number theorem was proved, Chebychev proved that

p(x) < 2x / ln(x)

whenever x ≥ 3. Let’s take Chebychev’s theorem as given.

Let x be a large multiple of k --- in particular, large enough that ln(x) > 2k.

Show that somewhere among the first x positive integers, there are k

consecutive composite integers.

Problems about multiplicative inverses and congruences:

4. What is the multiplicative inverse of 7 mod 13 ? (That is, find b such that 7b º 1 mod 13.)

5. What is the multiplicative inverse of 6 mod 13 ?

6. Which integers less than 8 have inverses mod 8 ? List them, and find all of their inverses.

7. Which integers less than 11 have inverses mod 11 ? List them, and find all of their inverses.

8. Suppose that x º 5 (mod 31) and x º 5 (mod 61). Prove that x º 5 (mod 1891).

(Hint: 31 and 61 are prime, and 1891 = 31 × 61.)

9. Suppose that x º 3 (mod 5) and x º 4 (mod 7). What is the least positive residue of x (mod 35)?

(end)