Problems

Filters
Clear Filters

5 problems found

2016 Paper 1 Q7
D: 1500.0 B: 1500.0
proof number theory modular arithmetic sets divisibility prime factorization closure properties counterexample

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

Solution:

  1. \(S \cup T\) is the set of odd positive integers. \(S \cap T\) is the empty set.
  2. Suppose we have two integers in \(S\), say \(4n+1\) and \(4m+1\), so \((4n+1)(4m+1) = 16nm + 4(n+m) + 1 = 4(4nm + n+m) + 1\) which clearly is in \(S\). The product of any two integers in \(T\) is in \(S\), since \((4n+3)(4m+3) = 16nm + 12(n+m) + 9 = 4(4nm+3(n+m) + 2) + 1\)
  3. Suppose \(p \in T\) is not prime, then it must have prime factors. They must all be odd, so they are in \(T\) or \(S\). If they are all in \(S\) then \(p\) must also be in \(S\) (as the product of numbers in \(S\)) but this is a contraction. Therefore \(p\) must have a prime factor in \(T\).
    • \(3, 7, 11, 19\) are all primes in \(T\). Notice therefore that any product of two of them must be \(S\)-prime. But then \((3 \times 7) \times (11 \times 19)\) and \((3 \times 11) \times (7 \times 19)\) are distinct factorisations into \(S\)-prime factors.

View
2013 Paper 3 Q5
D: 1700.0 B: 1487.0
proof number theory irrationality coprime divisibility proof by contradiction prime factorization rational and irrational numbers

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.

Solution:

  1. Suppose \(q^nN = p^n\) then since \((p,q) =1\) we must have \(p \mid N\), and then by dividing both \(p^n\) and \(N\) by \(p\) we can repeat this process \(n\) times to find that \(N = kp^n\) and in particular \(q = 1\). Suppose \(\sqrt[n]{N} = \frac{p}q\) for \(p,q\) coprime positive integers (ie it is not irrational), then \(q^nN = p^n\) and so \(q = 1\) and in fact \(\sqrt[n]{N}\) is an integer so \(N\).
  2. Suppose \((a,b) = 1, (c,d) = 1\) and \(a^ad^b = b^ac^b\), then since \((a,b) = 1\) we must have \((b^a, a) = 1\) so \(b^a \mid d^b\). Similarly since \((c,d) = 1\) we must have \((d^b, c) = 1\) so \(d^b \mid b^a\). Therefore \(d^b = b^a\). Suppose \(p \mid d\) then \(p \mid d^b = b^a \Rightarrow p \mid b\). Suppose \(\nu_p(d) = m, \nu_p(b) = n\) we must have \(bm = \nu_p(d^b) = \nu_p(b^a) = an\), ie \(b = \frac{an}{m}\). Note that \(p^n \mid b \Rightarrow p^n \mid n \frac{a}{m} \Rightarrow p^n \mid n \Rightarrow p^n \leq n\). Since \((p,a) = 1\).. But since \(p^n > n\) if \(p \geq 2\) we must have that \(b = 1\). Therefore suppose \(r = \frac{a}{b}\) with \((a,b) = 1\) an \(r^r = \frac{c}{d}\) we must ahve \(a^ac^b = b^ad^b\) and so \(b = 1\) implying \(r\) is an integer.

View
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
2005 Paper 2 Q2
D: 1600.0 B: 1516.0
Euler's totient function number theory prime factorization proof counterexample multiplicative functions integer properties

For any positive integer \(N\), the function \(\f(N)\) is defined by \[ \f(N) = N\Big(1-\frac1{p_1}\Big)\Big(1-\frac1{p_2}\Big) \cdots\Big(1-\frac1{p_k}\Big) \] where \(p_1\), \(p_2\), \(\dots\) , \(p_k\) are the only prime numbers that are factors of \(N\). Thus \(\f(80)=80(1-\frac12)(1-\frac15)\,\).

  1. (a) Evaluate \(\f(12)\) and \(\f(180)\). (b) Show that \(\f(N)\) is an integer for all \(N\).
  2. Prove, or disprove by means of a counterexample, each of the following: (a) \(\f(m) \f(n) = \f(mn)\,\); (b) \(\f(p) \f(q) = \f(pq)\) if \(p\) and \(q\) are distinct prime numbers; (c) \(\f(p) \f(q) = \f(pq)\) only if \(p\) and \(q\) are distinct prime numbers.
  3. Find a positive integer \(m\) and a prime number \(p\) such that \(\f(p^m) = 146410\,\).

Solution:

  1. \(f(12) = f(2^2 \cdot 3) = 12 \cdot (1-\frac12)\cdot(1-\frac13) = 12 \cdot \frac12 \cdot \frac 23 = 4\) \(f(180) = f(2^2 \cdot 3^2 \cdot 5) = 180 \cdot \frac12 \cdot \frac23 \cdot \frac 45 = 12 \cdot 4 = 48\) Suppose \(N\) has prime decomposition \(p_1^{a_1} \cdots p_k^{a_k}\), then \(f(N) = p_1^{a_1} \cdots p_k^{a_k} (1 - \frac{1}{p_1})\cdots ( 1- \frac{1}{p_k}) = p_1^{a_1-1} \cdots p_k^{a_k-1}(p_1-1) \cdots (p_k-1)\) which is clearly an integer.
  2. \(f(2) = 1, f(4) = 2 \neq f(2) \cdot f(2)\) If \(p, q\) are distinct primes then \(f(p) = p \cdot \frac{p-1}{p} = p-1\) and \(f(q) = q-1\). \(f(pq) = pq \frac{p-1}{p} \cdot \frac{q-1}{q} = (p-1)(q-1) = f(p)f(q)\) \(f(12) = 4 = 2\cdot 2 = f(4) \cdot f(3)\)
  3. \(f(p^m) = p^{m-1} (p-1)\) \(146410 = 10 \cdot 14641 = 10 \cdot 11^4\). Therefore \(p = 11, m = 5\)

View
1997 Paper 2 Q1
D: 1600.0 B: 1500.0
sequences digit constraints enumeration summation prime factorization combinatorics arithmetic

Find the sum of those numbers between 1000 and 6000 every one of whose digits is one of the numbers \(0,\,2,\,5\) or \(7\), giving your answer as a product of primes.

Solution: The first digit is \(2\) or \(5\), all the other digits can be any value from \(0,2,5,7\). Therefore we have \begin{align*} S &= 2000 \cdot 4^3+5000 \cdot 4^3 + (200+500+700) \cdot 2 \cdot 4^2 + (20+50+70) \cdot 2 \cdot 4^2 + (2+5+7) \cdot 2 \cdot 4^2 \\ &= 7 \cdot 4^3 \cdot 2^3 \cdot 5^3 + 14 \cdot 2 \cdot 4^2 \cdot 111 \\ &= 2^{9} \cdot5^3 \cdot 7 + 2^{6} \cdot 3 \cdot 7 \cdot 37 \\ &= 2^6 \cdot 7 \cdot (1000+111) \\ &= 2^6 \cdot 7 \cdot 11 \cdot 101 \end{align*} Alternatively, consider adding the first and last terms, and second and second and last terms, etc we obtain \(7777\). There are \(2 \cdot 4^3\) terms so \(7777 \cdot 4^3 = 2^6 \cdot 7 \cdot 11 \cdot 101\)

View