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

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.

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

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…

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

Marginalia to a theorem of Silver (see also this link) by Keith I. Devlin and R. B. Jensen, 1975. A humble title and yet, undoubtedly, one of the most important papers of all time in set theory.

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ with all its edges of the same color. For example, $R(3)= 6$, which is usually stated by saying that in a party of 6 people, necessarily there are 3 that know e […]

No, this is not consistent. Todorčević has shown in ZF that, in fact, there is no function $F\!:\mathcal W(S)\to S$ with the property you require. Here, $\mathcal W(S)$ is the collection of subsets of $S$ that are well-orderable. This is corollary 6 in MR0793235 (87d:03126). Todorčević, Stevo. Partition relations for partially ordered sets. Acta Math. 155 (1 […]

As suggested by Gerald, the notion was first introduced for groups. Given a directed system of groups, their direct limit was defined as a quotient of their direct product (which was referred to as their "weak product"). The general notion is a clear generalization, although the original reference only deals with groups. As mentioned by Cameron Zwa […]

A database of number fields, by Jürgen Klüners and Gunter Malle. (Note this is not the same as the one mentioned in this answer.) The site also provides links to similar databases.

You do not need much to recover the full ultrapower. In fact, the $\Sigma_1$-weak Skolem hull should suffice, where the latter is defined by using not all Skolem functions but only those for $\Sigma_1$-formulas, and not even that, but only those functions defined as follows: given a $\Sigma_1$ formula $\varphi(t,y_1,\dots,y_n)$, let $f_\varphi:{}^nN\to N$ be […]

I posted this originally as a comment to Alex's answer but, at his suggestion, I am expanding it into a proper answer. This situation actually occurs in practice in infinitary combinatorics: we use the axiom of choice to establish the existence of an object, but its uniqueness then follows without further appeals to choice. I point this out to emphasize […]

I think you may find interesting to browse the webpage of Jon Borwein, which I would call the standard reference for your question. In particular, take a look at the latest version of his talk on "The life of pi" (and its references!), which includes many of the fast converging algorithms and series used in practice for high precision computations […]

The reference you want is MR2768702. Koellner, Peter; Woodin, W. Hugh. Large cardinals from determinacy. Handbook of set theory. Vols. 1, 2, 3, 1951–2119, Springer, Dordrecht, 2010. Other sources (such as the final chapter of Kanamori's book) briefly discuss the result, but this is the only place where the details are given. More recent papers deal with […]

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

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…

Hi. The notations and mean the same thing: The greatest common divisor of and .

[I agree there is a little ambiguity in using this way, but it is standard in number theory.]

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