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 simultaneously 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.”
    🔗

    Faulty proof.

    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.
🔗
🔗
🔗
PrevTopNext