Problems

Filters
Clear Filters

2 problems found

2009 Paper 1 Q1
D: 1500.0 B: 1500.0
number theory divisor counting prime factorization divisor function systematic enumeration optimisation

A {\em proper factor} of an integer \(N\) is a positive integer, not \(1\) or \(N\), that divides \(N\).

  1. Show that \(3^2\times 5^3\) has exactly \(10\) proper factors. Determine how many other integers of the form \(3^m\times5^n\) (where \(m\) and \(n\) are integers) have exactly 10 proper factors.
  2. Let \(N\) be the smallest positive integer that has exactly \(426\) proper factors. Determine \(N\), giving your answer in terms of its prime factors.

Solution:

  1. All factors of \(3^2 \times 5^3\) have factors of the form \(3^k \times 5^l\) where \(0 \leq k \leq 2\) and \(0 \leq l \leq 3\) therefore there are \(3\) possible values for \(k\) and \(4\) possible values for \(l\), which gives \(3 \times 4 = 12\) factors, which includes \(2\) factors we aren't counting, so \(10\) proper factors. By the same argument \(3^m \times 5^n\) has \((m+1) \times (n+1) - 2\) proper factors, so we want \((m+1) \times (n+1) = 12\), so we could have \begin{array}{cccc} \text{factor} & m+1 & n + 1 & m & n \\ 12 = 12 \times 1 & 12 & 1 & 11 & 0 \\ 12 = 6 \times 2 & 6& 2 & 5 & 1 \\ 12 = 4 \times 3 & 4& 3 & 3 & 2 \\ 12 = 3 \times 4 & 3& 4 & 2 & 3 \\ 12 = 2 \times 6 & 2& 6 & 1 & 5 \\ 12 = 1 \times 12 & 1& 12 & 0 & 11 \\ \end{array} So we could have \(3^{11}, 3^{5} \times 5^1 3^3 \times 5^2, 3^2 \times 5^3, 3^1 \times 5^5, 5^{11}\)
  2. Suppose \(N\) has \(426\) proper factors, then it has \(428 = 2^2 \times 107\) factors, so it will either factor as \(p^{427}\) or \(p_1^{106} p_2^{3}\) or \(p_1^{106} p_2 p_3\). Clearly the first will be very large, and we should have \(p_1 < p_2 < p_3\), so lets consider \(2^{106}\) with either \(3^3 = 27\) or \(3 \times = 15 < 27\). Therefore we should take \(2^{106} \times 3 \times 5\)

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