9.5 Coursework Sheet 4
Hand in your solutions in the appropriate way by Monday, 06 November 2023, 19:00.
Exercise 1
Use the remainder theorem to establish that
- every odd integer is either of the form \(4k+1\) or \(4k+3\);
- the square of any integer is either of the form \(3k\) or \(3k+1\);
Exercise 2
The following is an alternative algorithm to compute the \(\gcd\) of two integers \(a\) and \(b\). \[ \gcd(a,b) = \begin{cases} a&\text{ if }a=b;\\ 2\gcd(a/2,b/2)&\text{ if }a\text{ and }b\text{ are both even;}\\ \gcd(a/2,b)&\text{ if }a\text{ is even and }b\text{ is odd;}\\ \gcd(a-b,b)&\text{ if }a\text{ and }b\text{ are both odd and }a>b. \end{cases} \] Use this algorithm to compute \(\gcd(2106,8318)\).
Exercise 3
For each of the following linear Diophantine equations determine the number of solutions for which \(x,y\) are both positive integers:
- \(23x+15y=130\)
- \(26x+39y=247\)
- \(72x+21y=1000\)
Exercise 4
For which integer values of \(k\) does the following equation have integer solutions for \(x\) and \(y\)?
\[42=35x+ky.\]
Exercise 6*
- The Fibonacci numbers, 0, 1, 1, 2, 3, 5, 8 are given by \(F_0=0, F_1=1, F_{n+2}=F_n+F_{n+1}\), so each number is the sum of the two previous numbers. Suppose Euclid’s algorithm is used to work out gcd\((F_n,F_{n+1})\): \[ \text{gcd}(F_{n+1},F_{n}) =\text{gcd}(r_1,F_{n})=\text{gcd}(r_1,r_2)=\text{gcd}(r_3,r_2)=\cdots= \text{gcd}(r_N,r_{N-1})=\text{gcd}(0,r_{N-1})=r_{N-1}\] where \(r_N\) is the first remainder equal to 0.
In this case what are the remainders \(r_i\)? (You do not have to prove this formally). What is \(N\)?.
- Using the approximation \(F_n \sim \frac1{\surd5}(\frac{1+\surd5}2)^n\), estimate the number of steps \(N\) in Euclid’s algorithm needed to compute the gcd of two consecutive 100 digit Fibonacci numbers.
In fact consecutive Fibonacci numbers are as bad as it gets. Euclid’s algorithm is never slower than this.