305 -Homework set 1

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.

This entry was posted on Monday, January 26th, 2009 at 2:24 pm and is filed under 305: Abstract Algebra I. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to 305 -Homework set 1

  1. 305 -Syllabus « Teaching page says:
    January 26, 2009 at 2:33 pm

    […] Homework 1, due February 6, at the beginning of lecture. Possibly related posts: (automatically generated)What Lil’ Ones Are Reading: Two Christmas Stories […]

    Reply
  2. George Shan Lyons says:
    February 2, 2009 at 6:51 am

    Perhaps this is a stupid questions, but what does the notation (a,b) = 1 mean in the first problem? Is it a function that I have missed somewhere? Is it equivalent to a = b = 1, so that we are to prove that a = a^n = 1 and b = b = 1 for all integers n >= 1? I’m a little lost…

    Reply
  3. andrescaicedo says:
    February 2, 2009 at 8:17 am

    Hi. The notations (a,b) and {rm gcd}(a,b) mean the same thing: The greatest common divisor of a and b.
    [I agree there is a little ambiguity in using (a,b) this way, but it is standard in number theory.]

    Reply
  4. 305 -Syllabus | A kind of library says:
    February 17, 2019 at 6:34 am

    […] Homework 1, due February 6, at the beginning of lecture. [This homework was not graded.] […]

    Reply

Leave a comment