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

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

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

A kind of library