Harrison Chapman

  1. Teaching
  2. Math 301
  3. Homework
  4. Homework 5

Math 301: Homework 5

Toggle fullscreen
Due: Friday, October 11, 2019

Reading: Read sections 6.1, 6.2, 6.3, 6.4.

Exercises:

  1. Define the Lucas numbers by \(L_0 = 2\), \(L_1 = 1\), and \(L_{n+1} = L_n + L_{n-1}\) for \(n > 1\).

    If the Lucas numbers satisfy the formula

    \[ L_n = c_1\left(\frac{1+\sqrt 5}{2}\right)^n + c_2\left(\frac{1-\sqrt 5}{2}\right)^n \]

    solve for \(c_1\) and \(c_2\).

    We solve the system of equations \(2 = L_0 = c_1 + c_2\) and \(1 = L_1 = c_1\left(\frac{1+\sqrt 5}{2}\right) + c_2\left(\frac{1-\sqrt 5}{2}\right)\).

    The first yields that \(c_2 = 2 - c_1\), while the second has that

    \[\begin{align*} 1 &= c_1\left(\frac{1+\sqrt 5}{2}\right) + c_2\left(\frac{1-\sqrt 5}{2}\right) \\ 2 &= c_1\left({1+\sqrt 5}\right) + c_2\left({1-\sqrt 5}\right) \\ 2 &= c_1 + c_2 + \sqrt 5(c_1 - c_2) \\ 2 &= c_1 + (2 - c_1) + \sqrt 5(c_1 - (2 - c_1)) \\ 0 &= 2 c_1 - 2 \\ 1 &= c_1 \end{align*}\]

    So \(c_1 = 1\) and \(c_2 = 2 - c_1 = 1\).

  2. All variables \(a, b, c, p\) are integers. Show that:

    1. If \(a \mid b\) and \(a \mid c\) then \(a \mid (b+c)\).

    2. If \(a \mid b\) and \(a \not\mid c\) then \(a \not\mid (b+c)\).

    3. If \(p\) is prime and \(p \mid ab\) then at least one of \(p \mid a\) or \(p \mid b\).

    1. \(a \mid b\) and \(a \mid c\) means that there exist integers \(m,n\) so that \(b = ma\) and \(c = na\). These two equalities combine to show that \(b+c = (m+n)a\). As \((m+n)\) is an integer this means that \(a \mid (b+c)\).

    2. Suppose that \(a \mid (b+c)\). \(a \mid b\) and \(a \mid (b+c)\) means that there exist integers \(m,n\) so that \(b = ma\) and \((b+c) = na\). These two equalities combine to show that \(c = (n-m)a\). As \((n-m)\) is an integer this means that \(a \mid c\), a contradiction as we took the hypothesis that \(a \nmid c\). So \(a \nmid (b+c)\).

    3. \(p \mid ab\), so \(p\) appears in the prime factorization of \(ab\). But prime factorizations are unique, and so \(p\) must appear in the prime factorization of \(a\), or \(b\), or both. In either case, \(p \mid a\) or \(p \mid b\).

  3. All variables \(a, b, c\) are integers. Show that:

    1. If \(a \mid b\) and \(b \mid c\) then \(a \mid c\).

    2. If \(a \mid b\) and \(a \mid c\) then \(a \mid (b-c)\).

    3. If \(a \mid b\) and \(a \not\mid c\) then \(a \not\mid (b-c)\).

    1. \(a \mid b\) and \(b \mid c\) means that there exist integers \(m,n\) so that \(b = ma\) and \(c = nb\). So \(c = n(ma) = (nm)a\). As \(nm\) is an integer, we have that \(a \mid c\).

    2. \(a \mid b\) and \(a \mid c\) means that there exist integers \(m,n\) so that \(b = ma\) and \(c = na\). These two equalities combine to show that \(b-c = (m-n)a\). As \((m-n)\) is an integer this means that \(a \mid (b-c)\).

    3. Suppose that \(a \mid (b-c)\). \(a \mid b\) and \(a \mid (b-c)\) means that there exist integers \(m,n\) so that \(b = ma\) and \((b-c) = na\). These two equalities combine to show that \(c = (n-m)a\). As \((n-m)\) is an integer this means that \(a \mid c\), a contradiction as we took the hypothesis that \(a \nmid c\). So \(a \nmid (b-c)\).

  4. Prove that if \(n\) is a positive integer that is not a square (that is, there is no integer \(m\) with \(n = m^2\)), then \(\sqrt n\) is irrational.

    1. Suppose for contradiction that \(\sqrt n\) is rational, so that there exist integers \(p, q\) with \(q \ne 0\) so that \(\sqrt n = p/q\). Then \(n = p^2/q^2\) and so \(n p^2 = q^2\). As \(n\) is not a perfect square, it has at least one prime, \(r\), with odd exponent in its unique prime factorization. As \(p^2\) is a square, all of the primes in its prime factorization have even exponent. So there must be an odd power of \(r\) in the prime factorization of the LHS. But as the RHS is \(q^2\), any power of \(r\) in the factorization of the RHS must have even exponent. This is a contradiction, so \(\sqrt n\) could not have been rational.