305 -Homework set 1

January 26, 2009

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 a,b are integers and (a,b)=1, then (a^n,b)=1 for all integers n\ge1.

b. This result allows us to give a nice proof of the following fact: Let n be a natural number and let m be a positive integer. If the m-th root of n, \root m\of n, 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 a/b=c/d and b+d\ne0, then \displaystyle \frac ab=\frac{a+c}{b+d}. Show that any fraction a/b with a,b integers, can be reduced so (a,b)=1. Assume that \root m\of n is rational, say a/b. Then also \root m\of n=n/(\root m\of n)^{m-1}. Express this last fraction as a rational number in terms of n,b,a. Use that (a^k,b)=1 for all k\ge1 and the general remarks mentioned above, to show that \root m\of n is in fact an integer.

2. Show by induction that for all integers k\ge 1 there is a polynomial q(x) with rational coefficients, of degree k+1 and leading coefficient 1/(k+1), such that for all integers n\ge1, we have \displaystyle \sum_{i=1}^n i^k =q(n). There are many ways to prove this result. Here is one possible suggestion: Consider \displaystyle \sum_{i=1}^n [(i+1)^{k+1}-i^{k+1}].

3. Euclidean algorithm. We can compute the gcd of two integers m,n, not both zero, as follows; this method comes from Euclid and is probably the earliest recorded algorithm. Fist, we may assume that m, n are positive, since (m,n)=(|m|,|n|), and also we may assume that m\ge n, so m>0. Now define a sequence r_0,r_1,r_2,\dots of natural numbers as follows:

  • r_0=m, r_1=n.
  • Given r_i,r_{i+1}, if r_{i+1}=0, then {\tt STOP}.
  • Otherwise, r_{i+1}>0, and we can use the division algorithm to find unique integers q,r with 0\le r<r_{i+1} such that r_i=r_{i+1}q+r. Set r_{i+2}=r.
  • Let A be the set of those r_k that are strictly positive. This set has a least element, say r_k. By the way the algorithm is designed, this means that r_{k+1}=0.
  •  Show that r_k=(m,n), and that we can find from the algorithm, integers x,y such that r_k=mx+ny.

(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 m>n, takes k steps. [For example, if m=35 and n=25, the algorithm gives:

Step 1: 35=25.1+10, so r_0=35,r_1=25,r_2=10.

Step 2: 25=10.2+5, so r_3=5.

Step 3: 10=5.2, so r_4=0, and (35,25)=5. Here, k=3]

Show that n\ge F_{k+1}, where the numbers F_1,F_2,\dots are the Fibonacci numbers, see Exercises 15-22 in Chapter 1 of the book.

5. Extra credit problem. With m,n,k as in the previous exercise, let t be the number of digits of n (written in base 10). Show that k\le 5t.

3 Comments | 305: Abstract Algebra I | Tagged: , , | Permalink
Posted by andrescaicedo

305 -Algebra and induction (3)

January 26, 2009

I won’t be here this Friday. Professor Marion Scheepers will cover the lecture for me. 

Definition. p>1 is prime iff the only positive divisors of p are 1 and p.

Proposition. A number p>1 is prime iff for all m, either p|m or else (p,m)=1. \Box 

Proposition. Let p be prime, and let m,n be integers. If p|mn then either p|m or p|n. \Box

In the more general setting of rings, of which the integers are an example, it is customary to call a number p prime when it satisfies the second proposition, and to call it irreducible when it satisfies the definition above. Both notions coincide for the integers, but there are examples of rings where there are irreducible elements that are not prime. We will introduce rings later on in the course.

Mathematical induction. Let N\in{\mathbb Z}. Let P(\cdot) be a statement about integers, so for each integer m, P(m) may or may not hold. Assume

  1.  P(N) holds, and
  2. \forall k\ge N\,( if P(k) holds then P(k+1) holds).

Then \forall k\ge N\,(P(k) holds).

Strong induction. Let N\in{\mathbb Z}. Let P(\cdot) be a statement about integers. Assume

  • \forall k\ge N\,( if \forall m with N\le m<k it is the case that P(m) holds, then also P(k) holds).

Then \forall k\ge N\,(P(k) holds).

Both induction and strong induction are consequences of the well-ordering principle. In fact, all three statements are equivalent. Most properties about the natural numbers are established by inductive arguments. Here are two examples:

Example 1. For all n\ge1, \displaystyle \sum_{ i=1}^n i=\frac {n(n+1)}2.

We also have \displaystyle \sum_{ i=1}^n i^2=\frac {n(n+1)(2n+1)}6 and \displaystyle \sum_{ i=1}^n i^3=\left(\frac {n(n+1)}2\right)^2. In fact, for all k\ge 1, there is a polynomial q(x) with rational coefficients, of degree k+1 and leading coefficient \displaystyle \frac1{k+1} such that for all n\ge1, \displaystyle \sum_{ i=1}^n i^k=q(n). 

Example 2. For all integers a,b, if (a,b)=1 then for all n\ge1, (a^n,b)=1.

The book discusses additional examples and has many more in the exercises. Other examples will be discussed in the first homework set, to be posted later today.

Leave a Comment » | 305: Abstract Algebra I | Tagged: , | Permalink
Posted by andrescaicedo