9.7 Coursework Sheet 6
Hand in your solutions in the appropriate way by Monday, 20 November 2023, 19:00.
Exercise 1
Decide whether each of the following congruences is true or false:
- \([6]\times [38]\equiv [-2]\) (mod \(5\))
- \([24]\times[32]\equiv [2]\times [6]\) (mod \(7\))
Exercise 3
Prove that the following polynomials have no integer roots:
- \(x^3-x+1\),
- \(x^3+x^2-x+1\),
- \(x^3+x^2-x+3\).
Exercise 4
Find the least non-negative residue of each of the following:
- \(24\times 33\) (mod \(35\))
- \(17\times 18\) (mod \(35\))
Exercise 5
Let \(f(x)=(x^2-13)(x^2-17)(x^2-221)\). For \(n=2,3,5,7\) show there exists \(x\) such that \(f(x)\equiv 0 \hbox{ mod } n\).
Exercise 6*
- The Fibonacci numbers \(0,1,1,2,3,5,8,\cdots\) are given by \(F_0=0,F_1=1\) and \(F_{n+2}=F_{n+1}+F_{n}\) for \(n \geq0\). Let \(m>0\) be in \(\mathbb{Z}\). Express the congruence classes \([F_{n+2}],[F_{n-1}]\) modulo \(m\) in terms of \([F_{n+1}],[F_{n}]\).
- How many different ordered pairs of congruence classes are there modulo \(m\)?
- Johny’s father cooks all Johny’s meals. Unfortunately he only knows how to cook \(m\) meals. Must Johny eventually have two consecutive meals that are exactly the same as two consecutive meals he had before?
- Show that for every \(m>0\) in \(\mathbb{Z}\), there exists \(a>0\) in \(\mathbb{Z}\), such that for every \(n\geq0\) in \(\mathbb{Z}\) we have \(m|F_{an}\).
(Hint: Use (c) to write down a pair of equations involving the congruence classes of Fibonacci numbers. Then use A10 to find the first instance of these equations holding. Also write down what you are trying to prove, in terms of congruence classes of Fibonacci numbers).