Problems

In the equality \[ 4 + 5 + 6 + 7 + 8 = 9 + 10 + 11, \] the sum of the five consecutive integers from 4 upwards is equal to the sum of the next three consecutive integers. Throughout this question, the variables \(n\), \(k\) and \(c\) represent positive integers.

1. Show that the sum of the \(n + k\) consecutive integers from \(c\) upwards is equal to the sum of the next \(n\) consecutive integers if and only if \[ 2n^2 + k = 2ck + k^2. \]
2. Find the set of possible values of \(n\), and the corresponding values of \(c\), in each of the cases
   1. \(k = 1\)
   2. \(k = 2\).
3. Show that there are no solutions for \(c\) and \(n\) if \(k = 4\).
4. Consider now the case where \(c = 1\).
   1. Find two possible values of \(k\) and the corresponding values of \(n\).
   2. Show, given a possible value \(N\) of \(n\), and the corresponding value \(K\) of \(k\), that \[ N' = 3N + 2K + 1 \] will also be a possible value of \(n\), with \[ K' = 4N + 3K + 1 \] as the corresponding value of \(k\).
   3. Find two further possible values of \(k\) and the corresponding values of \(n\).

1. The complex numbers \(z\) and \(w\) have real and imaginary parts given by \(z = a + \mathrm{i}b\) and \(w = c + \mathrm{i}d\). Prove that \(|zw| = |z||w|\).
2. By considering the complex numbers \(2 + \mathrm{i}\) and \(10 + 11\mathrm{i}\), find positive integers \(h\) and \(k\) such that \(h^2 + k^2 = 5 \times 221\).
3. Find positive integers \(m\) and \(n\) such that \(m^2 + n^2 = 8045\).
4. You are given that \(102^2 + 201^2 = 50805\). Find positive integers \(p\) and \(q\) such that \(p^2 + q^2 = 36 \times 50805\).
5. Find three distinct pairs of positive integers \(r\) and \(s\) such that \(r^2 + s^2 = 25 \times 1002082\) and \(r < s\).
6. You are given that \(109 \times 9193 = 1002037\). Find positive integers \(t\) and \(u\) such that \(t^2 + u^2 = 9193\).

1. Show that if \[\frac{1}{x} + \frac{2}{y} = \frac{2}{7}\,,\] then \((2x - 7)(y - 7) = 49\). By considering the factors of \(49\), find all the pairs of positive integers \(x\) and \(y\) such that \[\frac{1}{x} + \frac{2}{y} = \frac{2}{7}\,.\]
2. Let \(p\) and \(q\) be prime numbers such that \[p^2 + pq + q^2 = n^2\] where \(n\) is a positive integer. Show that \[(p + q + n)(p + q - n) = pq\] and hence explain why \(p + q = n + 1\). Hence find the possible values of \(p\) and \(q\).
3. Let \(p\) and \(q\) be positive and \[p^3 + q^3 + 3pq^2 = n^3\,.\] Show that \(p + q - n < p\) and \(p + q - n < q\). Show that there are no prime numbers \(p\) and \(q\) such that \(p^3 + q^3 + 3pq^2\) is the cube of an integer.

1. Suppose that there are three non-zero integers \(a\), \(b\) and \(c\) for which \(a^3 + 2b^3 + 4c^3 = 0\). Explain why there must exist an integer \(p\), with \(|p| < |a|\), such that \(4p^3 + b^3 + 2c^3 = 0\), and show further that there must exist integers \(p\), \(q\) and \(r\), with \(|p| < |a|\), \(|q| < |b|\) and \(|r| < |c|\), such that \(p^3 + 2q^3 + 4r^3 = 0\). Deduce that no such integers \(a\), \(b\) and \(c\) can exist.
2. Prove that there are no non-zero integers \(a\), \(b\) and \(c\) for which \(9a^3 + 10b^3 + 6c^3 = 0\).
3. By considering the expression \((3n \pm 1)^2\), prove that, unless an integer is a multiple of three, its square is one more than a multiple of \(3\). Deduce that the sum of the squares of two integers can only be a multiple of three if each of the integers is a multiple of three. Hence prove that there are no non-zero integers \(a\), \(b\) and \(c\) for which \(a^2 + b^2 = 3c^2\).
4. Prove that there are no non-zero integers \(a\), \(b\) and \(c\) for which \(a^2 + b^2 + c^2 = 4abc\).

