Let \(N\), \(r\) be positive integers with greatest common divisor 1, and for each integer \(m \geq 0\) let \(f(m)\) be the remainder on dividing \(r^m\) by \(N\). Show that (i) there exist distinct \(m_1\), \(m_2 > 0\) such that \(f(m_1) = f(m_2)\), (ii) there exists \(m > 0\) such that \(f(m) = 1\). Show that if \(n\) is any integer which is not divisible by 2 or 5, then there is an integer \(k\) such that \(nk\) has all digits 1 when written in base 10.
Let \(b_0\), \(b_1\), \(b_2\), \(b_3\) be integers. Show that \(b_0n^4 + b_1n^3 + b_2n^2 + b_3n\) is divisible by 24 for all integers \(n > 0\) if and only if all of the following conditions are satisfied: (i) \(2b_0 + b_1\) is divisible by 4; (ii) \(b_0 + b_2\) is divisible by 12; (iii) \(b_0 + b_1 + b_2 + b_3\) is divisible by 24.
A set \(S\) of positive integers is called sparse if the equation \(x - y = z - t\) has no solutions with \(x\), \(y\), \(z\), \(t\) in \(S\) apart from those for which \(x = y\) or \(x = z\). Show that the set 1, 2, 4, \ldots of powers of 2 is sparse. Let \(\{u_1, \ldots, u_n\}\) be a sparse set of positive integers, with \(n \geq 2\), and let \(v\) be the smallest positive integer such that \(\{u_1, \ldots, u_n, v\}\) is sparse. Prove that \(v \leq \frac{1}{2}n^3 + 1\). Show that for each integer \(N > 0\) there is a sparse set of positive integers less than or equal to \(N\) containing \([(2N)^{1/3}]\) members. [Here \([X]\) denotes the greatest integer less than or equal to \(X\).]
Express the sum of the fifth powers of the roots of a cubic equation in terms of the sum of the roots, the sum of the squares of the roots and the product of the roots. Prove that \(\frac{(x-y)^5 + (y-z)^5 + (z-x)^5}{(x-y)^2 + (y-z)^2 + (z-x)^2} = \frac{5}{2}(x-y)(y-z)(z-x)\) for all distinct real numbers \(x\), \(y\), \(z\).
Prove that by the end of a party, attended by \(n \geq 2\) people, there are two people who have made the same number of new acquaintances. Now suppose that of all the pairs of people, precisely one pair have made the same number of new acquaintances. Show that there are at most two possibilities for this number. (It is not necessary to calculate the possibilities explicitly in terms of \(n\).)
Two triangles in a plane (\(ABC\), \(A'B'C'\)) are in perspective from a point \(O\) (i.e. \(AA'\), \(BB'\), \(CC'\) meet at \(O\)). It may be assumed that all the points are distinct. (i) Prove that the points of intersection of corresponding sides lie on a straight line. (ii) Suppose now that \(BC'\) meets \(B'C\) in \(P'\), \(CA'\) meets \(C'A\) in \(Q'\), and \(AB'\) meets \(A'B\) in \(R'\). Prove that \(Q'R'\), \(BC\), \(B'C'\) meet at a point, and hence using the converse of (i) (which may be assumed), prove that \(ABC\), \(P'Q'R'\) are in perspective.
If two variables \(x\) and \(z\) are related by \[z = x + \lambda g(z)\] where \(\lambda\) is a constant, then any smooth function \(F(z)\) satisfies Lagrange's Identity \[F(z) \equiv F(x) + \lambda g(x)\frac{dF(x)}{dx} + \sum_{n=2}^{\infty} \frac{\lambda^n}{n!}\frac{d^{n-1}}{dx^{n-1}}\left(\{g(x)\}^n\frac{dF(x)}{dx}\right),\] which you may use without proof. (i) By using Lagrange's identity, or otherwise, show that one root of the equation \[4z = 2 + z^3\] is given by \[z = \sum_{n=0}^{\infty} \frac{(3n)!}{(2n+1)!n!}\frac{1}{2^{4n+1}}\] (ii) By considering \(z = x + \lambda(z^2 - 1)\), or otherwise, prove the identity \[0 \equiv x^3 + \sum_{n=2}^{\infty} \frac{x^n}{n!}\frac{d^{n-1}}{dx^{n-1}}(x^2-1)^n\] [You may assume all series converge.]
The triangle \(ABC\) is isosceles and has a right angle at \(B\). The sides \(AB\), \(BC\), \(AC\) are of unit length. Points \(X\), \(Y\), \(Z\) are selected at random on \(AB\), \(BC\), \(AC\), respectively. Let \(x\), \(y\) denote the distances of \(X\), \(Y\) from \(B\). Show that for fixed \(x\) and \(y\) the probability that \(ZXY\) and \(ZYX\) are both acute is \[\frac{x^2 + y^2}{x + y}.\] Hence show that the probability that both \(ZXY\) and \(ZYX\) are acute is \(\frac{2}{3} - \frac{1}{4} = \frac{5}{12}\).
A shooting gallery has two targets. A marksman has probability \(p\), \(q\) of hitting his aim when aiming for the first, second target respectively \((0 < p + q < 2)\). He never hits the target not aimed for, and each shot is independent of the others. He decides which target to aim for as follows: initially he aims for the first target; thereafter if his previous shot hit its mark, he fires at the same target, but if his previous shot missed, he aims at the other target. Obtain an expression for the probability that his \(n\)th shot hits its mark, and show that as \(n\) tends to infinity, this approaches \(\frac{p+q-2pq}{2-p-q}\).
The trace of a square matrix is defined to be the sum of its diagonal elements. If \(A\) and \(B\) are both two by two matrices, show that \[\text{trace}(AB) = \text{trace}(BA)\] If the elements of the two by two matrix \(A\) are functions of \(t\), \(\frac{dA}{dt}\) denotes the matrix whose elements are the derivatives of the corresponding elements of \(A\). If \(\Delta\) equals the determinant of the matrix \(A\), which may be assumed to be non-zero, show that \[\frac{1}{\Delta}\frac{d\Delta}{dt} = \text{trace}\left(A^{-1}\frac{dA}{dt}\right),\] where \(A^{-1}\) is the matrix inverse of \(A\). If, additionally, \(A\) satisfies the differential equation \[\frac{dA}{dt} = AB - BA,\] where the elements of \(B\) depend on \(t\), show that both \(\Delta\) and trace \((A^2)\) are independent of \(t\).