Problems

Filters
Clear Filters

2 problems found

2020 Paper 2 Q5
D: 1500.0 B: 1500.0
number theory digit sum divisibility modular arithmetic proof base 10 representation exhaustive search

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.

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