Problems

Filters
Clear Filters

1 problem found

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