Problems

Filters
Clear Filters

1 problem found

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