Problems

Filters
Clear Filters

6 problems found

2023 Paper 3 Q5
D: 1500.0 B: 1500.0
number theory diophantine equations factorisation prime numbers proof by contradiction integer solutions

  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.

View
2018 Paper 2 Q6
D: 1600.0 B: 1484.7
proof number theory factorial prime numbers divisibility exhaustive search inequality

  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! \,. \]

Solution:

  1. Let \(n! + 5 = p\). If \(n \geq 5\) then \(5\) divides the LHS and so must also divide the RHS. Since \(n!+5 > 5\) this means the RHS cannot be prime. Therefore consider \(n = 1, 2, 3, 4\). \begin{align*} n = 1: && 1! + 5 = 6 &&\text{ nope} \\ n=2: && 2! + 5 = 7 && \checkmark \\ n=3: && 3! + 5 = 11 && \checkmark \\ n=4: && 4! + 5 = 29 && \checkmark \end{align*} Therefore the solutions are \((2,7), (3,11), (4,29)\).
  2. Suppose \(1! \times 3! \times \cdots \times (2n-1)! = m!\). If \(n \geq 7\) then \(m! > (4n)!\) (by the first theorem) in particular \(m > 4n\). Therefore (by the second theorem) the RHS is divisible by some prime which cannot divide the LHS. Therefore consider \(n = 1,2,3,4,5,6\) \begin{align*} n = 1: && 1! = 1 = 1! && \checkmark \\ n = 2: && 1! \times 3! = 6 = 3! && \checkmark \\ n = 3: && 1! \times 3! \times 5! = 6! && \checkmark \\ n = 4: && 1! \times 3! \times 5! \times 7! = 6! \times 7! = 10! && \checkmark \\ n = 5: && 1! \times 3! \times 5! \times 7! \times 9! = 10! 9! > 11! && \text{would need a factor of } 11\text{ so no} \\ n = 6: && 1! \times 3! \times 5! \times 7! \times 9! \times 11! = 10! 11! 9! > 13! && \text{would need a factor of } 13\text{ so no} \\ \end{align*} Therefore all solutions are \((1,1), (2,3), (3,6), (4,10)\)

View
2016 Paper 3 Q5
D: 1700.0 B: 1500.0
binomial theorem proof by induction prime numbers inequality divisibility binomial coefficient number theory

  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\).

Solution:

  1. Notice that \((1+x)^{2m+1} = 1+\binom{2m+1}{1}x+\cdots + \binom{2m+1}{m}x^{m} + \binom{2m+1}{m+1} + \cdots\). Notice also that \(\binom{2m+1}{m} = \binom{2m+1}{m+1}\). Therefore evaluating at \(x = 1\), we see \(2^{2m+1} > \binom{2m+1}{m} + \binom{2m+1}{m+1} = 2 \binom{2m+1}{m} \Rightarrow \binom{2m+1}{m} < 2^{2m}\)
  2. Each prime dividing \(P_{m+1, 2m+1}\) divides the numerator of \(\binom{2m+1}{m}\) since it appears in \((2m+1)!\), but not the denominator, since they wont appear in \(m!\) or \((m+1)!\), and since they are prime they have to appear to divide it. Therefore the must divide \(\binom{2m+1}{m}\) and therefore \(P_{m+1,2m+1}\) must divide that binomail coefficient. Since \(a \mid b \Rightarrow a \leq b\) we must have \(P_{m+1, 2m+1} \leq \binom{2m+1}{m} < 2^{2m}\)
  3. Since \begin{align*} P_{1,2m+1} &= P_{1,m+1}P_{m+1, 2m+1} \tag{split into primes below \(m+1\) and abvoe} \\ &< 4^{m+1}P_{m+1,2m+1} \tag{use the condition from the question}\\ &<4^{m+1}2^{2m} \tag{use our inequality} \\ &= 4^{2m+1} \end{align*}
  4. We proceed by (strong) induction. Base case: (\(n = 2\)): \(P_{1,2} = 2 < 4^2 =16\) Suppose it is true for all \(k=2,3,\cdots,2m\) then it is true for \(k=2m+1\) by the previous part of the question. However it is also true for \(k=2m+2\), since that can never be prime (as n is now an even number bigger than 2). Therefore by the principle of mathematical induction it is true for all \(n\).

View
2014 Paper 1 Q1
D: 1500.0 B: 1500.0
proof number theory difference of two squares parity factorisation odd and even prime numbers counting arguments

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.

