Problems

Filters
Clear Filters

2 problems found

2015 Paper 3 Q5
D: 1700.0 B: 1516.0
proof by contradiction irrationality well-ordering principle sqrt(2) cube root set theory integer properties

  1. In the following argument to show that \(\sqrt2\) is irrational, give proofs appropriate for steps 3, 5 and 6.
    1. Assume that \(\sqrt2\) is rational.
    2. Define the set \(S\) to be the set of positive integers with the following property:
      \(n\) is in \(S\) if and only if \(n \sqrt2\) is an integer.
    3. Show that the set \(S\) contains at least one positive integer.
    4. Define the integer \(k\) to be the smallest positive integer in \(S\).
    5. Show that \((\sqrt2-1)k\) is in \(S\).
    6. Show that steps 4 and 5 are contradictory and hence that \(\sqrt2\) is irrational.
  2. Prove that \(2^{\frac13} \) is rational if and only if \(2^{\frac23}\) is rational. Use an argument similar to that of part (i) to prove that \(2^{\frac13}\) and \(2^{\frac23}\) are irrational.

Solution:

  1. For step 3, since we have assumed \(\sqrt{2}\) is rational we can write it in the form \(p/q\) with \(p, q\) coprime with \(q \geq 1\). Then \(q \in S\) since \(q\sqrt{2} = p\) which is an integer. For step 5, notice that \((\sqrt{2}-1)k\) is an integer (since \(\sqrt{2}k\) is an integer and so is \(-k\). It is also positive since \(\sqrt{2} > 1\). We must check that \((\sqrt{2}-1)k \cdot \sqrt{2} = 2k - \sqrt{2}k\) is also an integer, but clearly it is as both \(2k\) and \(-\sqrt{2}k\) are integers. Therefore \((\sqrt{2}-1)k \in S\). For step 6, notice that \((\sqrt{2}-1) < 1\) and therefore \((\sqrt{2}-1)k < k\), contradicting that \(k\) is the smallest element in our set. (And all non-empty sets of positive integers have a smallest element)
  2. Claim: \(2^{\frac13}\) is irrational \(\Leftrightarrow 2^{\frac23}\) is irrational. Proof: Since \(2^{\frac13} \cdot 2^{\frac23} = 2\) if one of them is rational, then the other one must also be rational. Which is the same as them both being irrational at the same time.
    1. Assume that \(\sqrt[3]{2}\) is rational, ie \(\sqrt[3]{2} = p/q\) for some integers.
    2. \(S := \{ n \in \mathbb{Z}_{>0} : n \sqrt[3]{2} \text{ and } n \sqrt[3]{4}\in \mathbb{Z}\}\)
    3. Suppose \(k\) is the smallest element in \(S\) (which must exist, consider \(q^2\)
    4. Consider \((\sqrt[3]{2}-1)k\) then clearly this is an integer, and \((\sqrt[3]{2}-1)\sqrt[3]{2}k = \sqrt[3]{4}k - \sqrt[3]{2}k \in \mathbb{Z}\) and \((\sqrt[3]{2}-1)\sqrt[3]{4}k = 2 k -\sqrt[3]{4}k \in \mathbb{Z}\).
    5. But this is a smaller element of \(S\), contradicting that \(k\) is the smallest element. Therefore, we have a contradiction.

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