This set is due February 6 at the beginning of lecture. Consult the syllabus for details on the homework policy.
1. a. Complete the proof by induction that if
are integers and
, then
for all integers
.
b. This result allows us to give a nice proof of the following fact: Let
be a natural number and let
be a positive integer. If the
-th root of
,
, is rational, then it is in fact an integer. (The book gives a proof of a weaker fact.) Prove this result as follows: First verify that if
and
, then
. Show that any fraction
with
integers, can be reduced so
. Assume that
is rational, say
. Then also
. Express this last fraction as a rational number in terms of
. Use that
for all
and the general remarks mentioned above, to show that
is in fact an integer.
2. Show by induction that for all integers
there is a polynomial
with rational coefficients, of degree
and leading coefficient
, such that for all integers
, we have
There are many ways to prove this result. Here is one possible suggestion: Consider
.
3. Euclidean algorithm. We can compute the gcd of two integers
not both zero, as follows; this method comes from Euclid and is probably the earliest recorded algorithm. Fist, we may assume that
are positive, since
, and also we may assume that
, so
. Now define a sequence
of natural numbers as follows:
,
.
- Given
, if
, then
.
- Otherwise,
, and we can use the division algorithm to find unique integers
with
such that
. Set
.
- Let
be the set of those
that are strictly positive. This set has a least element, say
. By the way the algorithm is designed, this means that
.
- Show that
, and that we can find from the algorithm, integers
such that
.
(If the description above confuses you, it may be useful to see the example in the book.)
4. Assume that the application of the algorithm, starting with positive integers
, takes
steps. [For example, if
and
, the algorithm gives:
Step 1:
, so
.
Step 2:
, so
.
Step 3:
, so
, and
. Here,
]
Show that
, where the numbers
are the Fibonacci numbers, see Exercises 15-22 in Chapter 1 of the book.
5. Extra credit problem. With
as in the previous exercise, let
be the number of digits of
(written in base 10). Show that 