1. Use De Moivre's theorem to prove that for any positive integer \(k > 1\), \[ \sin(k\theta) = \sin\theta\cos^{k-1}\theta \left( k - \binom{k}{3}(\sec^2\theta - 1) + \binom{k}{5}(\sec^2\theta - 1)^2 - \cdots \right) \] and find a similar expression for \(\cos(k\theta)\).
2. Let \(\theta = \cos^{-1}(\frac{1}{a})\), where \(\theta\) is measured in degrees, and \(a\) is an odd integer greater than \(1\). Suppose that there is a positive integer \(k\) such that \(\sin(k\theta) = 0\) and \(\sin(m\theta) \neq 0\) for all integers \(m\) with \(0 < m < k\). Show that it would be necessary to have \(k\) even and \(\cos(\frac{1}{2}k\theta) = 0\). Deduce that \(\theta\) is irrational.
3. Show that if \(\phi = \cot^{-1}(\frac{1}{b})\), where \(\phi\) is measured in degrees, and \(b\) is an even integer greater than \(1\), then \(\phi\) is irrational.

If \(x\) is a positive integer, the value of the function \(\mathrm{d}(x)\) is the sum of the digits of \(x\) in base 10. For example, \(\mathrm{d}(249) = 2 + 4 + 9 = 15\). An \(n\)-digit positive integer \(x\) is written in the form \(\displaystyle\sum_{r=0}^{n-1} a_r \times 10^r\), where \(0 \leqslant a_r \leqslant 9\) for all \(0 \leqslant r \leqslant n-1\) and \(a_{n-1} > 0\).

1. Prove that \(x - \mathrm{d}(x)\) is non-negative and divisible by \(9\).
2. Prove that \(x - 44\mathrm{d}(x)\) is a multiple of \(9\) if and only if \(x\) is a multiple of \(9\). Suppose that \(x = 44\mathrm{d}(x)\). Show that if \(x\) has \(n\) digits, then \(x \leqslant 396n\) and \(x \geqslant 10^{n-1}\), and hence that \(n \leqslant 4\). Find a value of \(x\) for which \(x = 44\mathrm{d}(x)\). Show that there are no further values of \(x\) satisfying this equation.
3. Find a value of \(x\) for which \(x = 107\mathrm{d}\left(\mathrm{d}(x)\right)\). Show that there are no further values of \(x\) satisfying this equation.

A sequence \(u_k\), for integer \(k \geqslant 1\), is defined as follows. \[ u_1 = 1 \] \[ u_{2k} = u_k \text{ for } k \geqslant 1 \] \[ u_{2k+1} = u_k + u_{k+1} \text{ for } k \geqslant 1 \]

1. Show that, for every pair of consecutive terms of this sequence, except the first pair, the term with odd subscript is larger than the term with even subscript.
2. Suppose that two consecutive terms in this sequence have a common factor greater than one. Show that there are then two consecutive terms earlier in the sequence which have the same common factor. Deduce that any two consecutive terms in this sequence are co-prime (do not have a common factor greater than one).
3. Prove that it is not possible for two positive integers to appear consecutively in the same order in two different places in the sequence.
4. Suppose that \(a\) and \(b\) are two co-prime positive integers which do not occur consecutively in the sequence with \(b\) following \(a\). If \(a > b\), show that \(a-b\) and \(b\) are two co-prime positive integers which do not occur consecutively in the sequence with \(b\) following \(a-b\), and whose sum is smaller than \(a+b\). Find a similar result for \(a < b\).
5. For each integer \(n \geqslant 1\), define the function \(\mathrm{f}\) from the positive integers to the positive rational numbers by \(\mathrm{f}(n) = \dfrac{u_n}{u_{n+1}}\). Show that the range of \(\mathrm{f}\) is all the positive rational numbers, and that \(\mathrm{f}\) has an inverse.

Consider the following steps in a proof that \(\sqrt{2} + \sqrt{3}\) is irrational.

