Problems

Filters
Clear Filters

2 problems found

2013 Paper 2 Q7
D: 1600.0 B: 1516.0
proof Pell equation Diophantine equation integer solutions number theory factorisation triangular numbers prime factorisation

  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.

Solution:

  1. \((x,y) = (1,0)\) we have Suppose \(p^2-2q^2 = 1\), then \begin{align*} && (3p+4q)^2-2\cdot(2p+3q)^2 &= 9p^2+24pq + 16q^2 - 2\cdot(4p^2+12pq+9q^2) \\ &&&= p^2(9-8) + pq(24-24) + q^2(16-18) \\ &&&= p^2 - 2q^2 = 1 \end{align*} So we have: \begin{array}{c|c} x & y \\ \hline 1 & 0 \\ 3 & 2 \\ 17 & 12 \\ \end{array}
  2. Suppose \(x = 2m+1\) and \(y = 2n\) then \begin{align*} && 1 & = x^2 - 2y^2 \\ &&&= (2m+1)^2 - 2(2n)^2 \\ &&&= 4m^2 + 4m + 1 - 8n^2 \\ \Leftrightarrow && n^2 &= \frac{m(m+1)}{2} \end{align*}
  3. Suppose \(b^3 = c^4 - a^2 =(c^2-a)(c^2+a)\), since \(b\) is prime and \(c^2 + a > c^2-a\) we must have: \begin{align*} && p = c^2-a && p^2 =c^2 +a \\ \Rightarrow && c^2 = \frac{p+p^2}{2} && a = \frac{p^2-p}2\\ && 1 = c^2-a && p^3 = c^2+a \\ \Rightarrow && c^2 = \frac{p^3+1}{2} && a = \frac{p^3-1}{2} \end{align*} Note that \(c^2 = \frac{p(p+1)}{2}\) is reminicent of our first equation, so suppose \(n = c = 6\) and \(p = m = 8\) then \(6^4 = 8^3 + 28^2\)

View
1996 Paper 2 Q6
D: 1600.0 B: 1500.0
proof number theory prime factorisation divisor counting proper factors optimisation

A proper factor of a positive integer \(N\) is an integer \(M\), with \(M\ne 1\) and \(M\ne N\), which divides \(N\) without remainder. Show that \(12\) has \(4\) proper factors and \(16\) has \(3\). Suppose that \(N\) has the prime factorisation \[N=p_{1}^{m_{1}}p_{2}^{m_{2}}\dots p_{r}^{m_{r}},\] where \(p_{1}, p_{2}, \dots, p_{r}\) are distinct primes and \(m_{1}, m_{2}, \dots, m_{r}\) are positive integers. How many proper factors does \(N\) have and why? Find:

  1. the smallest positive integer which has precisely 12 proper factors;
  2. the smallest positive integer which has at least 12 proper factors.

Solution: \(12\) has factors \(1,2,3,4,6,12\) of which \(4\) are neither \(1\) nor \(12\). \(16\) has factors \(1,2,4,8,16\) of which \(3\) are neither \(1\) nor \(16\). If \(N = p_1^{m_1} \cdots p_r^{m_r}\) then \(N\) has \((m_1+1)\cdots(m_r+1)\) factors since we can have between \(0 \leq k \leq m_i\) of the \(i\)th prime factor, whcih is \(m_i+1\) possibilities. We then need to subtract two for the proper factors, ie \((m_1+1)\cdots(m_r+1) - 2\).

  1. We need \((m_1 + 1) \cdots (m_r + 1) - 2 = 12\) ie \((m_1+1) \cdots (m_r +1) = 14\). Since \(14 = 2 \times 7\) we should have two prime factors, ie of the form \(p_1^6p_2^1\). The smallest number of this form is \(2^6 \cdot 3 = 192\)
  2. We wish to make \((m_1+1)\cdots(m_r+1) \geq 14\) with \(2^{m_1} \cdot 3^{m_2} \cdots p_r^{m_r}\) as small as possible and \(m_1 \geq m_2 \geq \cdots \geq m_r\). With \(1\) prime, the best we can do is \(2^{13}\). With \(2\) primes the best we can do is \(2^p \cdot 3^q\) with \((p+1)(q+1) \geq 14\). \begin{array}{c|c} q & p & N \\ \hline 0 & 13 & 2^{13} \\ 1 & 6 & 2^6 \cdot 3^1 \\ 2 & 5 & 2^5 \cdot 3^2 \\ 3 & 3.& 2^3 \cdot 3^3 \end{array} So the best here is \(2^6 \cdot 3\) With \(3\) primes, the best we can do is \(2^p 3^q 5^r\) with \(p \geq q \geq r\) and \((p+1)(q+1)(r+1) \geq 14\) \begin{array}{c|c|c|c} r & q & p & N \\ \hline 1 & 1 & 3 & 2^3 \cdot 3 \cdot 5 \\ 1 & 2 & 2& 2^2 \cdot 3^2 \cdot 5 \\ 2 & 2& 2 & 2^2 \cdot 3^2 \cdot 5^2 \end{array} With four primes we can achieve it immediately with \(2\cdot3\cdot5\cdot 7\) and more primes clearly wont help, so our best options is \(120\)

View