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

Advertisements

Like this:

LikeLoading...

Related

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

I am not sure which statement you heard as the "Ultimate $L$ axiom," but I will assume it is the following version: There is a proper class of Woodin cardinals, and for all sentences $\varphi$ that hold in $V$, there is a universally Baire set $A\subseteq{\mathbb R}$ such that, letting $\theta=\Theta^{L(A,{\mathbb R})}$, we have that $HOD^{L(A,{\ma […]

A Wadge initial segment (of $\mathcal P(\mathbb R)$) is a subset $\Gamma$ of $\mathcal P(\mathbb R)$ such that whenever $A\in\Gamma$ and $B\le_W A$, where $\le_W$ denotes Wadge reducibility, then $B\in\Gamma$. Note that if $\Gamma\subseteq\mathcal P(\mathbb R)$ and $L(\Gamma,\mathbb R)\models \Gamma=\mathcal P(\mathbb R)$, then $\Gamma$ is a Wadge initial se […]

Craig: For a while, there was some research on improving bounds on the number of variables or degree of unsolvable Diophantine equations. Unfortunately, I never got around to cataloging the known results in any systematic way, so all I can offer is some pointers to relevant references, but I am not sure of what the current records are. Perhaps the first pape […]

Yes. Consider, for instance, Conway's base 13 function $c$, or any function that is everywhere discontinuous and has range $\mathbb R$ in every interval. Pick continuous bijections $f_n:\mathbb R\to(-1/n,1/n)$ for $n\in\mathbb N^+$. Pick a strictly decreasing sequence $(x_n)_{n\ge1}$ converging to $0$. Define $f$ by setting $f(x)=0$ if $x=0$ or $\pm x_n […]

(1) Patrick Dehornoy gave a nice talk at the Séminaire Bourbaki explaining Hugh Woodin's approach. It omits many technical details, so you may want to look at it before looking again at the Notices papers. I think looking at those slides and then at the Notices articles gives a reasonable picture of what the approach is and what kind of problems remain […]

The study of finite choice axioms is quite interesting. Besides the reference given in Asaf's answer, there are a few papers covering this topic in detail. If you can track it down, I suggest you read MR0360275 (50 #12725) Reviewed. Conway, J. H. Effective implications between the "finite'' choice axioms. In Cambridge Summer School in Mat […]

I feel this question may be a duplicate, because I am pretty certain I first saw the paper I mention below in an answer here. You may be interested in reading the following: MR2141502 (2006c:68092) Reviewed. Calude, Cristian S.(NZ-AUCK-C); Jürgensen, Helmut(3-WON-C). Is complexity a source of incompleteness? (English summary), Adv. in Appl. Math. 35 (2005), […]

The smallest such ordinal is $0$ because you defined your rank (height) inappropriately (only successor ordinals are possible). You want to define the rank of a node without successors as $0$, and of a node $a$ with successors as the supremum of the set $\{\alpha+1\mid\alpha$ is the rank of an immediate successor of $a\}$. With this modification, the smalles […]

The perfect reference for this is MR2562557 (2010j:03061) Reviewed. Steel, J. R.(1-CA). The derived model theorem. In Logic Colloquium 2006. Proceedings of Annual European Conference on Logic of the Association for Symbolic Logic held at the Radboud University, Nijmegen, July 27–August 2, 2006, S. B. Cooper, H. Geuvers, A. Pillay and J. Väänänen, eds., Lectu […]

[…] 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.]