1. If an integer \(a\) is not divisible by 3, then \(a = 3k \pm 1\), for some integer \(k\). In both cases, \(a^2\) is one more than a multiple of 3.
2. Suppose that \(\sqrt{2} + \sqrt{3}\) is rational, and equal to \(\frac{a}{b}\), where \(a\) and \(b\) are positive integers with no common factor greater than one.
3. Then \(a^4 + b^4 = 10a^2b^2\).
4. So if \(a\) is divisible by 3, then \(b\) is divisible by 3.
5. Hence \(\sqrt{2} + \sqrt{3}\) is irrational.

1. Show clearly that steps 1, 3 and 4 are all valid and that the conclusion 5 follows from the previous steps of the argument.
2. Prove, by means of a similar method but using divisibility by 5 instead of 3, that \(\sqrt{6} + \sqrt{7}\) is irrational. Why can divisibility by 3 not be used in this case?

1. Find all pairs of positive integers \((n,p)\), where \(p\) is a prime number, that satisfy \[ n!+ 5 =p \,. \]
2. In this part of the question you may use the following two theorems:
   1. For \(n\ge 7\), \(1! \times 3! \times \cdots \times (2n-1)! > (4n)!\,\).
   2. For every positive integer \(n\), there is a prime number between \(2n\) and \(4n\).
   Find all pairs of positive integers \((n,m)\) that satisfy \[ 1! \times 3! \times \cdots \times (2n-1)! = m! \,. \]

The set \(S\) consists of all the positive integers that leave a remainder of 1 upon division by 4. The set \(T\) consists of all the positive integers that leave a remainder of 3 upon division by 4.

1. Describe in words the sets \(S \cup T\) and \(S \cap T\).
2. Prove that the product of any two integers in \(S\) is also in \(S\). Determine whether the product of any two integers in \(T\) is also in \(T\).
3. Given an integer in \(T\) that is not a prime number, prove that at least one of its prime factors is in \(T\).
4. For any set \(X\) of positive integers, an integer in \(X\) (other than 1) is said to be \(X\)-prime if it cannot be expressed as the product of two or more integers all in \(X\) (and all different from 1).
   • \(\bf (a)\) Show that every integer in \(T\) is either \(T\)-prime or is the product of an odd number of \(T\)-prime integers.
   • \(\bf (b)\) Find an example of an integer in \(S\) that can be expressed as the product of \(S\)-prime integers in two distinct ways. [Note: \(s_1s_2\) and \(s_2s_1\) are not counted as distinct ways of expressing the product of \(s_1\) and \(s_2\).]

1. By considering the binomial expansion of \((1+x)^{2m+1}\), prove that \[ \binom{ 2m \! +\! 1}{ m} < 2^{2m}\,, \] for any positive integer \(m\).
2. For any positive integers \(r\) and \(s\) with \(r< s\), \(P_{r,s}\) is defined as follows: \(P_{r,s}\) is the product of all the prime numbers greater than \(r\) and less than or equal to \(s\), if there are any such primes numbers; if there are no such primes numbers, then \(P_{r,s}=1\,\). For example, \(P_{3,7}=35\), \(P_{7,10}=1\) and \(P_{14,18}=17\). Show that, for any positive integer \(m\), \(P_{m+1\,,\, 2m+1} \) divides \(\displaystyle \binom{ 2m \! +\! 1}{ m} \,,\) and deduce that \[ P_{m+1\,,\, 2m+1} < 2^{2m} \,. \]
3. Show that, if \(P_{1,k} < 4^k\) for \(k = 2\), \(3\), \(\ldots\), \(2m\), then \( P_{1,2m+1} < 4^{2m+1}\,\).
4. Prove that \(\P_{1,n} < 4^n\) for \(n\ge2\).

All numbers referred to in this question are non-negative integers.

1. Express each of the numbers 3, 5, 8, 12 and 16 as the difference of two non-zero squares.
2. Prove that any odd number can be written as the difference of two squares.
3. Prove that all numbers of the form \(4k\), where \(k\) is a non-negative integer, can be written as the difference of two squares.
4. Prove that no number of the form \(4k+2\), where \(k\) is a non-negative integer, can be written as the difference of two squares.
5. Prove that any number of the form \(pq\), where \(p\) and \(q\) are prime numbers greater than 2, can be written as the difference of two squares in exactly two distinct ways. Does this result hold if \(p\) is a prime greater than 2 and \(q=2\)?
6. Determine the number of distinct ways in which 675 can be written as the difference of two squares.

