Math 124 Problem Set 1

1. First, we show that the binomial coefficient is an integer.
Claim: For fixed and , is an integer.
Proof. By induction. Clearly . Suppose that is an integer for . Now and for

which by the inductive hypothesis is the sum of two integers. This proves the claim.
Since is prime, it is sufficient to show that there is no factor of in the denominator. By assumption, so does not contain a factor of . Similarly, implies that , so also contains no factor of .
2. ;
;
;
;
3a. The base case is trivial. Suppose that for some . Then

as desired.
3b.If is even we may the group the terms as yielding the formula . Similarly, if is odd we have which gives the formula .
Therefore the general formula is .
4. We can run in PARI, which gives .
5. The Euclidean Algorithm gives us:
; ; ; ; so

6. yields x .
7.
8. A necessary condition is that the polynomial is irreducible over Z; this would include the condition that the gcd of the coefficients is 1. Certainly if is reducible then each factor could take the value 1 only a finite number of times (hence can be prime only at a finite number of integers). In the case where Dirichlet's theorem confirms that will take infinitely many prime values if , and in class the conjecture for was presented.
To test a given , we could use the following PARI code:

and then try for large values of . I tried this for some cyclotomic polynomials: , , and also for for up to 10 billion. All returned values close to the input. For example, for the call to gave 999999986. This suggests that for these polynomials the conjecture may be true, although it sheds little light on the general case of irreducible polynomials.
9. We can show that the Euclidean Algorithm on takes modular operations, where is the number of binary digits of . This is done by noting that if we proceed from to (where ) then . For if then . Combining this with yields . Similarly, if then . Therefore every two steps the original binary representation of is reduced by one digit.
Now since , a digit number has fewer than bits, so PARI can easily compute the gcd of two such numbers.
10. First we note that all odd integers must be congruent to , or modulo , and if then . Therefore all odd primes (except 3) must be congruent to or modulo . Next we note that if then . Therefore if then must have a prime factor (3 has no inverse).
Let . Suppose is finite. Since is nonempty (), we can define , the product of elements in . Now consider . Since , for some . But for all , , a contradiction. Therefore is infinite.
11a. We can define a function which computes

which gives .
11b. For , , so the values differ by about .