## 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 $nge1$.

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 mof 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+dne0$, 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 mof n$ is rational, say $a/b$. Then also $root mof n=n/(root mof 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 $kge1$ and the general remarks mentioned above, to show that $root mof n$ is in fact an integer.

2. Show by induction that for all integers $kge 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 $nge1$, 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 $mge 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 $0le r 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 $nge 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 $kle 5t.$

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