Solution:

  1. \(\,\) \begin{align*} && 3 &= 2^2 - 1^2 \\ && 5 &= 3^2 - 2^2 \\ && 8 &= 3^2 - 1^2 \\ && 16 &= 5^2 - 3^2 \end{align*}
  2. Suppose \(n = 2k+1\), then \(n = (k+1)^2 - k^2\)
  3. Suppose \(n = 4k\) then \(n = (2k+1)^2 - (2k-1)^2\)
  4. All squares leave a remainder of \(0\) or \(1\) on division by \(4\). Therefore the difference can leave a remainder of \(0\), \(1\), \(-1 \equiv 3\), none of which are \(2\).
  5. Suppose \(n = pq = a^2 - b^2\) with \(a > b\) ie \((a-b)(a+b) = pq\). Since \(p\) is prime, \(p \mid (a-b)\) or \(p \mid (a+b)\). Similarly for \(q\). Suppose also (wlog) that \(p > q\) Since the factors of \(pq\) are \(1, p, q, pq\) then \(a-b = 1, p\) (which are two possibilities) and \(a+b = pq, q\), ie \(a = \frac{1+pq}{2}, \frac{p+q}{2}\) and \(b = \frac{pq-1}{2}, \frac{p-q}{2}\) \begin{align*} && pq &= \left ( \frac{1+pq}{2} \right)^2- \left ( \frac{1-pq}{2} \right)^2 \\ &&&= \left ( \frac{p+q}{2} \right)^2- \left ( \frac{p-q}{2} \right)^2 \\ \end{align*} Where everything is an integer since \(p\) and \(q\) are odd. If we have \(p > 2\) and \(q = 2\) then \(p\) is odd and the number has the form \(4k+2\) which cannot be expressed as the difference of two squares.
  6. \(675 = 3^3 \cdot 5^2\), each factor pair of \(675\) will lead to a different solution of \(675 = a^2-b^2\), since we will have an equation \(a-b = X, a+b = Y\) where \(X, Y\) are both odd. Therefore there are as many solution as (half) the number of factors, ie \(4 \times 3 = 12\)

View
2000 Paper 2 Q1
D: 1600.0 B: 1516.0
proof unit fractions number theory prime numbers factorisation uniqueness algebraic manipulation Erdos-Straus conjecture

A number of the form \(1/N\), where \(N\) is an integer greater than 1, is called a unit fraction. Noting that \[ \frac1 2 =\frac13 + \frac16\\\ \mbox{ and } \frac13 = \frac14 + \frac1{12}, \] guess a general result of the form $$ \frac1N =\frac1a +\frac1b \tag{*} $$ and hence prove that any unit fraction can be expressed as the sum of two distinct unit fractions. By writing \((*)\) in the form \[ (a-N)(b-N)=N^2 \] and by considering the factors of \(N^2\), show that if \(N\) is prime, then there is only one way of expressing \(1/N\) as the sum of two distinct unit fractions. Prove similarly that any fraction of the form \(2/N\), where \(N\) is prime number greater than 2, can be expressed uniquely as the sum of two distinct unit fractions.

Solution: Notice that \(\frac{1}{N} = \frac{1}{N+1} + \frac{1}{N(N+1)}\), so any unit fraction can be expressed as the sum of two distinct unit fractions. \begin{align*} && \frac{1}N &= \frac1a + \frac1b \\ \Leftrightarrow && ab&= Nb+Na \\ \Leftrightarrow && 0 &= (a-N)(b-N)-N^2 \\ \Leftrightarrow && N^2 &= (a-N)(b-N) \end{align*} If \(N\) is prime then the only factors of \(N^2\) are \(1,N\) and \(N^2\). if \(a-N = b-N = N\) then \(a=b\) and we don't have distinct fractions. Therefore \(a-N = 1\) and \(b-N = N^2\) and we obtain the decomposition earlier (and it must be the only solution). \begin{align*} && \frac2N &= \frac1a+\frac1b \\ \Leftrightarrow && 2ab &= Nb+Na \\ \Leftrightarrow && 4ab &= 2Na+2Nb \\ \Leftrightarrow && N^2 &= (2a-N)(2b-N) \end{align*} Therefore for \(a,b\) to be distinct we must have \(2a = N+1\) and \(2b = N+N^2\) as the only possible factorisation. Both of the right hand sides are even so we can write \[ \frac{1}{N} = \frac{1}{\frac{N+1}{2}} + \frac{1}{\frac{N(N+1)}{2}} \] and this is unique

View
1987 Paper 3 Q1
D: 1500.0 B: 1500.0
proof number theory divisibility factorial prime numbers Wilson's theorem special cases

Find the set of positive integers \(n\) for which \(n\) does not divide \((n-1)!.\) Justify your answer. [Note that small values of \(n\) may require special consideration.]

Solution: Claim: \(n \not \mid (n-1)!\) if and only if \(n\) is prime or \(4\) Proof: \((\Leftarrow)\)

  1. \(4 \not \mid 3! = 6\).
  2. If \(p\) is prime, then \(p \not \mid k\) for \(k < n\), therefore \(p \not \mid (n-1)!\)
\((\Rightarrow)\) If \(n = 1\) then \(1 \mid 0! = 1\) so \(1\) is not in our set. The numbers less than \(6\) are all accounted for (either primes, \(4\) or \(1\)), so let \(n\) be a composite number larger than \(6\), ie \(n = ab\). Suppose first \(a \neq b\) then \((n-1) = 1 \cdots a \cdots b \cdots (n-1)\) so \(n \mid (n-1)!\). Suppose instead that \(a = b\), then \(n = a^2\). Since we know \(a \geq 3\) we must have \(1 \cdots a \cdots (2a) \cdots (a^2-1)\) so \(a^2 \mid (n-1)!\) and we're done.

View