1. Write down a solution of the equation \[ x^2-2y^2 =1\,, \tag{\(*\)} \] for which \(x\) and \(y\) are non-negative integers. Show that, if \(x=p\), \(y=q\) is a solution of (\(*\)), then so also is \(x=3p+4q\), \(y=2p+3q\). Hence find two solutions of \((*)\) for which \(x\) is a positive odd integer and \(y\) is a positive even integer.
2. Show that, if \(x\) is an odd integer and \(y\) is an even integer, \((*)\) can be written in the form \[ n^2 = \tfrac12 m(m+1)\,, \] where \(m\) and \(n\) are integers.
3. The positive integers \(a\), \(b\) and \(c\) satisfy \[ b^3=c^4-a^2\,, \] where \(b\) is a prime number. Express \(a\) and \(c^2\) in terms of \(b\) in the two cases that arise. Find a solution of \(a^2+b^3=c^4\), where \(a\), \(b\) and \(c\) are positive integers but \(b\) is not prime.

In this question, you may assume that, if \(a\), \(b\) and \(c\) are positive integers such that \(a\) and \(b\) are coprime and \(a\) divides \(bc\), then \(a\) divides \(c\). (Two positive integers are said to be coprime if their highest common factor is 1.)

1. Suppose that there are positive integers \(p\), \(q\), \(n\) and \(N\) such that \(p\) and \(q\) are coprime and \(q^nN=p^n\). Show that \(N=kp^n\) for some positive integer \(k\) and deduce the value of \(q\). Hence prove that, for any positive integers \(n\) and \(N\), \(\sqrt[n]N\) is either a positive integer or irrational.
2. Suppose that there are positive integers \(a\), \(b\), \(c\) and \(d\) such that \(a\) and \(b\) are coprime and \(c\) and \(d\) are coprime, and \(a^ad^b = b^a c^b \,\). Prove that \(d^b = b^a\) and deduce that, if \(p\) is a prime factor of \(d\), then \(p\) is also a prime factor of \(b\). If \(p^m\) and \(p^n\) are the highest powers of the prime number \(p\) that divide \(d\) and \(b\), respectively, express \(b\) in terms of \(a\), \(m\) and \(n\) and hence show that \(p^n\le n\). Deduce the value of \(b\). (You may assume that if \(x > 0\) and \(y\ge2\) then \(y^x > x\).) Hence prove that, if \(r\) is a positive rational number such that \(r^r\) is rational, then \(r\) is a positive integer.

1. The point with coordinates \((a, b)\), where \(a\) and \(b\) are rational numbers,is called an integer rational point if both \(a\) and \(b\) are integers; a non-integer rational point if neither \(a\) nor \(b\) is an integer.
   • \(\bf (a)\) Write down an integer rational point and a non-integer rational point on the circle \(x^2+y^2 =1\).
   • [\bf (b)] Write down an integer rational point on the circle \(x^2+y^2=2\). Simplify \[ (\cos\theta + \sqrt m \sin\theta)^2 + (\sin\theta - \sqrt m \cos\theta)^2 \, \] and hence obtain a non-integer rational point on the circle \(x^2+y^2=2\,\).
2. The point with coordinates \((p+\sqrt 2 \, q\,,\, r+\sqrt 2 \, s)\), where \(p\), \(q\), \(r\) and \(s\) are rational numbers, is called: an integer \(2\)-rational point if all of \(p\), \(q\), \(r\) and \(s\) are integers; a non-integer \(2\)-rational point if none of \(p\), \(q\), \(r\) and \(s\) is an integer.
   • \(\bf (a)\) Write down an integer \(2\)-rational point, and obtain a non-integer \(2\)-rational point, on the circle \(x^2+y^2=3\,\).
   • [\bf(b)] Obtain a non-integer \(2\)-rational point on the circle \(x^2+y^2=11\,\).
   • [\bf(c)]Obtain a non-integer \(2\)-rational point on the hyperbola \(x^2-y^2 =7 \).