** Next:** About this document ...

**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 .

** Next:** About this document ...
William A Stein
2001-10-11