Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Exercises 11.3 Exercises

1.

Prove that there is no integer \(a\) that simulataneously satisfies
\begin{equation*} a \equiv 2 \mod 6 \qquad \text{and} \qquad a \equiv 7 \mod 9. \end{equation*}

2.

Let \(a,b,c\in\mathbb Z\text{.}\) If \(a^2+b^2=c^2\text{,}\) then \(a\) or \(b\) is even.

3.

Let \(n\in\mathbb{N}\text{.}\) Suppose that \(a\in\mathbb{Z}\) is such that \(\gcd(a,n)\gt1\text{.}\) Show, by contradiction, that there is no \(k\in\mathbb{Z}\) so that \(ak\equiv1\mod{n}\text{.}\) This statement implies that \([a]_n\) is not invertible, which is a concept defined in Exercise 9.7.17.

4.

Let \(n\in\mathbb{N}\text{,}\) \(n\geq 2\text{,}\) and \(a,b\in\mathbb{Z}\text{.}\) Prove that if \(ab\equiv 1 \pmod{n}\text{,}\) then \(\forall c\in \mathbb{Z}, c\not\equiv 0\pmod{n}\) we have \(ac\not\equiv 0\pmod{n}\text{.}\)

5.

Prove that there do not exist \(x,y\in\mathbb Z\) that satisfy the equation \(5y^2-4x^2=7\text{.}\)

6.

Prove each of the following statements:
  1. There is no smallest positive rational number.
  2. There is no smallest positive irrational number.

7.

Two irrationality proofs.
  1. Prove that \(\sqrt{6}\) is an irrational number.
  2. Prove that \(\sqrt{2} + \sqrt{3}\) is irrational.

8.

Prove that \(\sqrt[3]{25}\) is irrational.

9.

Prove that if \(k\) is a positive integer and \(\sqrt{k}\) is not an integer, then \(\sqrt{k}\) is irrational.

10.

Let \(r,x\in\mathbb{R}\text{,}\) with \(r\neq0\text{.}\) Prove by contradiction that if \(r\) is rational and \(x\) is irrational, then \(rx\) must be irrational.

11.

Consider the following statements about preserving irrationality under addition and multiplication.
  1. Consider the following faulty proof of the statement, “If \(x,y\in\mathbb{R}\) are irrational, then \(xy\) is irrational.”
    Let \(x,y\in\mathbb{R}\) be irrational. Then there are no \(m,n,p,q\in\mathbb{Z}\) such that \(x=m/n\) and \(y=p/q\text{.}\) Hence for any \(m,n,p,q\in\mathbb{Z}\text{,}\)
    \begin{equation*} xy \neq \frac{mp}{nq}. \end{equation*}
    Since \(mp,nq\in\mathbb{Z}\text{,}\) we see that \(xy\) cannot be written as a fraction, and so \(xy\) is irrational.
    Show by counterexample that the statement above is false.
  2. Prove or disprove the following statement: If \(x,y\in\mathbb{R}\) are irrational, then \(x+y\) is irrational.

12.

Let \(x \in \mathbb{R}\) satisfy \(x^7 + 5x^2 - 3 = 0\text{.}\) Then prove that \(x\) is irrational.

13.

Consider the following questions about the irrationality of logarithmic values.
  1. Prove that \(5^k\) is odd for all \(k\in\mathbb{N}\text{.}\)
  2. Prove that \(\log_2(5)\) is irrational.
  3. Determine for which \(n\in\mathbb{N}\) is \(\log_2(n)\) irrational. Prove your answer. You may assume the following statement:
    For any \(n\in\mathbb{N}\text{,}\) there is some \(a\in \mathbb{Z}\text{,}\) \(a\geq 0\) and \(b\in \mathbb{Z}\) that is odd, so that \(n=2^ab\text{.}\)
For this question, you may assume the following properties about the logarithm:
  • if \(x\gt1\text{,}\) then \(\log_2(x)\gt0\text{;}\)
  • for any \(x,y\gt0\text{,}\)
    \begin{equation*} \log_2(xy)=\log_2(x)+\log_2(y); \end{equation*}

14.

Consider the subset of rational numbers
\begin{equation*} A = \set{x \in \mathbb{Q} \st x \leq \sqrt{2}} \end{equation*}
Prove that it does not have a maximum.

15.

Prove that there do not exist \(a,n\in\mathbb N\) such that \(a^2 + 35 = 7^n.\)

16.

Let \(x\in (0,1)\text{.}\) Show that
\begin{equation*} \frac{1}{2x(1-x)}\geq 2 \end{equation*}
  1. by contradiction, and
  2. by a direct proof.

17.

Consider the following statement: For all \(x, y\in \mathbb{R}\) with \(x, y \gt 0\) and \(x\neq y\)
\begin{equation*} \frac{x}{y}+\frac{y}{x} \gt 2. \end{equation*}
  1. Prove the statement directly.
  2. Prove the statement by contradiction.
  3. How does the statement change if we remove the assumption \(x\neq y\) ? That is: For all \(x, y\in \mathbb{R}\) with \(x, y \gt 0\text{,}\) what can we say about \(\frac{x}{y}+\frac{y}{x}\text{?}\)

18.

Let \(a, b\in \mathbb{R}\) with \(a,b \gt 0\text{.}\) Show that
\begin{equation*} \frac{2}{a} + \frac{2}{b} \neq \frac{4}{a+b} \end{equation*}
  1. using a contradiction, and
  2. using a direct proof.

19.

Recall the Intermediate Value Theorem:
Let \(g: U \to \mathbb{R}\) where \(U\subseteq \mathbb{R}\text{.}\) Suppose \(g\) is continuous on \([a,b]\subseteq U\text{,}\) and
\begin{equation*} f(a) \geq c \geq f(b) \quad \text{ OR } \quad f(a) \leq c \leq f(b), \end{equation*}
then there exists \(x_0\in [a,b]\) such that \(g(x_0) = c\text{.}\)
Let \(f:\mathbb{R}\to \mathbb{R}\) be a continuous, bijective function. Using the Intermediate Value Theorem, prove that \(f\) is strictly increasing or strictly decreasing. See Exercise 10.8.19 for the definitions of strictly increasing and decreasing.
<Prev^TopNext>